设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    9 l- p1 D9 l; p% }0 ~1 J, O( t
      ^) p, u& D# @0 S4 x# d解释的不错1 `( `% `" ^% O( P! G+ H

    $ C# t2 A. B* q7 |9 f递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    / m( v2 I: W( M. P0 Z& t
    7 A$ M7 G0 h1 t9 P% u2 e 关键要素5 x3 U* K) l7 R. r
    1. **基线条件(Base Case)**
    9 v2 s5 X8 u) ?# t8 o   - 递归终止的条件,防止无限循环0 \% s3 u; I, |0 W  M
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1( V' k4 _; n9 f# h6 u

    # Z, F0 F; E  r' u2. **递归条件(Recursive Case)**! q4 C& ]+ f0 M6 V, P8 k; G
       - 将原问题分解为更小的子问题
    ) e' r7 `: a% L0 n* }: k9 L   - 例如:n! = n × (n-1)!8 V% o: \& M  p% I
    $ X' N  K; s+ `5 s$ n6 W! p
    经典示例:计算阶乘" q# P( M. A$ G# K" e3 x3 _0 t
    python% @; }; |/ _5 W% Y
    def factorial(n):
    0 U4 F9 @" ?1 x0 o: ]/ M* Q& {5 s    if n == 0:        # 基线条件2 v! C$ O. P4 K' N* O
            return 12 U' _6 c' `; l
        else:             # 递归条件7 [3 V( j! a! d/ L, Z
            return n * factorial(n-1)3 U" g0 s6 m  B7 h" o
    执行过程(以计算 3! 为例):3 {/ ]2 E5 ?; E6 P+ n9 q- Y# [
    factorial(3); F5 w, I  r  g" ]
    3 * factorial(2)
    ; y$ |& }7 N9 I2 R3 * (2 * factorial(1))  ]) l! z: Q3 i% [0 S9 V
    3 * (2 * (1 * factorial(0)))
    + o: `4 S" r4 s2 L1 `3 * (2 * (1 * 1)) = 6
    7 l$ y. X4 L2 f; t/ t8 V
    5 L- e+ v: _% c' b$ L/ h* \ 递归思维要点& \4 N4 J  t8 ^. |( w4 f
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑4 g& \- Z! k# m
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间). C- R2 o9 V9 Q( F0 {1 j* M& Z
    3. **递推过程**:不断向下分解问题(递)% X; }! }$ p" S! I9 c4 X
    4. **回溯过程**:组合子问题结果返回(归)
    / Y# e! v$ K7 T3 O6 E: k9 l. a; {% j
    . w7 D( G2 V/ {. Z3 P0 n- @5 J3 D 注意事项
    ; c( E- N* E, `# t" }, m必须要有终止条件
    ! p: |# U; }- v& W+ L: {8 y7 ?递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    # ~; `. U* N* u' R# D! ]  D某些问题用递归更直观(如树遍历),但效率可能不如迭代4 p# m' V6 B# a* A+ W0 t7 U
    尾递归优化可以提升效率(但Python不支持)
    ; P4 I7 m% V; ~# w; n" d$ H  x3 a5 w* {/ Z
    递归 vs 迭代
    : R: y5 N& C' n$ K|          | 递归                          | 迭代               |6 g" n5 m4 Q) _6 q9 ^
    |----------|-----------------------------|------------------|
    & _" H6 @/ m- u; i* ?| 实现方式    | 函数自调用                        | 循环结构            |
    5 h7 m+ K5 t1 ]" v( |, k1 |9 B| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ) j1 E4 m5 Y( h1 I- J! S( p| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ! x5 k3 w7 [* O6 B| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    3 v5 ^+ k; O( A- ~8 H% W3 W+ _2 m4 i+ a: e
    经典递归应用场景- P% s' E4 |! |1 v  h" N7 Q3 B
    1. 文件系统遍历(目录树结构)
    " b) a/ p) ]6 G5 C2. 快速排序/归并排序算法4 g/ u* |0 m7 z4 C; t$ t& |
    3. 汉诺塔问题
    1 c! v+ e, l+ |3 j) J7 a4. 二叉树遍历(前序/中序/后序)
    * ]4 s$ O/ Q9 U+ r2 j' V  R9 j5. 生成所有可能的组合(回溯算法)
    6 Z9 t' }% x1 C7 s7 n9 X% b
    9 X+ y9 E6 D2 h4 {, [( K6 ]试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    12 小时前
  • 签到天数: 3244 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,+ h9 @1 a3 U, K6 g( i5 [
    我推理机的核心算法应该是二叉树遍历的变种。
    " |3 F' F9 p6 d* s) L6 p, {# X另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:4 m7 d' U( C4 y, ~* T* |/ }
    Key Idea of Recursion
    + W  s% d0 X* y. p7 H/ A' ~4 c, ?; {' B) ]
    A recursive function solves a problem by:. h. E& Z8 Z9 k0 H$ e3 r- s/ B* `: _( }
    : Y3 L$ z4 R* m  X& r
        Breaking the problem into smaller instances of the same problem.7 e5 P' K& f: h, O8 S
    ) N$ o4 }' M' O" C/ R
        Solving the smallest instance directly (base case).
      J& }% O5 `9 W) R* ~$ L; y' t- r- p# d/ U
        Combining the results of smaller instances to solve the larger problem.7 g/ ^4 J3 S! h) f
    ; d+ W( l+ B& G1 V  U( i
    Components of a Recursive Function0 R. B$ _8 v/ R' @
    . [) D! z2 S% C! a5 H/ |
        Base Case:4 _( l7 w2 A. q; L
    - i6 G& d) {/ y2 g+ O, N
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion./ L+ ]2 q& p9 Y$ v( d$ x
    ' I5 T, u4 A& b/ ?0 N
            It acts as the stopping condition to prevent infinite recursion.
    + q: e7 C4 N4 f) i9 |2 H5 o5 o, F- B
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.' q7 H# j, R( g' ?: E* u

    2 ]* f! Y# y. C/ I2 C2 r1 \9 W    Recursive Case:8 K8 y- {9 C7 i/ ^3 Z
    " [) v: @! G0 F9 ^
            This is where the function calls itself with a smaller or simpler version of the problem.
    + `2 ]' v" u* p& _7 @  _$ `' r" G! F. P8 D) k: p# k/ }
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).. f/ R7 i  m* T* N

    2 _: u& I3 ^( D* h  Z; q, |" O" VExample: Factorial Calculation! D  r" t0 j6 k) |. L. d' T
      [7 Y$ {7 i! F5 f: c
    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:. q( i; b/ V9 Y& X# L2 c' }
    ' e! G1 t4 X, Y' V1 S2 W
        Base case: 0! = 1
    9 `, q$ V# T8 F$ t4 D
    % n; G: x1 u' Q  X    Recursive case: n! = n * (n-1)!
    # N" v4 [  D9 r
    % {. n" i4 c8 ?5 P2 MHere’s how it looks in code (Python):
    / O5 I' Y2 a5 g6 tpython, i" i; |+ O& b( K! d) Z5 b
    . B. m* l3 G9 r* _6 k* S# {* Q. u7 _

    3 s  ^3 c2 s: p. M$ Sdef factorial(n):
    - H; k) D3 _% E- f7 h, w7 D    # Base case
    5 {% C- a7 O5 X9 `3 {2 Q) a    if n == 0:
    1 d: v  V# x: J  C# |        return 1- \5 m2 y; t- f6 d, |! H5 i1 J
        # Recursive case8 {" E! M! J' y; r
        else:9 i5 ^( F2 c, f
            return n * factorial(n - 1)7 l6 Y0 D' B% q! [# }
    ' Y/ D/ {) O, F, a
    # Example usage
    2 y$ @2 O7 T" c9 Hprint(factorial(5))  # Output: 120* Z, m  v- f; b+ f! |9 _; t
    ' s6 x: T$ R6 \* A  C* D
    How Recursion Works
    ( |! w8 G9 @$ U
    9 _- F+ }. l1 U2 x7 P    The function keeps calling itself with smaller inputs until it reaches the base case.& z1 J0 F# ^4 m. E
    1 v$ i. _) O4 F. P. U/ C5 t4 E# V
        Once the base case is reached, the function starts returning values back up the call stack.
    ( K0 @* }* E+ j: j9 c$ |/ \" R. U' C7 ~7 \3 O/ \4 a3 R5 r
        These returned values are combined to produce the final result.
    & z* s9 @  K% z9 h  G0 d1 z3 L; l' F  l* W6 q8 e; Q
    For factorial(5):
    6 c8 A, k6 J3 t# ?, ?) \9 E  t3 R: D, W+ }, r
    8 e- r# v8 y; m8 X0 B8 E
    factorial(5) = 5 * factorial(4)
    7 z0 R1 S+ d, c. ~; Tfactorial(4) = 4 * factorial(3)
    1 D' @5 p. _1 {2 D% W7 R5 ~factorial(3) = 3 * factorial(2)
    # E7 b8 t$ R  W; H. p9 b; ~5 q( |factorial(2) = 2 * factorial(1)
    & R6 \" W9 P& |6 r5 Y, Lfactorial(1) = 1 * factorial(0)
    : P& |" F  x" _6 rfactorial(0) = 1  # Base case
    6 s4 o- S4 T& j- O0 ^
    9 T% l0 A6 k/ C9 R9 M  z  C4 BThen, the results are combined:& u0 C' h2 @& I7 L
    . R/ m$ J3 N# h% Y3 d: |6 I2 x& |

    ' R( y) e# B# ^! L+ [- s# t2 y1 zfactorial(1) = 1 * 1 = 18 N2 N$ F$ n3 f# D9 |% G
    factorial(2) = 2 * 1 = 2; W* O! w) h* A  W# B, H. I
    factorial(3) = 3 * 2 = 63 g6 _! J4 J( |$ ]* a
    factorial(4) = 4 * 6 = 242 n$ V4 U% }& i# r/ [* b8 E% u. b5 R
    factorial(5) = 5 * 24 = 120
    ' g8 C" y/ w0 f! E5 r
    * d- G) ]. ~9 q8 F+ F0 |5 d9 VAdvantages of Recursion7 _; t+ a7 k6 f  C$ t! k
    ' g  {2 q# h4 L; C
        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).
    ( ^* @- r1 a% M: o! s9 Q" |4 |5 Y' w- O; U, p
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    & o/ a4 y  [& G4 f: I/ k- j
    # n4 @+ w  @7 h1 Q: {; N. Z/ s: }% B! NDisadvantages of Recursion
    0 G0 _7 ^; j* P8 f7 }6 s, q9 w) ]& n/ o/ ~
        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.( X" s. L3 H) T4 T% u! c( }# Z
    . i) e8 i9 ?) C3 j3 T- t' a- Y
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    - ?+ F4 C* I4 w1 ?* R4 I( C1 }
    ( L/ ~) b8 i/ [, b% J1 @1 t" {4 CWhen to Use Recursion
    2 y8 X* i( h( p5 e
    * h4 N8 |! @( Z    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    & `3 m% F* [# m+ }* l& @( p4 M+ C; f' n( h  Q
        Problems with a clear base case and recursive case.( x# E* K% w  ~3 f, V

    7 Q3 z0 s& A+ k  kExample: Fibonacci Sequence
    + q% g. a! x$ s3 Z, I4 a
    & H% {9 i* k/ Y  V7 }. v4 x& ^The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:! {- _: l. x, Z8 a+ w) ]& T, g

    . [7 ]" w1 l% @; x( O0 b    Base case: fib(0) = 0, fib(1) = 1# @# \0 o5 H3 w! R7 M2 N
    6 h: H7 I; B: z) v* R
        Recursive case: fib(n) = fib(n-1) + fib(n-2)% Z/ m1 I! \0 |9 ]) m/ f0 L( g
    ; c$ u% }6 Y& A& ]0 K1 o
    python
    4 H( Q6 X( z; K2 l( ?: z, ?
    $ X7 I7 [9 G4 |$ f) C0 _; R7 w
    ; T; x, Y! m( Rdef fibonacci(n):/ G3 L5 L2 |1 ]/ C, {1 n2 f
        # Base cases/ q$ }: |! j$ s9 |( d
        if n == 0:) x( g% J( b& F/ m! {) o  e
            return 0
    ; [3 [+ r( P% D: [    elif n == 1:
    8 n: L; H& M5 @' \7 n        return 1* N: @$ ?" K. z' \/ \
        # Recursive case8 d/ P" P8 u2 E6 B2 `
        else:
    " p* q- }8 t1 C" V+ d' C6 I        return fibonacci(n - 1) + fibonacci(n - 2)( r" K) r. r9 V) Q3 h* m: r

    / M5 g7 w! V# ~/ i1 L6 H4 |5 ]$ H# Example usage1 Y: s* d% S3 m
    print(fibonacci(6))  # Output: 85 b6 _" k! u$ i0 N7 d: Z

    , U& _6 z6 C' o+ TTail Recursion
    6 h4 e* d) o1 T+ m9 v
    3 L2 k) I  m! E$ d& eTail 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).6 V( s" @* K/ U
    0 \* b/ ~3 T  K5 U2 j( a
    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-20 19:37 , Processed in 0.060145 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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