设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 8 _9 F* K8 d& n8 `0 N  u  Z4 o
    7 s- V$ }8 _# v4 U# f3 U5 ], g
    解释的不错, s4 S1 X, o4 l9 J9 ?/ q

    + R# p. I+ T% j) b- B% A0 L! K递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。2 |: {  u4 g8 J4 j& k; U; X+ w

    / \5 k8 \. A/ O$ z8 _! e& e 关键要素/ t8 U- q/ G- Q3 Z8 P
    1. **基线条件(Base Case)**" A% `2 h* g4 [1 v, v* v7 P7 Q
       - 递归终止的条件,防止无限循环( C% w: C/ C5 M
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1" G6 C/ N: k  O% Q" `- d
    ( `& \# a1 c3 t) L) W
    2. **递归条件(Recursive Case)**2 q' i8 _: B: ~$ y
       - 将原问题分解为更小的子问题
    " `% y1 w1 g" J) q' H" B   - 例如:n! = n × (n-1)!
    0 t$ G4 L& E% `* O3 N& O: n9 v* B0 G0 y7 I' K8 x* X
    经典示例:计算阶乘) e6 L, J9 V7 d8 G
    python5 X  [5 S: L! F
    def factorial(n):: {* U2 C& _, N8 H9 W
        if n == 0:        # 基线条件0 h- [* r- E( e3 s2 Q( W
            return 1: }' P; j! T& M( X  O
        else:             # 递归条件: l/ }& E% k; Z5 m3 J* m
            return n * factorial(n-1)- U8 E% C+ P4 M5 V- b6 d) a
    执行过程(以计算 3! 为例):3 r, `* @1 r  @, M9 G
    factorial(3)
    4 z$ B! k* R  H5 t- l2 ^2 O3 * factorial(2)- y; H! ?: {( N/ h# |
    3 * (2 * factorial(1))( B+ }9 a  d2 l5 _
    3 * (2 * (1 * factorial(0)))
    . `  m/ M( ^6 p8 O) }3 * (2 * (1 * 1)) = 6
    ; |5 B: a9 C0 X# H7 `
    ! ?1 u- N0 w/ {% e: e 递归思维要点7 L9 Y$ O% R2 }$ U9 J" t2 M( C
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    $ G" ?4 R7 |: T% y2. **栈结构**:每次调用都会创建新的栈帧(内存空间)0 S/ m& v3 K6 F! F+ C! A
    3. **递推过程**:不断向下分解问题(递)3 S1 X7 e- T$ j+ Q6 b
    4. **回溯过程**:组合子问题结果返回(归)5 _' C) e4 `6 d' ?% A

    " |# J6 v' _1 r# r" V 注意事项
    3 z5 S; v2 F) c( e2 ]0 U必须要有终止条件& X. k1 o1 B8 _) w$ E- U% e5 `
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层), T1 v9 u$ I' j* H& o
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    4 W. x, a% _+ `* v8 I3 S8 g尾递归优化可以提升效率(但Python不支持)
    % T8 ^9 ^. H3 \5 O) V5 b
      Z' S$ y9 z/ q 递归 vs 迭代
    ( H% [) `' B1 F5 S8 y, n|          | 递归                          | 迭代               |+ r" j% E% S( H  A4 N
    |----------|-----------------------------|------------------|
    $ s9 ?% z/ `+ S2 L( U  f| 实现方式    | 函数自调用                        | 循环结构            |
    # w: x5 A3 s( y$ w| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |$ J: K* n0 w4 J5 j; H( b! x
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    5 s/ F' M2 D: S| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |% ?* v6 _+ q  n4 d% p4 z: _
    ; R) N9 Z% @9 \* L; K
    经典递归应用场景
    ; M9 q0 a/ @( d2 F1. 文件系统遍历(目录树结构)
    . z( I/ b# ]! w" B# C  \2. 快速排序/归并排序算法4 |0 G" z# b1 T' Q
    3. 汉诺塔问题8 i2 B& h/ E. Q0 B8 K
    4. 二叉树遍历(前序/中序/后序)4 y* i2 v: r# w( c  J' a' m
    5. 生成所有可能的组合(回溯算法)- \) s3 |( ~0 ]
    7 ~9 S, G. i& K. k% v% Z, ~. ~
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    慵懒
    昨天 09:20
  • 签到天数: 3234 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    7 h' s- X  V4 {( q我推理机的核心算法应该是二叉树遍历的变种。3 H1 W6 {3 Y$ l' z6 o* T
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:) _2 Q6 B# n) w$ Q- X' d' ~
    Key Idea of Recursion
    ) E' e2 x; O' c. ^9 O- f9 r& U$ ~; {- y3 Z9 D9 u7 J
    A recursive function solves a problem by:
    ) A7 s( V: s+ \0 j% b7 y; `$ N0 U" r
        Breaking the problem into smaller instances of the same problem.4 ~' L& |  \1 m, A1 g  O) i0 n

    5 T8 z& i( T1 s) W    Solving the smallest instance directly (base case).
    ; L/ {1 j  S3 G+ N# a
    7 `$ h8 p- Z' \6 [    Combining the results of smaller instances to solve the larger problem.0 f" M' w2 s( q3 v' U

    9 \, r# G+ {3 p. Q' o5 iComponents of a Recursive Function
    ( W$ f* g5 d- g9 d! N2 v3 G+ b, P
        Base Case:/ X) y: A8 C9 X0 R

    ; z: e$ v) u. c8 s& g        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    , p2 I/ M6 V" q, F+ \5 _4 j
    ) g' j7 n# T+ \! _- q/ j. x        It acts as the stopping condition to prevent infinite recursion.
    / Z6 J5 g  r; C
    7 m  W3 a: f3 a" [        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.+ R. i# Z0 K0 z1 C- Q9 {5 Q' r
      x/ a8 D) G; i
        Recursive Case:
    7 ~# H* ?# d+ G- q; P
    8 R9 F+ L( D* p; t2 M        This is where the function calls itself with a smaller or simpler version of the problem.& C9 q7 B% |: H; @7 X

    " R& ^; g( o- D9 u8 @* a6 Y* N        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    + r$ s% W: ~/ m' E9 \5 I. R+ }' O3 k0 q8 e6 c, `5 K
    Example: Factorial Calculation1 K9 P0 J3 w! B8 E3 M8 _
    ( ~1 F* }2 v% D: K
    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:
    0 W5 t6 t+ x, [: Q0 s( V$ J/ z% X3 t5 |5 O
        Base case: 0! = 1
    ( F- z0 j+ g# u" j& l9 {2 ^* S  \5 a0 k8 A9 b
        Recursive case: n! = n * (n-1)!, ~# t# d4 I" O& Z

    9 S! L  e; ~7 {6 E$ d& ?5 R4 |Here’s how it looks in code (Python):
    . K4 K- |5 S1 B: s8 m+ q5 Wpython
    ) W* u. D; q, |) Q0 v: n7 M$ ]' x1 S: u, [2 B1 ]

    2 @' x- Q  C8 o- o1 @def factorial(n):
    2 c7 j/ N9 ^! k3 D! a    # Base case
    7 {. h  w  n  ^0 \    if n == 0:2 T; d- [! G. V* \
            return 1. q% J: |6 h- _( m2 c. u
        # Recursive case
    2 d! P! N3 n3 m4 Q8 }    else:, \' u5 n8 y  |3 k  ?* D! n
            return n * factorial(n - 1)+ n; j5 N* r4 K1 }; R2 u4 C

    7 i) U9 D% k) l% R' a; |# Example usage
    1 q# u$ |( q7 ^! Z2 K' lprint(factorial(5))  # Output: 120  }4 g0 B* y, m$ \+ A- m) \. k
    ( R) J: i$ r2 s" H9 |- U8 C- L! r; f5 t
    How Recursion Works, N) {( g  ]0 I% b, ]0 o: U2 j

    - j  n2 x3 f, m4 f/ N    The function keeps calling itself with smaller inputs until it reaches the base case./ w  m+ t9 R( j& k9 z+ N1 v
      F; G7 [* I! I
        Once the base case is reached, the function starts returning values back up the call stack.
    8 W  x- e3 j4 f
    . \# c& T9 A- x    These returned values are combined to produce the final result.
    & ?9 G; \! k6 w
      h5 J3 A. X) Z+ H" u, y& W7 I* lFor factorial(5):* ?+ I6 @# r: ]" Z0 a. T

    ) ^% Y! F! ~+ X/ w( g: d
    7 C! e7 l7 D, z- ifactorial(5) = 5 * factorial(4)4 D2 m' w( B9 o' _* H
    factorial(4) = 4 * factorial(3)
    % Q% ~/ e2 V6 y) z* `1 B0 zfactorial(3) = 3 * factorial(2)$ T/ N, Y8 Q8 [/ W9 f
    factorial(2) = 2 * factorial(1)
    8 ~! B8 a$ P- Ffactorial(1) = 1 * factorial(0)3 Q& t" Z3 X& a# _8 D
    factorial(0) = 1  # Base case
    * R4 y) i7 ^' B. Z" r; G7 \6 @' R0 f2 p1 U5 p* p+ R
    Then, the results are combined:, q2 v" f$ h" y6 K

    0 U; q: }0 t- Y* [5 i7 A& f
    4 D7 Q. R2 q' n+ G' \& M$ E) w" Rfactorial(1) = 1 * 1 = 1
    3 H/ e) ]' B0 ?0 {factorial(2) = 2 * 1 = 2
    0 D: O" ~0 s  M; Nfactorial(3) = 3 * 2 = 6
    3 h- ]: v) B3 ?9 W: |! r% E$ ^) X" Kfactorial(4) = 4 * 6 = 24
    * C5 i  D3 A; f2 a& b6 ?factorial(5) = 5 * 24 = 120* C8 J( T; D- E1 l8 ]
    % M4 @  x; `- u. x9 G  ~5 m" R
    Advantages of Recursion
    . Y! d' C( S+ W) L
    * W" X# l- L5 ?    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).5 ?4 V& B7 @( T$ y7 o4 t
    % g# ]/ Q! V7 ~1 k
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    7 s( n# T+ u) n2 l' [' [
    ; e8 j/ {/ g$ p9 DDisadvantages of Recursion
    $ B, U( n- {/ t- o! r
    " r' q9 V% {3 B5 z/ }    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.. u( q. s$ ~! I/ n( M, C) l7 g, U

    , I" g) {! c- F- _1 x7 P    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).. G0 b$ `5 @: j5 _0 {# S1 V7 Y* d

    ! h8 N$ ?0 I) }, |- v1 `2 R. RWhen to Use Recursion: g( }8 R& \1 C9 S

    - V0 @8 b: [% R+ ]8 B4 l1 [& L8 B# A    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    & W& ~4 K) j; [: P4 x! G( k+ _7 i+ }  K
        Problems with a clear base case and recursive case.
    & P$ \  M$ I: E* R
      a/ k/ i' p2 J. ]0 U% T6 G8 u4 fExample: Fibonacci Sequence1 q0 }7 G" g! f) `0 L
    - u* m4 x3 q5 j  U; `' E
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:& q" Z# u1 v3 |7 f# y/ _! x

    7 c8 D" W) e: f& u    Base case: fib(0) = 0, fib(1) = 1% T1 {. B) u4 ^' x6 Y* Y

      U6 }/ o) V, J  v* J    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    2 ?- S7 O5 [: I. R1 S- o$ N3 f+ F! G. d7 q$ o
    python
      z- P2 a/ u( f0 v; E
    4 e! E6 Y; J- r8 r; [* k# l9 P* z8 l  k4 l: H/ ?3 t$ I
    def fibonacci(n):
    5 X. k2 G6 B2 ]  k% z    # Base cases" |% N" c& F; X$ x9 c8 ]
        if n == 0:
    6 b, j3 E6 s+ Z& ]        return 0, d  ]8 b  `/ u: j: J" \
        elif n == 1:
    : S- y  Y& g* r2 C( C% J, i3 e% U        return 1
    1 \- k# s3 f4 c8 h9 j" K    # Recursive case
    # o5 I3 t+ [2 @% T( N! H    else:$ |* V6 y5 Q7 P' m: X
            return fibonacci(n - 1) + fibonacci(n - 2)
    # R4 |& E( r* o. A* L3 l( \1 l' E" P3 @' r2 F7 y5 g4 {8 \2 T
    # Example usage
    5 e* V2 z) X. G4 e& `print(fibonacci(6))  # Output: 8" n' T( p# b' @/ _" c# _$ W
    ; E4 i: s. k  Z& h2 j( x
    Tail Recursion5 V: _# H, v9 Q+ J9 j3 }1 `
    7 y6 D* I% N7 Z  J6 s, M
    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).7 l# y) t2 h6 X  A* G
    1 c* e9 Z  S5 k$ k3 F4 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-5-9 11:40 , Processed in 0.059556 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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