设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ; G& ~2 y% P  L  M  _1 G$ \
    ) e- m& j5 g* X  X' p% Q/ i解释的不错
      p2 r% `( w0 B4 s- o3 a9 ~( O% p/ [: C' B/ m# j' q% x' S
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    , o3 D+ {; U% Z$ C) V9 u
    ( n9 q5 M( v0 |! i! ?) v 关键要素
    3 K. Y6 @! e: E5 A, h- K. N1. **基线条件(Base Case)**
    ) K- t( Y2 i7 f% N1 q- s$ i   - 递归终止的条件,防止无限循环
    ' X* @# A+ O4 y, S" g! c& g$ E   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1# }7 n! ^; a9 G) J, x2 m  {: F1 D
    0 s+ k5 l9 t9 r" b! P. ]
    2. **递归条件(Recursive Case)**% Y5 H- Z& m; _9 F/ o7 E
       - 将原问题分解为更小的子问题% P9 e! m% e6 @; n$ D/ }4 {
       - 例如:n! = n × (n-1)!8 y# p0 c+ ~7 O; ~# r

    4 b: r. O, n8 i+ o0 I 经典示例:计算阶乘, V6 }" a8 V' m6 g6 C( l4 p. k, }; Q
    python! \# W8 a' b" H) y+ J" P3 T
    def factorial(n):
      G, ~4 }' \2 p; k* }  I0 R    if n == 0:        # 基线条件- v7 P" ^  l" ]- u
            return 1
    % h4 x; S! n5 ?/ d( O    else:             # 递归条件
    0 f/ B! U, \* K1 O( d: A( g* n! l        return n * factorial(n-1)
    9 v2 u& H4 P: J: j) Y执行过程(以计算 3! 为例):" S. B- K! ]& Y* @
    factorial(3)
    / k1 W- z  Y, A3 X2 A9 b+ x# |' t3 * factorial(2)0 Q0 I2 m, y% d; k% \
    3 * (2 * factorial(1))
    0 u5 U8 S& f' `9 C2 R3 * (2 * (1 * factorial(0))). ~( r: _' c# J( P/ r$ S
    3 * (2 * (1 * 1)) = 6+ A$ q' I/ k0 g- z
    , T1 k' {" M- h6 n* x: o# @
    递归思维要点
    ) ?3 L& _$ o# v* B1 x4 Q3 r+ I1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    4 q: q0 g5 R3 V2. **栈结构**:每次调用都会创建新的栈帧(内存空间)5 ]4 l+ P, U1 o
    3. **递推过程**:不断向下分解问题(递)
    8 M' ^0 b% e, t4 g4. **回溯过程**:组合子问题结果返回(归)
    & F# r5 U. s3 v; s( G1 ?
    ! a( i7 p- s3 @6 n0 L7 b 注意事项5 `, B& J+ g+ @% e6 o5 ~
    必须要有终止条件2 \5 u/ j7 [* a" s  A9 G1 U
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    4 L. z6 R  G; C* I某些问题用递归更直观(如树遍历),但效率可能不如迭代' w' ]" h  I- \; Q$ }5 F. @% [+ O
    尾递归优化可以提升效率(但Python不支持)
    1 R. l$ M' V3 J9 W2 m/ F
    9 K' I& H. z1 h, F( E0 r 递归 vs 迭代
    ! S, m! f; ^" V|          | 递归                          | 迭代               |. {' p. H4 Z7 y1 i
    |----------|-----------------------------|------------------|- s$ N: ~# ?- P) n! N3 m
    | 实现方式    | 函数自调用                        | 循环结构            |) W9 f& S% G  ^" p7 |, B7 M) p/ l
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |& F; k9 L1 U! F: R1 L
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    . Q/ L% q- E/ P% O9 D  j| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |% d+ o; ?% p( A7 A$ S, ~! z/ _2 j

    8 T# w( B" d. d% a 经典递归应用场景
    0 J; k1 l, n9 c/ d. |9 u1. 文件系统遍历(目录树结构)
      p# @. p) h# `- {+ x2. 快速排序/归并排序算法
    ( y/ T' k( z2 W  T9 w& C1 _  m3. 汉诺塔问题
    9 b' ]5 S4 j" O, p3 I) m4. 二叉树遍历(前序/中序/后序)) e) `6 Z4 w! E# B, \( \: q4 ?- v
    5. 生成所有可能的组合(回溯算法)
    ' Q, e8 z7 P" A  ?
    * P8 P5 U8 a3 ~7 H试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    昨天 07:10
  • 签到天数: 3153 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    . P4 r) U! ]- S! q: q我推理机的核心算法应该是二叉树遍历的变种。
    4 W. n3 r) o- d% |# h4 y' p6 X+ @% d另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:/ s- O$ Q) r" |- ?
    Key Idea of Recursion
    & I+ E) k* G, x# R& {' q, |7 d
    8 [( |6 |; o$ S- \! PA recursive function solves a problem by:
    ; j* b1 B. D% D. [( _
    ' t# g5 ~, T- K/ S    Breaking the problem into smaller instances of the same problem./ g; a. r6 m* C: `

    - F" t: ^% L3 Z* P/ Q    Solving the smallest instance directly (base case).' s; L$ J/ x% r7 s: e+ M

    $ Z/ @7 ]; d+ {& c& ^# b    Combining the results of smaller instances to solve the larger problem.3 {+ Q1 a# N) r( _# p7 ?2 ^
    . [( p4 P9 k6 p9 W7 ?! `
    Components of a Recursive Function) o" O5 v" s! ]6 H- |

    , o6 \! b, B/ U8 v    Base Case:5 z) O( U' f6 r

    9 I- S2 |% F& K! o, \* U2 y, }        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    + Z& N! M/ y8 G5 s8 E* I
    $ F( D% D+ ?, u1 y' p: ?        It acts as the stopping condition to prevent infinite recursion.
    4 J5 E- V/ e2 q0 {- F! m8 h, m$ Z* y! r; u% ~% y+ s3 u
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.8 C& z( j' r6 b# v: S
    % p- b& _5 L/ G6 Z5 F6 l! Q
        Recursive Case:2 F5 |4 k3 l' C

    ( i7 }; j( |4 T) N        This is where the function calls itself with a smaller or simpler version of the problem.1 h& s0 G% ]7 X" f0 r" F, i. w

    ; c! s  f4 D+ [  T6 N        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).6 P$ _. I$ }9 D( o! g% }0 c# w
    7 N* h, C/ f3 k! ^
    Example: Factorial Calculation
    9 y9 R- N" H4 u" x6 z2 f' K* l5 q% w8 F: `0 d  n
    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:
    9 _- x4 @  N, L. f" e5 v$ C$ w/ w  P- l/ X! U9 Q& L9 Z
        Base case: 0! = 1
    4 H, p$ V. H! V! @. _. M3 f
    7 A7 t: X+ g. f2 f; \" e& T+ l; X) k    Recursive case: n! = n * (n-1)!
    : w  u3 H7 Z, c: X1 H# u0 c' x9 G' i' L# N
    Here’s how it looks in code (Python):( J6 Z! f4 f" ]( X; T
    python
    ( G& ]1 n' Q3 ^; N% |; E  q# T9 |3 f& i1 o7 \( D
    ! T& {8 v0 }6 g. l% t3 C
    def factorial(n):
    - K+ D5 U$ J0 v; ~2 Q$ W; _: p/ g    # Base case# a4 e& ~: f( H
        if n == 0:
    2 D) \; \( ]: X3 f8 C6 A% f        return 1
    % A" V% j* r! Q, V7 x    # Recursive case
    $ L6 p7 b$ L# `' \    else:( I6 e  @8 o1 n9 |% Z# n' ?! k
            return n * factorial(n - 1)9 v: \3 i( j( \  U5 {: M. P3 }: m/ W
    0 H; Y/ K) c: ^! \: i
    # Example usage0 `# C0 u5 y- D, e2 D! w
    print(factorial(5))  # Output: 120
    # Z, g6 ~$ ?" P! B& @' Z0 x) D+ P0 p! X5 J/ P; E% r
    How Recursion Works
    3 I4 E2 V  O+ f- ]
    / g, w4 g2 i+ E9 O8 ]' ^    The function keeps calling itself with smaller inputs until it reaches the base case.- K- f# W0 C9 W9 Y1 V' ?
    0 W! t4 \% ], V7 j- L0 n" ?$ q' a
        Once the base case is reached, the function starts returning values back up the call stack.
    , J6 t. a' @6 {4 q
    2 O* K% U+ O: p/ @    These returned values are combined to produce the final result.: P3 h" \( o6 s! U3 y* A8 k
    . m+ Q) M1 m4 I0 H
    For factorial(5):( B7 }! d# M; q, f, i9 Z5 N

    4 X9 r  ^! y4 C+ ]+ @* c& r0 s; w9 ~* K( N5 a5 |7 I" O4 |
    factorial(5) = 5 * factorial(4)
    / o+ m, {% @6 W: Vfactorial(4) = 4 * factorial(3)) s$ l! j7 }8 y' n$ r; z
    factorial(3) = 3 * factorial(2)
    4 q7 Y. ^  |+ Mfactorial(2) = 2 * factorial(1)
    5 w6 t9 f  {2 |1 c$ m3 s1 pfactorial(1) = 1 * factorial(0)& e* ~0 h6 W5 c) t; R. n" S
    factorial(0) = 1  # Base case
    8 Z% V% U3 N2 f( d9 }5 L) y3 o& C/ |/ T2 q* ^
    Then, the results are combined:* C, V. r6 d5 x% O& P
    2 r0 Z0 i+ M6 n6 k, V( ]/ u
    / m4 d, C3 M; C: a9 L2 |/ c
    factorial(1) = 1 * 1 = 1
    1 O5 P9 m! t8 g  afactorial(2) = 2 * 1 = 2
    3 Y8 ?9 X% v+ _. J" Lfactorial(3) = 3 * 2 = 6* e7 y$ d- D7 ], i
    factorial(4) = 4 * 6 = 24' H0 Y6 `+ `6 B) L! t& |" `) k$ S
    factorial(5) = 5 * 24 = 1206 {& d+ `; O, H- @- Q" I8 [

    / D* G; o  h# L+ i$ bAdvantages of Recursion
    0 S8 r  v( A0 e& _9 [% b
    ' R* D% ?4 A2 Q* w# p' V    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).
    % [8 I3 n9 J+ [" R( g: k) X7 p
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    * P/ u" O3 R6 _: O* M2 l' Z
    # b" l" w$ b9 P. z+ P* u5 ]Disadvantages of Recursion
    - t2 z! r1 z, ]! d* v9 A( I/ B9 c- }  }8 V* ]1 F) M) R& 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.7 r" P6 p4 c6 r

    5 K5 U7 I$ G' o' {& w    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    + D5 ~/ C/ w, L3 ?6 h
    4 n) |+ c5 J  W8 r& x6 L+ H: MWhen to Use Recursion
    8 W& F  v7 ]& H; e  e) ~( Z! a& l9 P' w! v5 f/ x+ R
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).5 P( T7 S5 h# i; }/ I' b2 m1 Y# ~
    : }$ N( i; \$ \: t2 V% }
        Problems with a clear base case and recursive case.
    9 S$ `. h, t6 G" o$ T* ?; Z
    , u1 h" `' p/ }. J+ I4 R) h$ pExample: Fibonacci Sequence
    0 W+ g/ ~% g7 l2 o! s) j. T( W% g& u2 L$ t2 F" g7 i% v
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    1 Z7 e9 x9 k! t5 y. I# }' S& ~+ {0 \; |# S
        Base case: fib(0) = 0, fib(1) = 19 k% _6 m. ]" S* Q, }

    8 C. u' U; @5 `  O- a. u; X    Recursive case: fib(n) = fib(n-1) + fib(n-2); N8 |) s3 y! Y2 z" A$ a" i

    9 ^4 H2 x: x$ c& j0 M2 q2 \) Bpython
    $ N. d9 O! j) g) b2 I
    ! d" U  u/ s: {- w
    ( h3 F, y; y; B( D3 A# @3 idef fibonacci(n):
    . j/ b& `  t, ^/ v    # Base cases/ O0 w! E* A. i2 L# G( d2 [
        if n == 0:
    8 Y& B3 B& T) D4 b; S; U        return 0: A( j) h6 h3 L6 G; _8 p
        elif n == 1:3 i0 k9 D# P% H1 f
            return 1# I* K8 Q5 F0 O9 b/ J. r
        # Recursive case) Z8 U8 |- l" N+ |4 t/ Y* V
        else:% Z( R/ S& T  _1 A3 i1 Q7 N/ s
            return fibonacci(n - 1) + fibonacci(n - 2)
    1 Q' n2 `; d) |/ [) C1 f3 I0 o- M, Q8 g1 j/ O
    # Example usage9 x# p# C6 d. ~7 [
    print(fibonacci(6))  # Output: 8
    " P4 ~" n* g3 X7 o( V6 n/ p" C2 I+ s% Q
    Tail Recursion3 S0 K* ^9 z4 V6 _! I$ O) G
    - Y, p  y8 g5 g& u) |7 |/ Q
    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).% b# j- |% N5 i6 d0 M' r$ I
    " J4 ^9 U8 }5 n. k
    In 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-25 06:08 , Processed in 0.062556 second(s), 22 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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