设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    5 j& B! Q) B$ g
    ! ^: d  e+ e, t4 N解释的不错
    ' n4 |% M) s( P7 l8 Q, h3 z% `9 T) Q9 l
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    * y( S- F: L( p. p  r2 T* Q5 q: R, X4 H( d" I
    关键要素  [" V" L- x) A+ ^# F# i7 L
    1. **基线条件(Base Case)**4 E4 I: S8 U$ r2 q
       - 递归终止的条件,防止无限循环* {+ k+ V- C* ^1 O* y$ s2 w0 E% E: ~
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 11 B- C" M7 V2 E8 Q' k- |0 \
    / o" R2 i2 S3 d
    2. **递归条件(Recursive Case)**
    / Z9 z% S# f/ J8 |4 [   - 将原问题分解为更小的子问题% R* q% A  c" \; o. L3 p
       - 例如:n! = n × (n-1)!
    ) G( N' t* Y- R6 u, b- M3 ^! Y/ v3 t5 A
    经典示例:计算阶乘
    & I. Q1 e7 W, a5 D$ }# S* |" T* Kpython
    / H! ^, J1 V8 `* A! K0 ]; Zdef factorial(n):
    0 H2 P! n% @3 l% N    if n == 0:        # 基线条件
    3 w2 B# x* |* J: s1 W: _9 B        return 10 n3 a+ G6 J/ M2 ?. o
        else:             # 递归条件
    3 `1 D9 U5 z/ L2 G        return n * factorial(n-1)
    : F& D; v# y# _6 q0 Z. s6 o* r执行过程(以计算 3! 为例):3 c. y0 v9 X/ h9 z6 q
    factorial(3)+ @9 l+ F  Y. W) |# K
    3 * factorial(2)$ v, U/ M5 c+ D4 l0 a, i' V
    3 * (2 * factorial(1))$ n0 C  N/ h  M4 h" U4 W6 A
    3 * (2 * (1 * factorial(0)))
    " a4 _, Y% K) ~: ?3 * (2 * (1 * 1)) = 6
    3 ^. t, Y" i$ n" x: J) {9 V; `$ {1 a, I8 _7 L, K# M4 A) ~
    递归思维要点/ P) u7 O  `0 N5 Q6 \* e
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ; G/ g& _) j$ K: Q7 b# Q2. **栈结构**:每次调用都会创建新的栈帧(内存空间)* R  l% ], w1 r
    3. **递推过程**:不断向下分解问题(递)
    ' Q7 j- G# B6 ?# E* ]4. **回溯过程**:组合子问题结果返回(归)% s* s3 q' K! ~7 @8 G7 \
    / b2 c  X& g4 E! J
    注意事项
    " C4 g8 ~8 a. A- v3 _必须要有终止条件5 }1 z3 b2 e5 |3 p6 {+ f
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)6 s2 L6 q1 b4 n5 s3 D
    某些问题用递归更直观(如树遍历),但效率可能不如迭代  e% r3 f1 X$ c; |0 @
    尾递归优化可以提升效率(但Python不支持)
    % O5 z: d  C1 r7 L! d* p: G1 |, c* q1 F
    递归 vs 迭代" B1 ?( s# ~, t" O
    |          | 递归                          | 迭代               |( ^5 o+ P8 m- R) T3 q2 |
    |----------|-----------------------------|------------------|* O$ d2 i7 a0 A2 |% K/ w
    | 实现方式    | 函数自调用                        | 循环结构            |
    1 y7 ^2 d4 d# `| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |0 B* U# p2 o; x* J
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    : `! P# z9 F4 t; X! X' U' }: \| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |1 _/ ?3 x  Z# C0 l2 o$ g
    $ z1 S( l- ^3 Q
    经典递归应用场景* L8 b+ ^+ `/ ^: z2 p7 Y3 U+ Q6 T
    1. 文件系统遍历(目录树结构)6 q7 q* [% S9 K. x# Y: V
    2. 快速排序/归并排序算法6 ^( O5 |3 f1 {' a! U# a
    3. 汉诺塔问题4 o1 V3 B+ P) @+ ]
    4. 二叉树遍历(前序/中序/后序)
    ) ?4 k( r( a( p1 i0 D4 g0 j5. 生成所有可能的组合(回溯算法)0 A& d4 ~3 q  j& {' u

    0 p$ L6 F/ m$ A/ h试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    擦汗
    昨天 06:41
  • 签到天数: 3102 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    # d3 b* q4 B- X9 f我推理机的核心算法应该是二叉树遍历的变种。6 Q0 j6 B  q+ Y
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:) w) H  f9 K$ P  [+ o4 S
    Key Idea of Recursion( T, C" f8 l( K3 @

    : h3 x& H# X% [+ ]" xA recursive function solves a problem by:  I2 C8 t3 c8 A
    * ~) Y8 _! U- Y, J% |
        Breaking the problem into smaller instances of the same problem., o- Z0 O9 [# c4 n2 h9 ?
    - H; [: r+ A+ d8 c) k
        Solving the smallest instance directly (base case).7 C( n) [0 J" f5 p
    , D: [4 k6 x# b4 c
        Combining the results of smaller instances to solve the larger problem.' q! B# k* @0 G1 ?. z
    1 |& A* k& l! \9 T/ q% C
    Components of a Recursive Function3 D; h* {/ V( C5 L' W

    % D* w0 [3 L" @/ c  Y; X1 ^) m    Base Case:
    7 c* F4 d1 y0 [8 L. z& }0 [7 s7 M- X6 |: T8 u8 s
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.1 R- J, j6 \. D+ e. U1 J+ L
    ! @$ a# ], z, c5 o0 V% B
            It acts as the stopping condition to prevent infinite recursion.
    6 X, d9 l0 `2 r* g# x6 p) B3 C& U6 }# s( g3 N. I9 a. F
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    / g% Q7 H* d6 E+ x( O9 Z  v  r) G& ?. l5 g
        Recursive Case:' F5 Y) i( f4 n* i
    + a. Z0 u$ t. |. o6 P+ y7 I
            This is where the function calls itself with a smaller or simpler version of the problem.. {/ N, e# ~" V) |8 u5 ^

    ' _/ p0 n/ ^& n1 N: o        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).' {! h9 E5 y, s( K
    ( r/ n0 v- E- s4 x2 e" ]
    Example: Factorial Calculation3 i5 G7 M3 x) L: T& ?5 i  m
    6 B; x8 S* _5 ]: Z& a+ E6 l, b
    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 n9 _6 k1 Q3 e- O2 [. F  u
    6 b- K, f# M  V6 S4 v0 P
        Base case: 0! = 1" T  G5 {3 p" U! Z# t0 ]

    9 K1 W5 [$ b- C( X6 b1 i    Recursive case: n! = n * (n-1)!* Q! }# C: H  j1 n# p! Z) ?+ }

    " G$ @% `  i- B' s+ U6 H3 [! ?Here’s how it looks in code (Python):3 ~; Q' m. n3 n
    python" _8 M5 V+ p) m8 p! K

    2 N; ~, b0 g4 R' u
    + ?* u9 p( ~& t& A8 K! I' {def factorial(n):
    ) _5 ?( i+ r( T' z0 `5 M% f1 p* v* j    # Base case/ W! U6 P: z) L' C5 c/ C1 s
        if n == 0:- h4 `0 L% Y5 F
            return 1* [( u; t' L1 c; Z0 }" M
        # Recursive case3 c# A# T  b" [
        else:" _$ F3 D7 q5 {
            return n * factorial(n - 1)
    5 ~9 K/ I/ f" @  O* l  h8 ]+ Y% U, P8 Z4 O* Z
    # Example usage
    3 N# f* P7 P% r% s, k9 wprint(factorial(5))  # Output: 120( d& e  g4 w7 ^
    ' O: {. a9 D2 N. u6 _
    How Recursion Works
    " ]$ ]( t- t9 }: O: O
    ' h4 d, b6 V# V' a; R* h: {' y2 j    The function keeps calling itself with smaller inputs until it reaches the base case.6 L, z- v- d. O
    9 ^- N) W, v0 h$ ]9 x3 T+ u
        Once the base case is reached, the function starts returning values back up the call stack.- Q* k, B6 t' F' b6 O
    & \" r; O0 j0 Q$ q& K0 t
        These returned values are combined to produce the final result.
    * c  t( M/ c, o) b" n1 ^- F/ H1 k; j, [
    For factorial(5):
    + ^7 W  r$ x7 U$ |& {/ i
    7 `0 k: b8 U  I9 ^* H) j+ r  K. N% E( I% G6 C4 e' t
    factorial(5) = 5 * factorial(4)8 F/ T7 o, g: H% s8 U" X
    factorial(4) = 4 * factorial(3)
    ( G/ A( F5 `1 x9 V3 C" {* Tfactorial(3) = 3 * factorial(2), n6 i. l' ]( E+ ?
    factorial(2) = 2 * factorial(1)
    3 ?2 p  b# Y: R: }factorial(1) = 1 * factorial(0)
    4 M" V2 a' ?* l& [! Wfactorial(0) = 1  # Base case( T: W- R6 J8 s0 {, K* ?

    ! M/ X1 i* w, n; d( uThen, the results are combined:# V- m$ e6 w% e% e6 F0 Z+ r; B. S

    7 C/ d+ ^+ L7 U: ~% Z& @5 m+ L6 L# m; _$ o
    factorial(1) = 1 * 1 = 1
    ! y6 P- g  _5 z- |3 V5 Yfactorial(2) = 2 * 1 = 2
    & p+ y0 n3 G9 z' N8 x3 S8 [factorial(3) = 3 * 2 = 6' ~) D' r8 [+ \' a: B' \
    factorial(4) = 4 * 6 = 24
    ( U+ h* ~( s+ x6 i5 H$ B: k+ D2 Cfactorial(5) = 5 * 24 = 1206 H" l$ i( W5 [+ `* O. q9 Q
    # a* |9 O/ q1 h" m
    Advantages of Recursion
    3 f* t- e7 L4 L7 f! h& f5 P2 p. Z( [2 Q
        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).4 H' n& X: s9 l

    * ^' g* |: p. \; F- q- O6 V    Readability: Recursive code can be more readable and concise compared to iterative solutions.! T6 V3 N* H2 P  h2 \
    4 E+ i& q2 V" }# E' f; F( e; [$ M/ [
    Disadvantages of Recursion4 r; W& a2 ?: F3 b" N; {. {' x
    3 v# S% h5 O& ?# j% e2 Q' a
        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.- S9 G* {3 l2 I  C& U

    1 K- f% G5 A0 `. k( ^6 U    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    9 y9 T* o/ o) h: V; a7 A) b! C
    2 b* q0 f  k1 Y5 F8 S: q1 FWhen to Use Recursion
    * P( ]2 ]" C1 w! K4 s/ ]% g8 r+ Y5 c3 I" N# E8 y+ x$ U" j
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort)., M$ ?$ S+ ]1 S3 T

    $ e' G% l& e( q+ K7 w- F' W# B    Problems with a clear base case and recursive case.
    0 N7 i2 D* e6 I0 g  i
    " [" Y# s+ ~# y# H; X1 h2 p& p* KExample: Fibonacci Sequence$ L7 x! W5 {' R6 C0 |0 X8 i3 j
    ) ^3 Y4 D2 o' a, z, |# H
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:. X6 J; W% w! a$ r, c* q
    ! A$ @' P# }" n. R
        Base case: fib(0) = 0, fib(1) = 1
    8 m- x$ c# y( S0 F6 S) i. [% j3 Z1 j2 j% N3 A" }  V$ U5 ~1 c
        Recursive case: fib(n) = fib(n-1) + fib(n-2)& `% }% e4 Y" y( ]9 c$ @4 ?1 ]" c! s
    : l: l# J) o$ A. g
    python9 l; @8 |4 J. s; D/ d) _

    $ r" _* R' P# U* m2 S8 M
    + @; I4 f7 S, S: d& l& Ydef fibonacci(n):/ B& `' q, E7 X8 j6 [, Y
        # Base cases# x( y3 H$ u! z7 M" @
        if n == 0:
    0 k! n/ ?9 N" x) i: B+ C3 ]        return 0
    & U; V7 k7 I1 z4 F' Y* ?    elif n == 1:1 H9 w3 o) R/ l" P3 P& k1 B
            return 1/ T3 k5 b% @& R4 G
        # Recursive case+ y& j+ I& t' B
        else:
    7 R. S' Y5 f- Y3 H* t0 ?' ^5 A        return fibonacci(n - 1) + fibonacci(n - 2)( ?" C% E( ~& _- C/ M$ \0 |  W

    6 {4 a" k4 E3 a3 S) H* Y# Example usage
    - B& A( W- r4 A/ Q! }% {5 Q4 u) Xprint(fibonacci(6))  # Output: 8
      m) D5 S" ?  v4 ?( t& O
    & I* R5 ?# _4 T/ NTail Recursion
    * F: t: H; ^5 _# `
    , e" W1 O+ V% o/ W& H( ZTail 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).
    " `& F% ]/ Z4 h2 \0 O
    8 m7 L( j$ a; b, h# uIn 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-11-27 20:08 , Processed in 0.031948 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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