设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    - d- d( [) }- |% p3 Q
    " s/ `( ~7 T  L4 f$ k解释的不错
    + _* |" w; }8 Q8 \. ?: W8 L7 q+ E3 C" F
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    % S  ]0 T$ P( g- s; ~% M# c- Z* H
    关键要素: D( G% m) |, p
    1. **基线条件(Base Case)**0 @. q; v1 M; E2 B" Q3 Y
       - 递归终止的条件,防止无限循环
    . ]+ i' O7 p% H$ z, M- d6 |8 o) v   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1  U) [% S  @6 M6 G2 g/ i4 ?

    ) d4 c& U& V0 ?/ y) F2. **递归条件(Recursive Case)**
    2 Y% B( D, ^5 c% A   - 将原问题分解为更小的子问题
    0 p9 _- u  Q: e3 _( y   - 例如:n! = n × (n-1)!# [9 s) U$ K' s7 b1 x7 J

    8 n/ \4 D, r0 i' u1 t! k$ j9 ?& T& S 经典示例:计算阶乘. ~: Q+ L: ^% o
    python
    ' c% e3 p( _" O& d9 odef factorial(n):
    2 i% z* ?4 F. U. n; @" d) ~7 H    if n == 0:        # 基线条件
    ' j0 J, c. J  v1 U: t" h; f2 j        return 1
    # O: b' }; K. r    else:             # 递归条件
    2 Q* i0 G) ?% D/ U5 ~- L        return n * factorial(n-1)
    ; M& P. [( [( G# H6 C6 R( ?执行过程(以计算 3! 为例):
    " s) ]% H1 S# d3 A" N0 O5 ]# Bfactorial(3)- F( y7 q4 w) @9 _0 ~3 F
    3 * factorial(2)7 Y% |- S. C  r7 }* Q0 N' }
    3 * (2 * factorial(1))# E: ^* A  m% w
    3 * (2 * (1 * factorial(0)))
    ) B+ E. `9 \/ z" h3 * (2 * (1 * 1)) = 6
    , |  c2 C$ s& q8 f# g
    3 `! Q- H! O" K; p9 p; Q 递归思维要点. p3 g# J3 q6 t7 ~, }' y/ T& n, T3 Y# y/ s
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑8 S$ ^; X: W6 c  ~1 p5 a* V/ [
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    & o' N: ^; z) N3 ~3. **递推过程**:不断向下分解问题(递): @" Z" @/ {- G7 W& B+ Q
    4. **回溯过程**:组合子问题结果返回(归)
    ! P. n, e# @6 y) b) d* H
    0 P& |9 p/ M" w# q( w 注意事项
    , @% i( C/ I: ]# ~0 ?) E* g3 l必须要有终止条件. F9 Q* V7 W. J+ I' K
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    0 h( Y# S! W2 [, G* ~/ z某些问题用递归更直观(如树遍历),但效率可能不如迭代
    1 [5 M5 G5 |- ~+ x  J尾递归优化可以提升效率(但Python不支持)0 L  F9 \: m. v8 [4 u/ f8 u3 `& N0 X

    5 s4 \0 L% @/ x- J9 w 递归 vs 迭代7 t' d7 u  ?$ \+ r; m3 h2 x
    |          | 递归                          | 迭代               |
    ( Y4 `( E8 @8 G; ]|----------|-----------------------------|------------------|1 m) E. H! D% z, j/ u- }9 g! y! w
    | 实现方式    | 函数自调用                        | 循环结构            |, q$ |' c+ w( t; w( z' x; {' N
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    8 p$ J7 [8 `- M( L  U4 p; E| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |% Q2 @( X3 b3 w. [% H3 ~& Q
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    7 f) ?5 ^( Y  `" @6 Y$ g; \0 c
    ' ?: g3 K: e6 b$ z7 k; Z3 b. D 经典递归应用场景- Q+ J+ }6 U$ x: q3 z' |; N* I
    1. 文件系统遍历(目录树结构)
    % ]0 L4 t1 a: M( ]  K2. 快速排序/归并排序算法9 e& Y$ _& \: x' X1 }
    3. 汉诺塔问题2 T' \7 o! M& g2 M+ `: \* J  O" g
    4. 二叉树遍历(前序/中序/后序)3 Y. _& @4 |' y! n
    5. 生成所有可能的组合(回溯算法)
    7 ]5 N! ?3 ~2 o- ]! R
    4 x3 h- w; ~1 P! c& z* {! `& [试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    昨天 07:26
  • 签到天数: 3158 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,' @3 F; O% _. [9 V6 F
    我推理机的核心算法应该是二叉树遍历的变种。
    6 L8 ]1 h! b! b+ ~另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:: k- p1 t' d, H7 w% ?& @
    Key Idea of Recursion
    : l* ?3 v5 `( @5 X' Y
    ( `) k; `7 c8 _; ]$ [( G5 zA recursive function solves a problem by:5 z% w: T  a& w$ v, u; _  }* a
    ; ~( L3 W! s- ~
        Breaking the problem into smaller instances of the same problem.
    - ?1 _/ u3 S% |: {; m+ J3 p& Q2 _! b6 v5 K! J7 K
        Solving the smallest instance directly (base case).# \. @! J( v6 T+ P

    ( ?0 U4 Y* u0 d& {    Combining the results of smaller instances to solve the larger problem.1 ~! l; L* ?2 F& D6 F, t  b+ z5 v
    5 a: j- x/ S. ]; B: w8 u( ~/ n
    Components of a Recursive Function
    . i/ f; N$ J( d7 |5 S4 t# t) t; \  @3 S; P
        Base Case:
    3 @1 L( Q1 S% k. M  \
    4 x' _8 O7 a* \0 Y, m7 D4 o" z        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.# y( G# S7 r1 G+ M, w

    " R' X& i  j9 }. g* J* A: l" j$ h2 i        It acts as the stopping condition to prevent infinite recursion.$ M7 c5 K" C+ w" V( q" p
    % |5 {9 E5 \" |7 s0 U- _
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    # X9 {3 g  f+ A0 e, C
      t# \' }+ L5 f, g* C( K' o    Recursive Case:
    / }( g4 [$ k* g. O) z# W! d) O- l9 K; L  w; d6 c- Z
            This is where the function calls itself with a smaller or simpler version of the problem.
    , l: j- \' G( h5 c4 }4 J  j  Q: I; h2 O" i1 F& r% d, I
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    - h$ Z; T) t$ C. \
    8 S+ t$ _5 C; }9 B1 D1 r& f4 RExample: Factorial Calculation
      z. p6 ^" W( F9 p. s+ K5 e7 b& r' X* o% G3 ~4 j
    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:
    + Z+ b3 g2 O1 H4 ^2 m8 ]
    3 G/ V8 u0 N! ]& p9 p    Base case: 0! = 1% I6 G1 k. q% u: K# @
    ! t5 p! F% C1 ^% S: [0 Z
        Recursive case: n! = n * (n-1)!
    0 P0 H; f$ x& @9 G5 U4 B* d! b* {
    4 v: p# C5 Y+ q, A9 J. tHere’s how it looks in code (Python):# p. |8 A% L8 E8 O* d! c0 R, ]
    python* v4 i, l1 U8 v' \

    0 u+ j) i1 s! @0 Q5 J0 F) r4 X: b# t4 m0 `
    def factorial(n):1 B! I# w: [6 n5 z6 m$ A
        # Base case; n, H# S5 U1 q) z- O6 _
        if n == 0:
    8 P, a" b# g0 r1 \& m        return 1
    5 l3 [8 n: q  L- A    # Recursive case
    / c- R$ x+ N- M; [    else:
    - F+ N( _2 ~* `* f/ R# }7 G2 ?; X1 S        return n * factorial(n - 1)
    $ V/ f* S  @0 U5 u/ N6 N
    4 z, p# X4 \+ Y9 |- R0 s. ^6 c6 a# p# Example usage
    4 X% l1 ~8 G; Iprint(factorial(5))  # Output: 120& @) A6 M8 o/ d4 Z) _/ o; d
    , r% J. o: i7 l" X4 b$ m
    How Recursion Works
    5 d. z, V) l6 j' L' V( ?
    ; E& |4 `" K) {    The function keeps calling itself with smaller inputs until it reaches the base case.4 q! f+ F9 y5 c" ]- z1 u+ z

    ( I) `+ J# H( p) y9 r' h" s    Once the base case is reached, the function starts returning values back up the call stack.. n( g0 {" h! m; Z3 Y8 n
    / K! G: l) k+ |8 i
        These returned values are combined to produce the final result.' U; M3 m" T5 F, C9 H6 n

    8 r. x& F! K. y1 J9 M1 h, zFor factorial(5):' u; s, t! L3 u) w, {# _5 }
    + R+ m% P% K& `+ H$ G

    1 K' l& q  Y7 P: f! v5 Jfactorial(5) = 5 * factorial(4)
    . q" Y& u( D3 {7 `/ Q+ Pfactorial(4) = 4 * factorial(3)/ G+ {  n  x) @$ {$ s5 Z* U- L
    factorial(3) = 3 * factorial(2)1 v/ N5 F4 j) D
    factorial(2) = 2 * factorial(1), w  U, F7 S; m+ Z
    factorial(1) = 1 * factorial(0)
    1 ], T; @- L9 ^factorial(0) = 1  # Base case/ o' @: E  n- [
    ( K4 i" Y: L& K1 A7 ]/ k
    Then, the results are combined:( j' P/ \2 B' [1 N2 i  t

    # _9 k1 w8 Z7 G6 I& E
    9 Z8 h4 p2 B* l" t$ j5 {factorial(1) = 1 * 1 = 1
      b9 m/ q- F* @" Q4 hfactorial(2) = 2 * 1 = 21 {8 ?& b1 `& j
    factorial(3) = 3 * 2 = 6
    8 y" I1 |7 s9 J$ Zfactorial(4) = 4 * 6 = 24
    1 Q" w2 T( {2 C8 nfactorial(5) = 5 * 24 = 120
    - ]7 v* \! o& ]. A) v* \6 G* F% F& L7 W1 l+ M9 A6 U; @
    Advantages of Recursion
    $ t' S) n7 u- V& I' P! z. r1 f, w7 Y8 @
        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).' i* Z3 ]8 R0 X. `" {9 b
    * t4 ]3 y/ i3 y- ^/ J$ l$ b9 x
        Readability: Recursive code can be more readable and concise compared to iterative solutions.! n5 y+ A) A6 p8 @+ v
    - r7 K/ `3 `3 Z( E% Q7 I6 k
    Disadvantages of Recursion  F% x1 @2 V& T
    1 l# S' _8 s4 q+ F" F9 R
        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.# y9 |1 i0 A. C4 y

    ; c1 @7 A) I9 ]6 c& z2 J0 D' C, Z    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    , d' `, D* u. w1 K0 Y7 v* H3 s( [6 w
    5 y3 s: U& z/ o3 hWhen to Use Recursion
    1 Q5 {+ P( @* {  b7 D2 W; p0 N7 m$ g% @; q* X& @
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).3 B* |# u: x: ?' f% {9 B

    " |5 M! b. K, `% e$ J7 f3 B    Problems with a clear base case and recursive case.! q* U, c7 k1 X$ `
      Q) @0 R' p6 L0 a# ^4 n9 k( p
    Example: Fibonacci Sequence
    9 Y. N2 j' i$ z; j
    ) G9 s- n! ^6 l0 aThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:. \; k* ?! m4 r  b( {) P
    - @: |- d: w: X# l; Y
        Base case: fib(0) = 0, fib(1) = 1$ S+ m9 b8 T, A# F" h
    7 g& R! f: M$ w' ^0 u% X7 v7 P
        Recursive case: fib(n) = fib(n-1) + fib(n-2)! g. R8 t! r# a
    # h/ |9 A' R: x
    python) W, y0 u/ W1 }

    ( V: W* t& n9 x9 H0 u
    " @( ?0 q9 `! G* X) p4 ^1 v' r, Xdef fibonacci(n):4 j9 F- ]9 p, s- r. b
        # Base cases
    - b" u+ k& L7 G/ ?    if n == 0:  w% R: q0 t; I: D4 ?; [8 ?% Z7 M
            return 0
    2 p: X- ~- Z! x8 |* S9 C    elif n == 1:4 O, X( `+ w$ `# u: v* _
            return 1
    & }6 t. s7 r6 @& w6 X; F1 O" z1 V    # Recursive case! ]4 j  v" O- \4 S) o' M: N  ^
        else:
    2 A3 R6 y. m. x2 c        return fibonacci(n - 1) + fibonacci(n - 2)
    2 D5 J. F$ L2 j2 T2 _% G' [  L
    4 j" `: g9 N6 a8 X7 l# Example usage% r3 K2 X6 D0 l, O8 P
    print(fibonacci(6))  # Output: 8
    , f2 F  M1 p8 Q( P' P8 r# M7 E8 f3 ^% Z# r6 j6 _- B, P9 _2 R/ N; n
    Tail Recursion% i4 d+ h! K0 a% L" ?0 S' z
    . A, c9 G: {3 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).! y, D0 ?! {& }. T, `3 D5 p1 h4 r

    4 `: ^3 E/ Z* Z$ @9 WIn 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-31 01:37 , Processed in 0.057760 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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