设为首页收藏本站

爱吱声

 找回密码
 注册
搜索
查看: 1763|回复: 3
打印 上一主题 下一主题

[科技前沿] 突然想到让deepseek来解释一下递归

[复制链接]
  • TA的每日心情
    开心
    2025-9-8 05:08
  • 签到天数: 3 天

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 / t9 v' f6 Y1 J4 [4 \* P

    # y! g. I& v' H: R2 G' X解释的不错
      }( a3 a1 [; f
    # i4 w' w! m% l& p, G; }9 z3 r递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。) T6 g; p: Q& t$ P: Q5 a
    : D% ]5 F- i9 w
    关键要素
    : {% P: ]/ H3 `& i1 R1. **基线条件(Base Case)**
    + o& v  J/ j" u& r0 n) _9 }5 [0 F   - 递归终止的条件,防止无限循环2 H) p' r. L1 f* b- z
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1: Z; K+ D3 O) I5 n0 v5 P3 c

      V# l* j$ L0 j8 D' L* P. R2. **递归条件(Recursive Case)**2 o  d6 u1 K( g4 ~6 A! h
       - 将原问题分解为更小的子问题" p: A, Y  U" u* }* p' W
       - 例如:n! = n × (n-1)!9 D' v' C+ {* G' n7 s
    ( I, U' q  r& o- p9 l3 Z' d# j
    经典示例:计算阶乘
    1 k, f: m0 \% L  [: Y: Qpython
    & m0 T' O" |; A7 O: Vdef factorial(n):
    0 h5 S+ S' L) i( o( y( N! {    if n == 0:        # 基线条件
      c! [- V% b+ W  [/ @1 C8 |8 d  T        return 1
    / g2 F0 \! L3 g  v    else:             # 递归条件
    ; I* q5 X- I7 v; E        return n * factorial(n-1)
    . d$ w9 f2 J# _* w" m+ M  B; w执行过程(以计算 3! 为例):/ q8 r2 P6 [. p# X+ o2 x" B/ d
    factorial(3)# B% _" ]4 V* j3 s6 n  `8 [6 d9 c
    3 * factorial(2)
    + ~" z& Q1 N% m  o2 a3 * (2 * factorial(1))2 {& u( j) X( ]/ P% K& A
    3 * (2 * (1 * factorial(0)))
    " T# i; ?9 C! j0 S. Z1 E# E3 * (2 * (1 * 1)) = 6+ e0 h8 P/ y  H3 ]4 ]. D& [/ Y

    + ]0 U: ~) D: o 递归思维要点
    / @) u; C5 [. N1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    5 F$ n/ R; z6 h5 p2. **栈结构**:每次调用都会创建新的栈帧(内存空间)" @( _! l% g& _
    3. **递推过程**:不断向下分解问题(递)
    7 F: q5 h1 `5 Z4. **回溯过程**:组合子问题结果返回(归)# t0 o% v2 U1 ?# V
    ! N4 n- |+ c/ Z" G' P. G7 V
    注意事项1 v0 v5 k6 n1 [8 S* s/ ~% n& S# z
    必须要有终止条件
    , I, ^6 X1 I+ ?  W递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    , A' m- D! c4 }' a+ Z( M+ D某些问题用递归更直观(如树遍历),但效率可能不如迭代
    5 ?6 X4 M1 M/ K3 J尾递归优化可以提升效率(但Python不支持)9 j) k/ o4 O) O- w% Z

    ' @! V( Q. o6 B* \3 Z' n% {$ ^ 递归 vs 迭代
    3 q$ h% b9 \( J% x9 X# W|          | 递归                          | 迭代               |
    8 f# R2 t) m  W|----------|-----------------------------|------------------|
    2 F& k" F2 F# Z: Y+ @| 实现方式    | 函数自调用                        | 循环结构            |4 D1 n7 z/ W9 E) r
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |2 j  N& r+ J% y0 k8 Q2 q8 \. r
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |% `+ h  E( c6 a$ I) e
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |- t; a" B2 h# n- R

      N# f7 ?7 Y4 F! g" n# n+ h 经典递归应用场景
      x9 f8 ~1 l9 w, S) T1. 文件系统遍历(目录树结构)# ]) y, ?9 d$ h2 J  H3 Q- [! g
    2. 快速排序/归并排序算法
      k& M. z; T% N3. 汉诺塔问题% o5 n/ Q0 I  @% e, q
    4. 二叉树遍历(前序/中序/后序)3 U8 d6 v1 m) e& `% `( v
    5. 生成所有可能的组合(回溯算法)
    - [2 g8 `+ s# m$ ]: _& Y# }) `9 Y7 j8 u6 O! w
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

    参与人数 3爱元 +26 收起 理由
    pcb + 4
    老票 + 16 涨姿势
    住在乡下 + 6 给力

    查看全部评分

  • TA的每日心情
    慵懒
    2 小时前
  • 签到天数: 3140 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,/ o$ H- K2 A7 w7 Z; g) B! z/ J
    我推理机的核心算法应该是二叉树遍历的变种。
    8 d5 O. H0 Z5 H( w2 B+ I4 x2 A' l另外知识系统的推理机搜索深度(递归深度)并不长,没有超过10层的,如果输入变量多的话,搜索宽度很大,但对那时的286-386DOS系统,计算压力也不算大。
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    板凳
    发表于 2025-2-2 00:45:59 | 只看该作者
    Recursion in programming is a technique where a function calls itself in order to solve a problem. It is a powerful concept that allows you to break down complex problems into smaller, more manageable subproblems. Here's a detailed explanation:+ F" \; G# U# N& W
    Key Idea of Recursion: |$ e3 t6 {6 I3 ^) `+ s

    % [  v: T; b) s- f* W/ W+ {, ZA recursive function solves a problem by:3 h# J% [# ~; u0 @
      _& x% A1 O' `7 M) i/ {  Z
        Breaking the problem into smaller instances of the same problem.6 \( t  V+ V+ z
    & F# C0 z! [4 U3 f5 e
        Solving the smallest instance directly (base case).
    3 |& w1 y, C/ M2 M& U1 j7 s1 e- p* J7 E7 ^7 n) {) |+ E/ S
        Combining the results of smaller instances to solve the larger problem.
    / L$ I# y+ ^- ^$ c  \% Q6 m5 N) j. _2 Y8 D
    Components of a Recursive Function
      M2 m( {$ e, Q5 _& w
    ' r) K+ d- Z9 n; q* z; l* D4 a1 i    Base Case:
    ! B, {9 k# k% M
    $ B; @/ p/ @; I4 Q5 Y        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.. W4 w  J! f( z! v) ?( x1 u

    % O1 w5 ~) A( V, j0 T% h        It acts as the stopping condition to prevent infinite recursion.  u6 [( \+ }# f& Z+ r6 |. m$ I

    ; ]" j, g' c" m2 p        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    / Z0 f6 L+ X# v' S) ]  I4 F% k# Q
    " T- h9 b) I5 H% F6 L2 r! J    Recursive Case:/ }. i2 i$ L( h9 k6 T- ?8 S
    + S; s/ K- ^2 q5 D
            This is where the function calls itself with a smaller or simpler version of the problem.
    1 W- w8 i5 \, S# c# W5 u- I* u
    ( D, L' s" Y' N& J" d/ i- H        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).6 S! S- \) w) ]" G
    9 W+ V8 U7 X& B7 o/ R
    Example: Factorial Calculation
    & T! W1 n8 x' L1 L; d3 H  j2 w+ r, ]  w0 `
    The factorial of a number n (denoted as n!) is the product of all positive integers less than or equal to n. It can be defined recursively as:
    2 h; _. B& A  a
    6 [5 d$ f+ |$ V7 e    Base case: 0! = 1
    3 E( {6 Z* p1 `4 T0 a) ~5 w, Z$ W$ e- i( C
        Recursive case: n! = n * (n-1)!
    / z$ M# t9 r1 A: m  f' X, R7 n1 B" C1 {' V% u7 U6 y+ [. q# s
    Here’s how it looks in code (Python):
    % ?3 [. F4 @$ V2 Y3 @& Spython5 d2 ]4 \7 }2 V' q3 @9 x$ n; D
    ; x& h% _  T2 U9 G

    & v" p' ^: e" @$ b) Y0 P- ^def factorial(n):" {2 o# X" ^' l# b5 W/ w1 r
        # Base case0 q6 e; z& E) x8 G; Q) I5 N
        if n == 0:
    ) Z% X; b6 k( S/ {        return 1
    * z+ c' [! e+ E1 v# X- c% l    # Recursive case, \1 t- J/ ]% y9 N9 G$ E! \
        else:: B4 p! k/ x8 R- R
            return n * factorial(n - 1)
    4 s9 o. ?" P/ r, H* D7 O4 D7 d: U/ Q" D# d* B/ j( b8 I: y: W
    # Example usage
    ( a( V6 s* b3 H4 zprint(factorial(5))  # Output: 120
    8 `; s' B- H" i; z( G% ]3 A9 I) R5 ^! u( n$ l" g
    How Recursion Works  `! |0 e2 H' `' c+ j$ I
    ! D9 k: {$ Z% H- M
        The function keeps calling itself with smaller inputs until it reaches the base case.
    5 E5 D' A- |* D6 A' F9 E# r. _( k0 w5 Z4 g* z% {+ V, K( S! A# K
        Once the base case is reached, the function starts returning values back up the call stack.
    ) L0 n7 _9 \1 _" U
    5 E4 H: Q% l7 X. V9 R    These returned values are combined to produce the final result.- P% G1 X/ e0 T$ q
    8 h- L! o3 I4 r( U
    For factorial(5):7 [! H1 B6 p: ^, G
    - M4 c  o- B9 y3 z0 N
    6 |7 }5 H" \1 X+ P  n
    factorial(5) = 5 * factorial(4)
    " c/ o& K/ V# _. W, i& h7 k( M+ Ifactorial(4) = 4 * factorial(3)
    . K" E, S* B( s* {$ g/ F5 @factorial(3) = 3 * factorial(2)0 W) ^/ w7 j* F3 d8 ?7 a
    factorial(2) = 2 * factorial(1)
    + t/ S5 h  A' ?8 ffactorial(1) = 1 * factorial(0)
    * B7 D9 |* ]. U! s' V7 kfactorial(0) = 1  # Base case
    ; N+ ^- O- b' q! Z& J* E
    . a0 X* ?$ O5 j- j+ f3 fThen, the results are combined:
    ' f; r4 S. c" u) ], S" B9 I# n: I& [3 b- e; s: V

    7 C5 P% i4 B; {% F3 D: N' y' |factorial(1) = 1 * 1 = 1
    , F" w7 Q# ~3 `7 j/ V/ n, O6 ~! I& kfactorial(2) = 2 * 1 = 28 K; W3 {  t- w( Q. P& _
    factorial(3) = 3 * 2 = 6' ]6 R7 T1 Q$ {! b
    factorial(4) = 4 * 6 = 24& Q  p$ n" h, D+ j3 V
    factorial(5) = 5 * 24 = 120" A3 U. D3 b8 M$ y+ Y. I3 m* t3 C* P
    ! P: R. V: a/ O7 T: v2 L
    Advantages of Recursion
    ( o+ P8 I2 v" D
    3 l+ n0 a+ z; k) f    Simplicity: Recursive solutions are often more intuitive and easier to write for problems that have a natural recursive structure (e.g., tree traversals, divide-and-conquer algorithms).9 g  D7 ]5 f6 F

    8 [2 D' P) ~- y! ?" w    Readability: Recursive code can be more readable and concise compared to iterative solutions.) U# N7 T$ J! \5 L5 q$ J

    ( z9 l5 N8 b2 iDisadvantages of Recursion  J8 g1 u5 \- [

    1 m) N6 H; _- Y2 Q7 r    Performance Overhead: Each recursive call adds a new layer to the call stack, which can lead to high memory usage and potential stack overflow for deep recursion.5 C* F( A: O) C1 {8 m0 M$ i. l5 [
    ) M, X$ Y- I3 k
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).. \6 z; u# l6 R6 K: K9 S! x7 u: ?

    ! G* D# h, J% r0 l( Q* RWhen to Use Recursion
    5 ]! a, c5 [6 Y1 e
    4 `0 y+ m9 _. Z- u: Q: ~1 m: _/ k    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    & U5 m/ P, k6 Y8 B8 {! E: R5 {
    # R$ k* T: V8 ]1 h" x) f    Problems with a clear base case and recursive case.
    8 T) D+ k: C8 }* Z0 T( L3 q1 z' D4 ~) Y! K7 [4 S
    Example: Fibonacci Sequence  D$ k" }6 g0 G( b4 n, L  A
    ) ?9 k& e/ r9 x5 ]2 R
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:6 {+ O6 D, }, d# }

    ! f4 V5 U: D# i# h0 F    Base case: fib(0) = 0, fib(1) = 1# U, q4 c4 P0 k/ L- o! a: g# M

    7 k2 f. S, t7 |9 w& ?    Recursive case: fib(n) = fib(n-1) + fib(n-2)) s; ^/ T$ f. ?1 m* f! P  w

    ' X- z6 F& c0 G" E* apython
      Q" o* L" X/ {) }9 u9 ~
    / F0 _8 B3 z1 u
    9 G- P& ^0 c/ f0 }def fibonacci(n):
    $ J+ ~+ e. R3 P    # Base cases
    9 b7 A% u6 u% e) l    if n == 0:
    . E4 {% F3 p+ C: g        return 03 W! L) A. R% d0 D% O
        elif n == 1:: S3 G/ ]& H  n  R
            return 1
    7 `) Z7 m* m1 V; H1 |" e5 ?    # Recursive case' _6 y0 ]5 ?3 \
        else:# A( w) [4 p. c
            return fibonacci(n - 1) + fibonacci(n - 2)
    , j  q% T* h8 Y* o$ b5 k! R
    9 V8 k, _' G: c5 T0 N- ~5 T# Example usage
    3 L- K; f/ i0 S, S* q9 |* Gprint(fibonacci(6))  # Output: 8' F9 O/ r/ N0 @2 c1 g0 V4 Y

    8 x$ m' M$ y& E1 E% E. ?: nTail Recursion0 Q% {4 v2 W" J) a4 o8 ]  e1 e( r
    / x) D: |' R; e1 ?( z. V7 A
    Tail recursion is a special case of recursion where the recursive call is the last operation in the function. Some programming languages optimize tail-recursive functions to avoid stack overflow, but not all languages (e.g., Python does not optimize tail recursion).9 Z1 c3 i5 E- N( q

    2 V& K$ U3 L* f( ~5 }5 WIn summary, recursion is a fundamental concept in programming that allows you to solve problems by breaking them into smaller, self-similar subproblems. It’s important to define a base case to avoid infinite recursion and to understand the trade-offs between recursion and iteration.
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    地板
    发表于 2025-2-2 00:47:27 | 只看该作者
    我还让Deepseek 给我讲讲Linux Kernel Driver 现在的开发流程,让一个老同志复习复习,快忘光了。
    回复 支持 反对

    使用道具 举报

    手机版|小黑屋|Archiver|网站错误报告|爱吱声   

    GMT+8, 2026-1-8 08:03 , Processed in 0.028669 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表