设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    * q, V4 a7 }& w6 O& @* @' i
    , M9 d9 d. J  F& y* B6 a解释的不错+ \  `' T+ n( _* o
    " r: g9 [/ P* z3 k: L
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ) d0 V5 @, `2 S: O) J
    0 [: o5 m4 R& _  |1 g$ n8 b3 U1 L6 {/ l 关键要素( q7 `& c; |% U& A3 a( E, [) S
    1. **基线条件(Base Case)**
    ; Q& d6 b: p* q4 f2 v   - 递归终止的条件,防止无限循环
    9 _, S/ ?8 k* Y4 E: O3 Z, }! N   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 19 y5 h" l  k0 d- f; ]3 f  @

    ! T7 ?7 ?  |1 s4 i# H2 k2. **递归条件(Recursive Case)**7 K; s+ z5 R( }, v, w& C
       - 将原问题分解为更小的子问题! y0 Y# D- O" i) x
       - 例如:n! = n × (n-1)!
    0 V1 [5 @& o- A! v  b6 T/ C
    / z* Q7 ?$ O0 Q3 n# Z 经典示例:计算阶乘2 `2 _* l3 |% h
    python
    8 h$ q* y' O; K* I/ |! V/ z; jdef factorial(n):% L; h( c/ w+ k- D  b. q2 o/ \' w. D
        if n == 0:        # 基线条件' Y8 S" T' U2 y# e; r
            return 1, p: Y- ]# k; W' h
        else:             # 递归条件6 w" m3 Z  X2 J
            return n * factorial(n-1)! O. }# l9 X* n0 o7 o
    执行过程(以计算 3! 为例):$ o& L) K) S4 H
    factorial(3)  y" I2 X  A3 s
    3 * factorial(2)% `, I# X5 m$ ^& @
    3 * (2 * factorial(1))# v$ X7 i* D+ @% N. c8 x
    3 * (2 * (1 * factorial(0)))
    * [7 `3 ~' E9 Y9 \/ [" X3 }3 * (2 * (1 * 1)) = 64 m! o& ~2 Z2 J5 ^5 O$ a

    ; k0 Q+ n9 e7 V5 B5 g  B5 f; Q' J" p 递归思维要点" o3 |( y& l, X
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    - |2 z8 M8 Z2 k2. **栈结构**:每次调用都会创建新的栈帧(内存空间)* z1 J+ s& l5 V8 _0 Y$ _
    3. **递推过程**:不断向下分解问题(递)% Z1 T1 j4 c8 p% g: p
    4. **回溯过程**:组合子问题结果返回(归)# h# F" R3 N4 Z, O

    8 D; w( b7 @- v 注意事项2 s: u8 w; |8 ]
    必须要有终止条件6 T/ |7 G& e! D) q: l: q$ M0 N5 D
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)! P! D' {1 p% v. m$ f) X6 S
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    + }& z1 U8 V+ y& B尾递归优化可以提升效率(但Python不支持)
    ; ?9 t& q$ c1 v1 L  j# G
    . @  c4 l) k4 X. q7 W! F% c$ X 递归 vs 迭代2 f( z# W/ n0 r: F
    |          | 递归                          | 迭代               |! l, ^9 g  E( B# a/ d, U' |
    |----------|-----------------------------|------------------|; }1 G! K8 c) `. y$ k
    | 实现方式    | 函数自调用                        | 循环结构            |$ p4 J4 q# j! U0 U6 u  Z" r, b$ u0 G
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    + B% F7 Z/ |# K; X6 e, n$ R  F| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |( K- t$ H0 U/ h) @, v. d4 P6 }9 y
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    3 Z, \& C( X. ~* E# ?
      e* _0 V" Q8 \7 }2 t 经典递归应用场景
    - A. `3 c$ ~( l; D* \1. 文件系统遍历(目录树结构)
    6 _+ q2 y% |. a- l4 Q/ c2. 快速排序/归并排序算法/ ]8 t9 L# @: t" i9 L+ R
    3. 汉诺塔问题
    , E7 o1 j5 ^; S4 i4. 二叉树遍历(前序/中序/后序)
    8 v/ J  r- w2 X1 Z9 z. _5. 生成所有可能的组合(回溯算法)/ k" f9 f1 p6 c: c0 F& J) c
    2 T( ?7 B7 B) o, }6 m" ?7 T
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    半小时前
  • 签到天数: 3126 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    4 Z9 N9 q5 Q5 r1 ~3 y) {$ ~我推理机的核心算法应该是二叉树遍历的变种。3 e$ M* }& E3 N4 P* E
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:  [3 m5 y& N+ D* M; f
    Key Idea of Recursion
    4 H: ?' p1 S! g8 A, F2 l6 W. u9 A: S: h
    A recursive function solves a problem by:3 M# m1 M' c% G9 \5 m. H0 Q0 L* J

    , g/ p3 Q# W0 E; z! P5 \/ ?7 {$ Z    Breaking the problem into smaller instances of the same problem.7 A6 R3 h1 k6 I
    + A2 Q0 n; g4 o, `
        Solving the smallest instance directly (base case).
    - z, n7 f4 W; ~. K0 }
    $ J. G6 y1 E) Y& I3 z    Combining the results of smaller instances to solve the larger problem.+ M  }- Q  u3 ]) G2 M
    2 P1 v3 }/ D8 ]* Y0 u% M  y
    Components of a Recursive Function) D  G! u- b' j; g" S5 n
    ' V& `5 F% l3 Q9 |( j  I
        Base Case:
    * U6 s# x" H' \5 `
    1 W! P5 ^5 l! g/ Y) G        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.# m0 [, v/ w# g+ B+ k) w
    " B1 _; a7 x* K- s; O
            It acts as the stopping condition to prevent infinite recursion./ r# N/ j+ |6 \; y, D/ s1 }+ J: N6 V$ y
    % }- E  L% E; J' E
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.2 ]! }& X$ P. c+ R  |- }

    $ t7 t! f# q4 j) F1 {" Z    Recursive Case:+ j+ l' o+ h  q9 Q3 N, Z9 H

    * x( R' r. y6 i. I3 t        This is where the function calls itself with a smaller or simpler version of the problem.
    ) c& g6 _2 u* M; S, z  a* J( s+ F4 H# O2 Q3 S$ w' J
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).+ N, ]4 K' c: E, w6 I
    ' F/ L0 F9 g/ R( }( h, `
    Example: Factorial Calculation
    ' a! N7 ^9 y! S  `9 V7 B4 N
    0 L  P9 Q6 t/ B$ R+ gThe 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:
    ; {; R  u- |: L5 q7 F" Y& c: J; U5 x$ e
        Base case: 0! = 1
    ! _2 b) F/ ]4 p2 Z2 L! [5 A, x- t7 w
        Recursive case: n! = n * (n-1)!
    0 o& ^9 N: q. }- C' \  f# r/ j9 s) [+ Z; t% Q% j3 G
    Here’s how it looks in code (Python):
    ) b; j( K1 T- U, B8 m5 wpython( A5 ?3 U' ^  M
    ; O4 k( R$ I2 J

    $ q$ _9 H8 d. {) q) U' Rdef factorial(n):- i) x# N8 ?4 v+ c) V8 d
        # Base case$ M9 l, b, c5 Y2 r. C# u
        if n == 0:
    : c$ W' a/ \# }4 |  Z" _+ e        return 19 b( m7 _% i! b+ K5 [
        # Recursive case
      P/ u* y+ Q- A0 t, D! V    else:3 o1 z6 {* I* ~, f- V+ s. ^+ \9 V, y
            return n * factorial(n - 1)6 ?% X. T- H) b* z% x/ B! ^( k

    0 q2 ~, p& L0 s# Example usage
    * y( D& _) |, ?. a+ kprint(factorial(5))  # Output: 120( H7 e# \- B1 ~+ g! u, j

    , n/ I. z% ]9 [How Recursion Works  p) G9 {4 ], O
    . e5 |3 W& ~0 _& _. ?7 |
        The function keeps calling itself with smaller inputs until it reaches the base case.  Z& \: I( Z1 j. |# ~" m# i
    ' [; A: {2 p- i0 a* V' U
        Once the base case is reached, the function starts returning values back up the call stack.; s5 \$ n) C, R5 Z

    " G; j0 `+ t3 U. T/ P/ f    These returned values are combined to produce the final result.
    0 f* k: k% q* J; q  }
    9 I4 K: t6 ?# z: j% xFor factorial(5):
    ; P% Y$ A; q* ]8 \* P8 u
    1 }" ~- W! f! d
    , l! z+ a2 L; W0 T5 Gfactorial(5) = 5 * factorial(4)
    4 e9 n/ d) x2 Q. z7 lfactorial(4) = 4 * factorial(3)* `! O) q  y3 t) @' n' W; _# A9 T
    factorial(3) = 3 * factorial(2)
    : M5 _8 D: |( V( O0 j# b( Z+ Jfactorial(2) = 2 * factorial(1)
    ) c9 C  {4 g5 X7 ~, W& qfactorial(1) = 1 * factorial(0)
    $ D' i3 r$ a8 ~factorial(0) = 1  # Base case
    . u6 c* m, d( N8 g
    ) O/ T+ |8 Z& a; OThen, the results are combined:# P" j$ H7 v# h/ Q( }- H6 r+ u$ x: J
    * \. z! a4 Y5 K( \, u+ [

    ) m$ X( V8 t! ^7 h; D* Ofactorial(1) = 1 * 1 = 1
    , v# u7 R; u+ y( k: f9 T$ Ofactorial(2) = 2 * 1 = 2" l9 @- c6 b$ E
    factorial(3) = 3 * 2 = 6
    % I& Z" \7 a% {7 G; x; Cfactorial(4) = 4 * 6 = 24
    ) P* L! P* k8 n/ Z' Ufactorial(5) = 5 * 24 = 1207 U3 A7 ^5 V1 z0 O
    7 _. l0 B8 o% }2 J7 v2 k/ B
    Advantages of Recursion, B6 T3 R: U. z) ^

    ; S7 j) I  b( ?; w9 P    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).
    7 v" C9 n9 h* C( I4 D0 N  ?9 t0 g
    1 {# {. v& V) ~& M4 y; S    Readability: Recursive code can be more readable and concise compared to iterative solutions.. D2 q( p  s2 q# ]  Y$ t
    ' d' S, [% ~7 \# m# h
    Disadvantages of Recursion$ k1 Z2 `% V) v. d" s8 ]

    7 K3 `5 g. n; m$ N( ?  }6 v( n    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.
    ) ]" g5 g$ e$ Q1 e
    " \! L, z, N5 G! f    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).2 F$ d, ~! v# w9 d& Z/ y4 D
    ; b1 D1 D' G0 d  x
    When to Use Recursion$ l" M6 a' e! ]9 w/ t3 M

    6 O0 r6 H1 f+ L# i/ B+ C- L/ W    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).8 U1 Z4 A( C! v, }1 l0 |

    % P7 T( E7 l  N$ d. k8 Z" v0 O    Problems with a clear base case and recursive case.
    ; [. t7 w! l$ @& u. X, ^# H7 A, |& p$ A8 l
    Example: Fibonacci Sequence
    * s8 C6 ]3 O$ _" ?8 W5 X& R) J4 y8 E) s8 m9 U: m- C
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:) u1 H% D7 ^* J* I& T

    & m  B) b# w# g    Base case: fib(0) = 0, fib(1) = 1+ o7 n0 [2 }/ M6 I; S$ d* |7 X) S$ F
    9 \: ?, v  k# h/ I
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    : ?' v5 r4 }6 K+ K% y% h4 X8 w( c3 D# x( Z. Y* w. X' d' E: ~
    python
    , |; I% W2 n7 W5 e3 T3 f" V! \. |% c7 s3 w; s1 u

    % N7 N& P/ j# \1 k* `$ o' xdef fibonacci(n):
      T' A! M4 }. P    # Base cases
    ) a! |5 ~* F$ B; T, K0 Z    if n == 0:
    5 T2 p& D$ K! P5 Z8 b        return 0
    : f5 T' y: @& u  q! B* Y7 ?  U4 m3 H    elif n == 1:- p: c$ j# k  ]' @! _
            return 11 G5 T  j+ ?% |1 `
        # Recursive case9 H* A9 x. f) s0 f* K
        else:$ v& }1 T, G4 k# e9 N8 G
            return fibonacci(n - 1) + fibonacci(n - 2)! ]4 Y8 x0 A% a. z
    / j$ N, ^) N( W. `
    # Example usage( i4 F0 o8 ]& A; v- {  v( X
    print(fibonacci(6))  # Output: 8) Z# U( M* B" Z
    / j" @# P9 E$ G8 _- ^4 w. E" v
    Tail Recursion
    7 d( Y/ f( e2 e7 q( y, n8 ~
    ' M- O; }( b* bTail 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).0 I' {9 F: q6 q. \- E* ]

    4 _1 Z& C6 ~2 @; ~. m/ r+ Y2 h- DIn 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, 2025-12-24 08:45 , Processed in 0.030360 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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