设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ; V' {# C0 G8 d1 M- a
    5 `6 l9 s; |! h7 ^; o+ w" a* Z解释的不错
    ' ^( o& _( ^: B( r1 \! C# G2 \
    ) ?; K8 W9 D' _; U% \8 F递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    . [4 ]% [) {9 b- W1 @; p- _& ~3 s- Y8 y# u: o- C1 n( M6 T. H
    关键要素0 w* _" h  I8 Y5 D1 f
    1. **基线条件(Base Case)**9 x2 A/ u# g3 h
       - 递归终止的条件,防止无限循环
    0 P" D! {/ R4 v" U4 f/ R! c   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 16 k$ F) F5 x0 C) N3 I9 [
    % d! q6 \; J7 B0 a" n3 m0 q3 F
    2. **递归条件(Recursive Case)**
    , j" e  n+ C: l$ q& L; w  q   - 将原问题分解为更小的子问题
    . [! q8 Y( [8 y) M" m1 W   - 例如:n! = n × (n-1)!7 {/ _  r3 d2 |8 s/ {  }
    1 d, F% B( F/ ~3 A# H, I1 g# V* L
    经典示例:计算阶乘2 h6 r" S+ ]. f( n: ]# K
    python5 V5 w( ~0 y& g2 T" o5 ]
    def factorial(n):
    4 `& ^4 T$ H8 b( K2 u5 c/ |! b    if n == 0:        # 基线条件
    % b7 g" x% o; D7 d- ]& y        return 19 l# z5 o+ W  A0 Z
        else:             # 递归条件
    : S0 S1 u4 I  E9 J4 P        return n * factorial(n-1)9 h2 F3 y' V( s8 P: u6 k3 e
    执行过程(以计算 3! 为例):, Y/ z3 L9 M4 |& F; \* H
    factorial(3)
    # N7 v1 E" |& s3 * factorial(2)
    . [$ T$ L2 v. F6 Q8 Q3 b  n8 M8 Y1 L  w& ?3 * (2 * factorial(1))
    . O1 {5 G/ Z) I3 * (2 * (1 * factorial(0)))
    . U+ _# L9 l+ z& v  C, V- U3 * (2 * (1 * 1)) = 6
    ! i5 b$ m  q. X5 x1 l, V+ j* @9 `/ F& B+ e8 U1 X) z$ E- W/ {
    递归思维要点
    8 u. R3 ?% u: s. C$ e$ v1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    1 V6 E# g/ @7 F, X2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    1 g) p+ l$ `# p, g; {9 n4 z3. **递推过程**:不断向下分解问题(递)8 i# v, W1 R! q9 J* b
    4. **回溯过程**:组合子问题结果返回(归)5 m- K. C7 B/ L& d: G

    / a6 b" `; q4 P3 v: e* {2 ` 注意事项
    # T( C% A% C7 f2 q必须要有终止条件* \$ k( F# q, u7 T
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)5 x' A& p1 K$ Y& e
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    ; L+ H& K3 N# u9 }$ p尾递归优化可以提升效率(但Python不支持)% e6 ?2 m8 P. y' g8 x2 O( j( L
    ; k" V) [; V) m0 w1 w/ n
    递归 vs 迭代
    * P6 ^! j6 v/ d5 L8 H2 [|          | 递归                          | 迭代               |, w# N' t+ v9 C1 m
    |----------|-----------------------------|------------------|
    3 ?9 Z; x4 ~. c' Y1 P2 @2 P4 |2 g| 实现方式    | 函数自调用                        | 循环结构            |3 @8 ]- n, ?( W/ g8 k
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ( G+ Q7 |- h( D$ p, e- {; D8 \| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    1 z  K# V3 o: U# ~! F9 K3 M  \| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    / i1 ]3 M1 q. \2 ]2 I
    * E( M& T+ m. N* l 经典递归应用场景
    - U! R: Y' }5 E$ w! T% S- b2 [1. 文件系统遍历(目录树结构)2 r8 Y2 g' K" n; Q6 m1 ?$ y7 r/ ?
    2. 快速排序/归并排序算法
    , n( m% |! v& Q, V0 G3. 汉诺塔问题* l' d5 I( F' u4 v: S& h+ Q5 g5 N# @
    4. 二叉树遍历(前序/中序/后序)
    ( G4 a0 a# A$ w1 M5. 生成所有可能的组合(回溯算法)
    4 ~; p' K3 _( f: p  a9 E& ]: K# H0 k  s; b4 E, h+ r
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,3 c0 \9 L7 K( s4 U3 A
    我推理机的核心算法应该是二叉树遍历的变种。
    4 h# K% H3 f. d' l0 c/ M. J' 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:" Q) ?+ u, T1 H. c3 j: Y8 j; s
    Key Idea of Recursion( Q' w  ~2 z& \  Z& ^' Q

    + E, H* n! F2 m! M( R+ g$ V4 G) hA recursive function solves a problem by:6 g6 d9 g1 ?. V; c

    ! w6 v* p4 Z% y0 j: F    Breaking the problem into smaller instances of the same problem.
    ; h7 `, z5 Z3 H- y: a5 H' ]3 u; [( g9 K0 B' t& d3 E& ?7 {
        Solving the smallest instance directly (base case).
    ( l' I. B  Q  I4 P/ u2 r9 D9 _7 b
        Combining the results of smaller instances to solve the larger problem.
    / r/ W- b# x$ T
    : v% q6 K* U8 U3 d( {' LComponents of a Recursive Function# \8 x, _; r2 j1 m

    ' X1 f3 I& t- \" D7 d7 x# q$ L    Base Case:( Z2 J  D1 ?  |) C, W4 d) N, c5 [3 {

    . O5 c* Z* H0 Z: r; o3 U        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    8 @! d8 D( L6 N6 q$ }5 p! B: H9 D( ?0 r: M' ^
            It acts as the stopping condition to prevent infinite recursion.
    ' f6 A% |6 I2 |. i2 X  \& O0 p3 Y& x1 K$ v' C8 O" ?
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    / q0 d7 T9 K4 J5 g3 `% I$ h* F" T  z8 l8 n4 ]( p) i9 j! Q
        Recursive Case:
    : y: m9 {. \* J  }2 y# r7 I. I7 q  }' A/ n
            This is where the function calls itself with a smaller or simpler version of the problem.
    ' L: k" j3 o$ q" z) G
    7 \: G1 Q' a1 R3 R        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1)., p8 I; a$ q2 [4 b# l* I
    5 e8 Z' i/ M" i" \# ?
    Example: Factorial Calculation. V3 g  w' m" _$ Q5 D5 g
    ) B' t1 o. ~" z( e$ }( L" G6 d
    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:: q6 o( [2 J$ P: l! N

    / d( Y- i) @- Q: e6 F% J5 n    Base case: 0! = 1
    , s0 \) {' `$ V8 V; k! A
    8 `# D+ i* }" b' M" D2 P* ^4 A    Recursive case: n! = n * (n-1)!2 P( a; S- ^* U6 `6 o) j5 I# g& l
    + f+ A0 L' F# b; x3 U0 J! ~2 I$ |
    Here’s how it looks in code (Python):
    # u0 L) g, s6 L3 H, v0 g; x$ Hpython9 d" L) M7 N) n+ P/ ?. k
    5 s9 P7 H$ [- d0 k5 \0 l
    : n# D; Q8 S! M- W+ w' n* [. j
    def factorial(n):
    ) H; C  f9 Q" p; T: V+ r1 L7 |    # Base case
    8 y. Y7 ^9 k% \# H" P0 O    if n == 0:
    * ]$ ]' m' ?' R: x5 w( v! Z' j! P        return 1
    7 g$ Y2 W, B" ^6 P0 {: W& }. N1 f    # Recursive case
    ( Y6 ^% p5 Q7 E7 O: e6 a    else:# s. q, ^. h/ W; t+ x# C
            return n * factorial(n - 1)
    4 T+ i; _9 f' B# P4 N
    7 W, s0 F3 f4 V+ e1 s+ h) u# Example usage
    8 p( n, ~( F9 h* jprint(factorial(5))  # Output: 120
    : ~9 ^: a1 d3 W1 S- P- U, q; }( F' M0 k) ?# L" ]( N
    How Recursion Works. o, }& U0 _- {3 T  l

    / ]# v" h1 k, Y7 S  A% d* g% J    The function keeps calling itself with smaller inputs until it reaches the base case.8 X, g8 y9 t; r6 f

    / j6 O* t9 l7 ^) I8 Q5 \    Once the base case is reached, the function starts returning values back up the call stack.
      i; e0 Q; y2 k4 f8 c' W
    ( Y- U% j! ]9 Y; t3 v5 I9 j    These returned values are combined to produce the final result.
    # j% f" A+ G# z7 W+ n. C' y6 m: o$ J; {
    For factorial(5):
    4 w, j) ]; @- d0 c8 E3 ^. v: I/ j
    ; j: M0 |+ V3 b1 ~# l& Z4 z
    % c- i9 }; ?2 s4 I3 f, ~) u2 Kfactorial(5) = 5 * factorial(4)
    9 @  k0 m( e: D- l. T8 ?factorial(4) = 4 * factorial(3)( J3 D/ a- i4 R2 F( H, M# }
    factorial(3) = 3 * factorial(2)
    . `& I  K8 D: {1 p2 o4 Lfactorial(2) = 2 * factorial(1)
    8 n. x# U# c  U' R3 q9 tfactorial(1) = 1 * factorial(0)1 c4 |' ]4 f8 J  n! f
    factorial(0) = 1  # Base case" j+ A' J& D1 A6 x3 k8 ~& E
    / V& }4 e2 t% E6 G
    Then, the results are combined:
    + X3 o9 Z5 D# F0 R* c
    * h  U+ d! _7 R* h5 A7 x) O/ |% \% S5 X& k0 h4 y" k
    factorial(1) = 1 * 1 = 10 _, X5 j9 t  j, [4 s; s- [7 o
    factorial(2) = 2 * 1 = 2
    * w/ _: v  `; m% u; {0 Qfactorial(3) = 3 * 2 = 6# q% X! }& s0 E$ c1 q9 {
    factorial(4) = 4 * 6 = 24" C$ @+ @0 n3 Y% y0 U2 q8 m, j3 L
    factorial(5) = 5 * 24 = 120
    ) Q: }! l+ ?- H
    6 D( [. V/ }0 g+ n$ s( Y; \# g; `; f9 s/ `Advantages of Recursion+ e7 ^! R# z( J! c) T9 d

    ) [/ j+ b, o# X/ P  X, 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).
    1 ^8 R- N2 Y; F# T8 N, y
      h; j7 i& ^" [1 ?( w  s    Readability: Recursive code can be more readable and concise compared to iterative solutions.  v+ ?9 R4 N1 e+ p  x

    , m& S* A" O- @& I3 j; B) ADisadvantages of Recursion) Q' x& Z! v! v7 r* s1 s( J6 c

    2 e" d; H4 [4 s% s    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.
    8 _( f) n, ^! c' A  A; Y, p
    9 l2 f/ n+ t6 d4 s7 a    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).$ i; _' ?0 }8 J/ `* s. B
    / {* k$ }- }, I' W0 e
    When to Use Recursion& {( i8 y  B& ]8 k8 [$ Y
    9 D+ S2 U' g  E6 N: ^
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    / [! b+ B, U" ]5 v
    9 L7 b2 Q. q1 a1 y    Problems with a clear base case and recursive case.
    + r8 o0 R- i+ {; a8 }5 Z% j  h& P, p, |& J
    Example: Fibonacci Sequence
    + F$ U. q" i: W0 k) A4 x( P4 R7 {' t0 o0 i6 u+ W3 c
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
      w1 z+ ]' l2 ?+ R/ h3 `) f/ i0 U& F- y
    . O6 g% m1 Y7 N    Base case: fib(0) = 0, fib(1) = 1$ c: l1 {1 k: H3 l

    " G7 I$ C/ H& ^8 W6 B) U; W    Recursive case: fib(n) = fib(n-1) + fib(n-2)" e" i" b9 [) Q  q( F4 x
    7 z# Y! {( W2 q. _) v7 ]
    python
    % m$ E4 K% F+ A/ D8 ]; }$ ^
    $ ?9 R. P. X% y& u' @9 ]
    ; i( `6 U- `; w3 ~& l% Edef fibonacci(n):" c$ N2 p9 P* U3 x
        # Base cases
    8 `! @/ V2 A" f* N5 k2 C( Y    if n == 0:: q8 g5 E# K( ?0 ~2 H1 P, S
            return 0. j! b1 O3 ^! y# c4 e+ r& y' G5 K  [
        elif n == 1:  y) a, I* C, @" l# |% w: f
            return 1* ^2 E/ @" c& l% Z3 I
        # Recursive case
    % N5 n% {! Z$ f- w& t2 P7 w7 u    else:
    2 `7 I! H# q* ?( f* {/ f/ @+ j4 _        return fibonacci(n - 1) + fibonacci(n - 2)/ x- I* P$ [- t7 x
    + Q+ C5 e! x. H) V: O
    # Example usage
    0 I, w. j9 o6 K" m, B% Tprint(fibonacci(6))  # Output: 87 H% h7 C2 K4 }: D: _1 e/ w

    $ E/ Q+ u- j. ~. G; V( s4 X% B, PTail Recursion
    2 b! G( X; {) Y0 c& Q" n3 f
    & y9 v, F. [* ]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).8 A9 a: R4 U1 u! y
    $ ~+ _. V- O0 l, [9 N, N5 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, 2026-1-28 22:07 , Processed in 0.058509 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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