设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ( D. |' T8 H. Z9 |4 w+ [$ `+ m+ j
    5 W8 m1 b3 A8 e) i解释的不错
    7 ~4 L0 P7 `: @( d
    , e( X1 t) E+ Q# D  y, N4 g递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。( P% W3 n+ \% x4 _
    ) v# t. J& D% f( J  f, J5 d; k
    关键要素
    8 `# Y/ c$ B0 q, u5 s" D: K1. **基线条件(Base Case)**0 P+ ^) h6 J9 p  f) N$ D
       - 递归终止的条件,防止无限循环- {0 O- A  S" M/ ^4 H
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    . o. @$ P2 W4 N3 ^0 C' J" M. n1 y6 ^' m6 u
    2. **递归条件(Recursive Case)**+ B+ A% K5 o/ E$ p3 ]# D' K7 B; ?5 D
       - 将原问题分解为更小的子问题
    . r! k3 x( h+ s8 M; {   - 例如:n! = n × (n-1)!
    ! C9 A3 g5 L# x. E
    % ^! x/ {% |* d6 ^8 h' x 经典示例:计算阶乘
    ; w; k9 u! b0 G# M3 vpython0 p, q  R5 V  I  Q
    def factorial(n):
    3 R" [& R, h+ o) Y    if n == 0:        # 基线条件( j, s" {. a' z9 F
            return 10 ~# q' O+ \. X! a
        else:             # 递归条件2 d. |$ g" o3 E9 p0 O
            return n * factorial(n-1)5 _: W* f; l0 q6 x
    执行过程(以计算 3! 为例):
    0 L1 j! F$ [3 N" O! ]* e. t! xfactorial(3)
    - q3 J% F: V3 j* [3 * factorial(2)
    * h" Q1 r1 N4 q9 Q3 * (2 * factorial(1))
    ) r" U9 ?7 T. I5 e% A& x+ x3 * (2 * (1 * factorial(0)))- W' |" m2 u/ f0 s: y* R
    3 * (2 * (1 * 1)) = 6
    ; z8 x7 Z8 y. X4 q7 E1 J
    4 l) @) v4 A! G: {4 D! \/ n 递归思维要点- r1 Q( C" [1 ?, }$ F. o
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    / i+ X% _4 j+ z5 @8 Q2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    2 c! }- G0 f1 A* Q1 I0 h* [! t& @3. **递推过程**:不断向下分解问题(递)' ~$ L# t# j$ P( H; X) q
    4. **回溯过程**:组合子问题结果返回(归)( D+ F% N% X) I3 X/ |% q( f* E3 h! K# A# ]

    $ V# t8 K! i' Z; C 注意事项
    1 u- w. f2 r* X必须要有终止条件
    6 K( g5 p- o8 ^; ?* O递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    5 |7 M, h& Y5 k! L某些问题用递归更直观(如树遍历),但效率可能不如迭代
    / u/ c/ y$ J: m  e: Q尾递归优化可以提升效率(但Python不支持)2 Q* i% X; S/ H

    , z" m( ]2 W2 I. n 递归 vs 迭代
    " ], e' n1 s$ A% b|          | 递归                          | 迭代               |
    7 U1 {# l" K* H) K  g1 c* ~3 g|----------|-----------------------------|------------------|
    ) p" |2 c3 d' o) E, x| 实现方式    | 函数自调用                        | 循环结构            |3 N& P7 G$ d7 Z/ g/ P8 `
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ( L# z* @% |0 I0 m+ b2 F6 M| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |. ~# [( Y$ `9 {' {
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    ! ?2 V5 B5 u0 H1 h; G6 P, ]
    0 x* @6 A, G+ \# S7 f2 e6 i2 I4 h 经典递归应用场景
    7 z( r( `- ?" p1. 文件系统遍历(目录树结构)' I+ N- q) \; z! C6 g/ f7 P) O
    2. 快速排序/归并排序算法
    ! ?0 C* ?6 z' {6 y2 C3. 汉诺塔问题
    * L+ L! m0 J/ m/ i' y) J6 q4. 二叉树遍历(前序/中序/后序)
    / h+ T( E( w9 v0 q2 o4 r. f0 ?5. 生成所有可能的组合(回溯算法)
    % S, T' u9 C7 n* {: L# A# _
    & R- C; d1 A5 m) \  V, p  \1 v$ K试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,' }9 _5 M$ U! x, F
    我推理机的核心算法应该是二叉树遍历的变种。
    " ~, N% |' F+ g" A" _0 B8 U' G9 @另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    * E# h, B9 k1 DKey Idea of Recursion
    # @' O9 a. o2 n1 f+ ^+ g' [: p  D$ P4 U# @6 P& R% B
    A recursive function solves a problem by:
    & s4 k) E( e. m- _7 e0 P$ D
    / F/ k, G5 P' B: ]5 m% t, Z    Breaking the problem into smaller instances of the same problem.; K0 m* ~0 d! a1 q6 ?( k& y% T

    8 I# S6 e3 I/ s3 {; [# j    Solving the smallest instance directly (base case).
    8 s" I9 o0 z; @6 v: S: j
    1 W1 c+ |+ Z: |( N    Combining the results of smaller instances to solve the larger problem.
    $ v+ G" A8 \+ N" X/ m  _+ R# k) D9 M3 q
    Components of a Recursive Function2 [: d% F, M  i: ]) d

    9 i% q1 o- [7 ?. D    Base Case:
      R; A0 @4 U5 \  ?, B. }" e1 b: J/ q& i0 O7 Y+ k) @9 R! H
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.6 I# r: `, {" p/ F/ R7 N6 B8 R
    / L5 K$ v  l2 e/ W6 Z, q: o
            It acts as the stopping condition to prevent infinite recursion.
    3 s5 _: T, z: b  }3 m. y' t6 e
    * w% X/ x. J2 B( V" n! [5 Y% \        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    : ?2 R: S" _# G8 \& `2 c/ I' f; P4 T; |2 v6 v
        Recursive Case:
    . b$ \/ J* V) e* T9 L$ B9 X
      K- S7 K' _( @& R! J4 _0 S        This is where the function calls itself with a smaller or simpler version of the problem.- r8 }3 ?4 M' W) J

    " [& l. w3 a3 p& C2 S        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    * z( Q" @8 \# n- ~2 ~# W7 \# {
    5 t: G' J# g" }9 Y. HExample: Factorial Calculation
    # m; W$ j( {) v- G4 @
    : I4 Q/ P1 e6 _, P$ lThe 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:, Y/ F) r0 F( @) v  _- L3 I

    9 R* k, x7 ]% A2 T4 ]    Base case: 0! = 1, O: W+ ]9 y4 S& ?6 X7 C# M
    / Z. T( F1 w& M: S
        Recursive case: n! = n * (n-1)!- q' {# p! W8 {/ ?# x! n

    - d) j9 |5 u# A+ q- c: MHere’s how it looks in code (Python):
    ) u2 D% g' l; u/ r+ w7 a4 t7 w" Y1 ypython9 c2 Z- Z; Q! o" ~& f" T! s
    9 n- i& a; r7 Y3 O( t' l' ]

    2 r' G: R6 L4 edef factorial(n):4 p' I* A9 s: h) U; [( z
        # Base case2 o9 g* \! V* `. |' B
        if n == 0:
    . U: ]0 ~) c/ e# U# c" R. K( V. I        return 1
    ; Q' z! j+ F% a9 d* Q& D5 ~    # Recursive case$ S& @/ |: G8 S9 M
        else:
    1 O9 c4 e9 C! y        return n * factorial(n - 1)
    - f* `# d: p8 q1 N8 J0 H9 v2 @+ m! i1 D) m
    # Example usage
    & a7 U7 E9 b, G( A6 ?' Jprint(factorial(5))  # Output: 120
    / l, i& j9 z4 K3 Q9 L
      |/ }. m  V; L5 ~# FHow Recursion Works' h0 r+ q; E  p% S1 v

    + m- j" t. G" D    The function keeps calling itself with smaller inputs until it reaches the base case.6 b+ m5 F+ I  p* Q* R- E$ Q1 M

    ; X+ B! g) ]( S$ T3 ?    Once the base case is reached, the function starts returning values back up the call stack.
    8 _% J4 Z9 a) r6 ?1 o1 Y- `+ E. K) N1 H2 r
        These returned values are combined to produce the final result.' F7 [6 f& s' V
    " X4 [3 D. T3 T$ L3 _. u, c7 [
    For factorial(5):
    5 U* }8 j# V  N* l+ j, ^! o5 J) X) a

    . r' P/ a7 N) w/ E5 ?) Jfactorial(5) = 5 * factorial(4)
    ! d. A5 ^9 V8 m2 ]factorial(4) = 4 * factorial(3), j% ?( o3 x; A
    factorial(3) = 3 * factorial(2)) L9 X7 A6 E( V2 N4 \: ~
    factorial(2) = 2 * factorial(1)
    0 C2 o8 u+ r8 X6 y5 l2 Pfactorial(1) = 1 * factorial(0)
    $ u9 N3 }, H8 Jfactorial(0) = 1  # Base case
    4 R0 t9 w0 S4 d: t8 V$ f
    7 ]% ~$ u0 j! O  p, hThen, the results are combined:5 P9 S) m! N- ]+ G6 h
    ( N6 ?3 d' W0 ?+ Y0 T

    2 k9 t$ C1 u( B, q1 R! c5 Jfactorial(1) = 1 * 1 = 1% ?! P- e, y  a- W# u
    factorial(2) = 2 * 1 = 22 @5 ^1 F% V3 P8 e0 Z
    factorial(3) = 3 * 2 = 6( r9 `7 s0 [' o
    factorial(4) = 4 * 6 = 244 G/ J  O( I9 J& e/ J/ V
    factorial(5) = 5 * 24 = 120
    - E* |. K5 h- U) C7 o- j$ B) T0 u7 X+ u6 I
    Advantages of Recursion" ~3 y0 d( E: ]! v6 \; b4 c; w: |/ y
    & F0 }4 B& i* x0 ~7 \& \  x' M! e  a
        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).: y2 Z; D* c4 q3 s! d( {* W$ [

    $ m, ?! [. D; O: j: {    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    # B" u$ }4 e1 }& I; ]5 Y
    , e) L  ?. x, o9 Y. _Disadvantages of Recursion
    $ a4 R2 }2 z# w8 {( L
    ( `* M% H) Z5 g    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.
    * G9 ~' s* y' V$ {
    1 S* [9 }# q+ S! [    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).) V8 i1 L9 u  i, T3 t

    5 S2 P3 r# g6 ?- C! CWhen to Use Recursion
    6 D" N6 \0 B4 t" O& Q" q4 }5 u  O
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).7 I6 E8 q: ?: G4 n. [2 `: r5 J
    / K& C# {7 z$ R4 X' P
        Problems with a clear base case and recursive case.9 d; p& u- p3 k4 P

    - A) P% c% {' _0 P& S* oExample: Fibonacci Sequence9 @1 f7 a- }: W( m3 j6 a- j, D) Z

    4 ?/ d- A4 D# {. E* Z9 qThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    ' d( Q$ s* C9 j6 q
    ! C7 Y% Z6 {) T# {    Base case: fib(0) = 0, fib(1) = 1
    * Y' Z9 A; _" N3 Z5 {& z3 q" J5 t3 g' C, @& s
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    5 z2 P. i" g, H& g
    ; r8 u' A2 H8 H; g3 D  gpython
    % K3 ?" b9 h, [. \4 F
    7 w$ Q0 W# D% h+ o; I
    : N  T3 ^4 m& m% e) odef fibonacci(n):
    / z6 Q5 M& t- y6 c* I) L    # Base cases
    6 V4 r1 D' K0 ]( j. C5 L$ I2 o    if n == 0:
    , ^- [. O1 j0 n1 f: z        return 0
    / }' p' ^- W( w& S, y9 @& U+ s    elif n == 1:
    ' K2 b+ R  r0 z! o- a! g0 I        return 1
    ( k! v! y/ T$ n    # Recursive case8 h5 V0 ^! g6 j' G: K. u
        else:
    3 v# c/ G1 G. D& H        return fibonacci(n - 1) + fibonacci(n - 2)2 \% W' L$ l  s5 W5 d, u
    1 h& Y8 _, g9 h% i" G
    # Example usage( d2 X1 m) R! d* _+ T" r
    print(fibonacci(6))  # Output: 84 g0 S/ d9 j' H5 @7 A' p
    ; j5 R- A* M3 s3 V8 k+ {
    Tail Recursion
    - z  C; D5 ]1 k7 J/ r
      O( [0 D2 Q( v1 S* YTail 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).$ X' M- y9 g# x. L
    5 d' v6 p* M0 U; K. g
    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, 2025-12-8 12:10 , Processed in 0.037015 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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