设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 0 c6 f* t0 M% i! f
    ; X; i. N- Q3 g$ a8 Z( m2 Y
    解释的不错
    - a9 E- }( M- v4 i0 h, L+ A8 \" Q* D% C. j( m$ F7 a
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ( M$ W" i8 F/ w. m9 v4 i' ~$ J: m8 U- @
    关键要素
    1 M9 t+ y/ P, a% L1 M0 U2 `( N0 g1. **基线条件(Base Case)**
    1 u6 M" O+ W" e) s$ p   - 递归终止的条件,防止无限循环8 l# V7 M7 Z- i& H6 X  R
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    - [% d. R: e' i6 [: F- `
    ! g! g9 Q* L: M7 w2 |2. **递归条件(Recursive Case)**8 p& I5 O. `/ N0 c, G+ {
       - 将原问题分解为更小的子问题
      Z/ o' Y$ a  W4 z   - 例如:n! = n × (n-1)!
    ; F$ k& B1 W6 i
    9 u/ W; H) y0 K 经典示例:计算阶乘! ?& b: Y5 {+ i0 ~
    python
    7 W& e2 i7 }2 k* k8 @& Ddef factorial(n):2 y5 C, B% t# z  J* e
        if n == 0:        # 基线条件
    ) i. X0 p2 o9 f! b        return 1' ^' E; M/ V" G9 x/ T# x  B
        else:             # 递归条件
    & r; V+ ]# l) K( i2 m# C6 @        return n * factorial(n-1)
    9 }' R/ q" M, t& o执行过程(以计算 3! 为例):
    ( Z9 n4 X7 g' F$ Sfactorial(3)8 x: Q9 w1 u& \( _' U+ f
    3 * factorial(2), m8 N# c$ G1 A3 N! C
    3 * (2 * factorial(1))7 Q) [  {% `5 b3 i! V
    3 * (2 * (1 * factorial(0)))
    & S8 N  @- l# k1 I# h7 _3 * (2 * (1 * 1)) = 6# C% P1 r- ~! q) u, g# @

    , N  J. @3 K0 l" u/ R/ k# f 递归思维要点
    / Q0 v. C3 `8 E  s. x1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    - u' T+ U% K1 i: A. L0 a# h2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    , w  o2 l7 i( _- I% i# `2 ^7 ^$ A3. **递推过程**:不断向下分解问题(递)2 B2 Q) H, x; E( A, v
    4. **回溯过程**:组合子问题结果返回(归), B' f  o9 C' N, w

      c1 |3 U' A" C 注意事项" }+ H9 h3 Y. D
    必须要有终止条件
    , L4 a* f# @7 p5 y8 z递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    $ R% W2 z1 `+ v% m1 s* Q/ ]2 r某些问题用递归更直观(如树遍历),但效率可能不如迭代
    + N5 E; _; x3 x1 T5 `' w# x% y1 ~尾递归优化可以提升效率(但Python不支持)
    8 m" n4 ]* Z& E
    4 B7 G4 ]4 N9 N! [0 \7 J) |) |* C 递归 vs 迭代
    ( M3 k+ m" P  C|          | 递归                          | 迭代               |
    ! ^& Q6 Q2 m" f( ~; @6 v9 m+ q|----------|-----------------------------|------------------|
    8 ^6 Z' o8 ]+ L# [) _' {| 实现方式    | 函数自调用                        | 循环结构            |# B) n, L* y8 h% p6 T* F% ~
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    3 c% e; o8 L* @. I2 J" @% ]| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    & [+ y5 M2 h7 Q0 S| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    : W; T- q6 w+ u" S. c2 u& ?! d
    6 Q  k# ]$ l; G' H, q7 ]9 G$ s 经典递归应用场景
    6 x0 p- U* G" f) h3 e/ k; m+ j0 [1. 文件系统遍历(目录树结构)
    3 i5 _7 _; A* A9 J9 N% j2. 快速排序/归并排序算法6 y, {! S' }3 @' w  }4 O
    3. 汉诺塔问题
    8 o: m* W" e1 N$ O4. 二叉树遍历(前序/中序/后序)8 G; h+ n1 ]9 ]2 {& A$ |! r) ^
    5. 生成所有可能的组合(回溯算法)% W( T+ `/ X6 _6 W; _
    - N# t9 S4 P( Z' |
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    8 j5 F9 F0 H8 Y" w+ K8 ?) Z我推理机的核心算法应该是二叉树遍历的变种。, _  k2 t) L6 o, d- S) [
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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 Q* i2 H; Q4 j4 d' P0 iKey Idea of Recursion7 p* z0 y/ x- i; S
    2 V* a2 v& o5 o+ g# s' b
    A recursive function solves a problem by:
    1 [* m  K  ]5 V! g, d; a2 N
    " e7 F( @" r- C    Breaking the problem into smaller instances of the same problem.
    3 L; n$ t; |. a5 S3 @+ k1 o5 D& M" [- V0 X
        Solving the smallest instance directly (base case).
    8 ]9 ?) ~) V2 _5 C' C! |( Y  a+ E0 n/ E5 v7 ~4 E
        Combining the results of smaller instances to solve the larger problem.. x1 b8 P  H3 K2 O
    2 w3 [5 ?; K6 }# B! c4 _. _) ]! G$ j
    Components of a Recursive Function7 F8 e. s; N* }; t
    1 R0 a  z* Q; w# y! _5 v
        Base Case:4 p* N6 {3 I: x
    * d9 P9 n( d7 [+ {  P
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.& Z, Y/ P5 B* \; r$ k
    - Z' i0 o" j! d0 U5 q2 A9 Y
            It acts as the stopping condition to prevent infinite recursion.5 u. J/ t* x7 ^# n: ?

    + n; ]% L8 P# |, H& T! b        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.$ K$ h' d+ l( }0 T
    ( W2 O0 K; q3 |) X
        Recursive Case:! l7 F/ R" ]( ~  t
    ) {0 a1 v8 \4 ~! G# O9 Q
            This is where the function calls itself with a smaller or simpler version of the problem./ U% E) Y- H, N+ b6 i" [
    3 y4 b; V$ @! G+ }
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    ( t! X- |! R8 y. S
    0 V+ w  b8 U) k! N* EExample: Factorial Calculation
    % v% P0 {( ~+ p, X
    " E# ~6 `/ ^/ t. B6 }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:
    : A2 J" Q( h0 l* |
    " u  ?  t. `. z8 O. s  D8 R    Base case: 0! = 1
    9 ]) P/ I3 p3 F2 C
    & z$ r# F3 q$ b  G0 |! \! ?, N/ }    Recursive case: n! = n * (n-1)!7 i4 _8 M; R+ q" a% [& p

    7 J+ X! }; R: q& pHere’s how it looks in code (Python):
    * j2 I' T4 g+ q! p) T3 z5 j( o+ w9 ?python
    9 N. N, r% R  K4 @7 s. R
    # v3 V4 W) a! u5 m8 Y. A; _8 S3 E0 D
    + V: d  R! ]4 ^/ e# K* _3 l% Adef factorial(n):
    % p1 J  k5 `, m% U% n+ ?    # Base case. [5 V5 w. ^  s/ ]$ A7 i. n
        if n == 0:! E! m6 G9 g7 \
            return 14 t- y3 S* {) |6 L6 D
        # Recursive case
    & y& u0 \8 `2 V, \- e! q& Q5 Z6 X, g    else:/ A! r. D) B, r. V
            return n * factorial(n - 1)1 h& k, Z9 K+ X" g, v
    3 Y, \: m1 h2 Y# @% s
    # Example usage- I" o; @1 i9 Q5 \7 v
    print(factorial(5))  # Output: 120
    ! t5 v6 v, l/ R# U; J6 l" y& v  x4 N; R# R$ W) R
    How Recursion Works
    1 F( s; T6 m: \
    9 j! c. b; O' O8 B$ G3 @    The function keeps calling itself with smaller inputs until it reaches the base case.
    % u2 `2 N3 O9 I& e" o' r( W
    / \/ T+ v  _9 ?' b: Q: S  E    Once the base case is reached, the function starts returning values back up the call stack.
    # ], @# C% ~0 H
    # k! @  i8 j4 }  `  z: |/ g  {    These returned values are combined to produce the final result.
    9 j$ c& A' L6 E- m1 G- N; r4 Y/ o$ i+ C3 S6 V2 r
    For factorial(5):
    7 u' A0 E" ?( S: c1 I% H4 C9 H; d$ P' y. {

    5 b  }& u& i: |* y9 xfactorial(5) = 5 * factorial(4)8 X2 |" E( A- ~# f% k7 ?4 A# {
    factorial(4) = 4 * factorial(3)8 q4 ~+ k& F, [/ O1 I* k$ k" ]
    factorial(3) = 3 * factorial(2)
    5 R5 Z" V) |  X1 ^0 F. I6 d9 l' kfactorial(2) = 2 * factorial(1)
    ; \1 }# L' P. V, U( \' ^factorial(1) = 1 * factorial(0)5 {: s% m! m. K" |& w/ \* r& S& p! {
    factorial(0) = 1  # Base case4 ^( I9 r& @9 Z0 G% j2 ]; |
    # q' s/ i. y3 o* e& a! _6 f
    Then, the results are combined:2 h4 h. L0 ~( L$ G8 y' N
    . K0 \! }; T% R, c0 ?4 P' ]. P7 b) L
    7 M3 Y9 u" Q; `! e$ V
    factorial(1) = 1 * 1 = 1
    ( P+ R2 F6 t. A) @6 Mfactorial(2) = 2 * 1 = 29 y/ x$ J1 {7 ?# p" L1 M6 l6 g8 q
    factorial(3) = 3 * 2 = 65 {/ ]1 @5 [' U$ g8 @) A  p5 e
    factorial(4) = 4 * 6 = 24
    % V7 M" n( j% z6 x1 Sfactorial(5) = 5 * 24 = 120/ O) W. O+ b9 W
    6 M1 \  C5 [: }% C8 c% q- Z5 _
    Advantages of Recursion# p/ B; o( s8 [$ F/ M; B

    1 Z( w5 s. v! t. u4 D+ [    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).$ A* \2 @7 a) R8 Y# g5 \6 V4 {) \

    & I6 `% U0 `) |    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    $ @0 K0 e" _7 N$ W" k# K
    ' U9 O* ~5 E. N) S+ W% ^, hDisadvantages of Recursion
    5 j& E2 {+ @2 i& O0 Y8 P
    ) S5 g4 Q  {3 l4 P    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.
    ) M3 z- Z" Y  X! q9 f$ t" p2 l4 e+ U; L1 ~
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).' Z8 y& R( [7 |0 R- R

    ! n- U/ X" q4 |4 G( n9 d% lWhen to Use Recursion' G8 i# U: A+ r

    6 k6 m8 `5 Y; o' m    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).. X& r+ N' I; O; n& Q
    & x% Y/ ^+ s7 ]" S" S4 v: D
        Problems with a clear base case and recursive case.
    # S! W$ E! s" `& W  F
    7 t( [0 _* _+ W  \. [' r1 jExample: Fibonacci Sequence: H+ ~9 ?) M' j, {0 l* ]
    " {! i" I6 K7 C- y6 R7 z* D
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    " h) ?: O$ M; K) e' G
    + O; a4 z1 l2 ?. h* S, H, l6 U% w    Base case: fib(0) = 0, fib(1) = 1
    1 N1 [1 h, I$ m3 p" z" q: `4 k/ B0 F' s4 S
        Recursive case: fib(n) = fib(n-1) + fib(n-2)9 U+ J! T) q. r9 g& v( D, `

    6 p+ i2 R# U, s+ B* npython
    ( C3 r) Y3 V3 O! S0 a$ X/ T$ p/ f  V3 ]. H4 [  \5 o5 ?
    ' E9 v$ f/ I# m  R9 e# b' L
    def fibonacci(n):$ t/ S, R7 L0 E6 P8 i- ~
        # Base cases
    # `: c, T7 m& I. W  u0 r    if n == 0:6 s' T2 S( B8 h$ f8 E+ }
            return 0  P3 C. {8 i7 Z; g9 L
        elif n == 1:$ K0 Z/ V+ Y6 R
            return 1
    ) S/ M2 A$ y' Y- T# [    # Recursive case! g+ `+ D# b# u, @
        else:
    & @6 d+ ~. U5 ]% L        return fibonacci(n - 1) + fibonacci(n - 2)
    2 r2 M2 }/ N8 _% R0 _6 Y. n
    " A% A# K  Y3 C' y# F. g/ d! `# Example usage
    ; T! D9 D1 y: s9 E  _4 Bprint(fibonacci(6))  # Output: 8/ b1 n2 V& d& Z( Z% A8 U/ x$ n
    6 j; ]& A+ P' b3 B& q
    Tail Recursion
    . d9 r4 u  T* M5 J5 H1 ^7 U" _* o9 t! c) y
    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).
    : \' \+ W, Y- Z5 F3 P" i& H& b
    9 Z( x! j# x/ eIn 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-10 18:09 , Processed in 0.032040 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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