设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ) k: [: c9 h5 A# m
    0 k( A+ N9 l6 C4 l解释的不错8 L1 _" C/ A7 p0 o$ d9 c

    4 ^; e' T( O# I递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ! j8 v2 R0 a7 R  k$ o4 j
    2 p% S! l+ ^; ~- W5 G. G, r 关键要素& d* F( H& u4 ~2 A4 D
    1. **基线条件(Base Case)**
    4 O8 w% k# Z8 M* ]   - 递归终止的条件,防止无限循环
    : a% ]+ u( n) Z5 d6 d6 o1 D# R   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    3 b5 j" u0 s. b
    . O+ _% G' r: ?* r2. **递归条件(Recursive Case)**
    0 T% |# S- {8 Y0 \1 q% |4 L) l2 |   - 将原问题分解为更小的子问题
    6 g9 T$ S( V5 W3 A+ b6 J3 I   - 例如:n! = n × (n-1)!
    # I9 |( E/ m# k2 Z+ g) ~, ]7 o7 s# ~! \$ i) V1 Z2 V7 }, L
    经典示例:计算阶乘
    % D6 U9 A/ I2 |5 X1 J9 ^/ Ypython
    . n* N$ f% i2 R8 pdef factorial(n):7 V9 c3 A0 I8 }$ b7 {
        if n == 0:        # 基线条件
    $ Q: G3 }& I7 T        return 1
    & V1 Q+ W5 F6 H  [% k    else:             # 递归条件
    1 h5 j) \. a. o        return n * factorial(n-1)
    ' q6 O) {5 G9 F4 p: w0 m执行过程(以计算 3! 为例):, `4 N, C8 O) V; x( G. j1 z0 F
    factorial(3)9 w& h; V$ C, b; o! D
    3 * factorial(2). R8 ?% ?0 c2 D3 F, n3 h8 X
    3 * (2 * factorial(1))7 O/ m% z. V) E& `
    3 * (2 * (1 * factorial(0))), X8 n5 @7 |- x. h7 A3 S3 D
    3 * (2 * (1 * 1)) = 6
    " a) [& s, B0 L" ^; Z9 m% e0 [5 [! {. s9 A* }8 z& `* ~
    递归思维要点5 S6 p: ^* q& e8 [0 j( r& b
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑2 Z& e( h1 E& O( c& W
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    3 k2 Y- ^" u' X" z3. **递推过程**:不断向下分解问题(递)
    ; E! x# K5 e; r9 v' w4 s4. **回溯过程**:组合子问题结果返回(归)
    6 w( U- n1 h/ G# K
    8 W5 D$ `" m8 }" i" f 注意事项
    1 y# a2 h" j7 e' p$ d+ L5 `5 i必须要有终止条件
    5 n$ b* `2 s7 |$ l* I+ r7 P/ E递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    ' U0 ^" ~7 ?& l5 z) U某些问题用递归更直观(如树遍历),但效率可能不如迭代
    6 q. s+ z9 @- d; I. R* A& q2 C* f尾递归优化可以提升效率(但Python不支持)! y. S/ S% J4 X4 ?+ ~8 D: _, c

    5 m4 J1 A9 s* Y0 g4 [ 递归 vs 迭代$ J$ Q* D$ c" w8 `; g1 v/ @
    |          | 递归                          | 迭代               |1 S& L2 L. N! ^  K" ]% n& |8 {, d
    |----------|-----------------------------|------------------|. Q# M8 B" U, w& b8 H- p
    | 实现方式    | 函数自调用                        | 循环结构            |
    6 X5 V4 u) [! z- ]+ j7 f! R1 D| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |8 |- q( l7 u+ o
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    2 I9 M, n; V. \; }| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |4 b3 _& Y: }( D0 @
    / }3 x* H) _  O% ~: \
    经典递归应用场景  g) B8 Y3 e" n: ^. F7 E, F
    1. 文件系统遍历(目录树结构)# _4 C* P5 ]; x4 X. G5 v
    2. 快速排序/归并排序算法# Q. a4 \* H% \+ W, R
    3. 汉诺塔问题) J+ O0 R$ s3 K' ?; O
    4. 二叉树遍历(前序/中序/后序)
    : J- E* q0 }- h2 V4 b6 x; C& V! _5. 生成所有可能的组合(回溯算法)/ d) b0 [& h% i% ~6 J

    0 N% X) l$ t! O试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    1 小时前
  • 签到天数: 3104 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,$ n! N  {$ `" @1 Y" l, U$ C& C; y4 s2 f
    我推理机的核心算法应该是二叉树遍历的变种。; \. l0 P4 `6 A0 r& R& O* _
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:, m8 _; p; I' M( v
    Key Idea of Recursion
    * i9 K5 D+ `# ^) J" ^: S
    + `9 A7 A! ]' m5 V% @A recursive function solves a problem by:3 V% h5 d  Q/ {9 K

    4 m# B( R8 \& b3 a' d. c    Breaking the problem into smaller instances of the same problem.
    7 R0 T4 D7 q. v" l0 e" e
    1 u; @6 C, S, h: ^& Y0 I9 T# H    Solving the smallest instance directly (base case).
    5 `" P2 u/ B: g% }7 N0 L7 S) _7 i/ b0 r5 P! i7 V8 E+ H
        Combining the results of smaller instances to solve the larger problem.. a. N$ _+ o  b" S5 u# E9 H
    - Y! ]; H* D+ \: B9 X7 ~
    Components of a Recursive Function
    * J: q( H1 \; o* v
    4 F" r$ b. [" _7 n    Base Case:3 K2 e7 S* ?2 m4 W5 w

    % S; L- {- |+ s: L7 s        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.6 U3 ]0 ^% _# Y7 o0 I3 l
    ' k6 ]8 l$ Y& J
            It acts as the stopping condition to prevent infinite recursion.3 G  C6 }4 s; R2 Y
    0 C# F2 i9 g$ G6 P$ I. {0 i
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.+ S( Z$ R1 u, a" c3 E. O

    1 L+ V% |* r0 W# R, N    Recursive Case:
    ) x1 [0 }, @( Z2 s9 B# X( t/ s0 v, G% k$ x4 W
            This is where the function calls itself with a smaller or simpler version of the problem.. u* [6 S# v" s2 |6 b; V
    1 N1 r) E+ q- x1 M; L! o
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    $ r; e/ L/ p6 \; m" Y" w5 M
    - c' L2 P2 K& G7 B' T! l. \) d: {Example: Factorial Calculation
    1 w2 x& D$ [* D' _5 o  j. F9 e& R. T7 S. v( I5 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:
    * S$ `6 O) I9 G- n0 g1 [3 W7 _1 f! \. [
        Base case: 0! = 1% g/ C: w) x5 p1 |, |) Y1 u
    # H) A, o, F4 m6 L1 g6 d
        Recursive case: n! = n * (n-1)!
    ' n6 W3 X$ x! h8 \7 r& X6 [1 b9 g1 X; E2 j. r
    Here’s how it looks in code (Python):" M3 P% s3 |/ M' i
    python% M* F5 f, D/ X2 \$ l8 M

    4 ?, K2 p" G( \* }4 |1 P( B% {' C: Q
    : E9 H) M; ?4 w' j2 W$ @$ o; Odef factorial(n):
    8 Y# R) ~; l& E* i3 X    # Base case4 w) r2 F& m0 r$ M* i0 W: i. R1 {' ]
        if n == 0:
    ' I' @! Y$ x0 l# N        return 10 d& z3 {- E; y5 d" z& F* |
        # Recursive case
    : Y3 W- _! C  D& N8 l; L/ F    else:& m: n5 j  c0 i: m0 w1 c$ ?
            return n * factorial(n - 1)
    & J0 A( E  r8 u  {# V% X
    ( i% L4 w% h; w* N8 R# Example usage5 x" |) F8 p& P- h$ Q
    print(factorial(5))  # Output: 120
    " A5 t; k. ~" c2 f
    - C; z2 Y6 K, b( hHow Recursion Works
    , F2 A7 \! d- Q2 E/ C+ Z. l- f, @9 G6 ]& D9 O& g) b
        The function keeps calling itself with smaller inputs until it reaches the base case.
    0 ]/ v: v7 d: [# k: R/ O
    ; q% [; \: p; J9 ^    Once the base case is reached, the function starts returning values back up the call stack./ E% h) t# M* g: I/ U
    2 S; m4 t5 U" @- K" m: j( z8 ~/ \
        These returned values are combined to produce the final result." Z  s  [! _! t+ V  X
    # [! @0 z8 K6 B* |" D3 M3 M4 Y1 Y
    For factorial(5):* u$ W4 u, w% N$ Z  f+ G7 z' r

    6 |" F8 T2 W$ \3 I9 L2 z+ n1 h& {/ Q4 {- J( D) r0 b  ^
    factorial(5) = 5 * factorial(4)
    ; C' Q! K! b1 N3 s& o  M6 Y  }  ~4 ?factorial(4) = 4 * factorial(3): p# K) o$ [3 Q9 [6 m; V+ a8 L8 u
    factorial(3) = 3 * factorial(2)
    - {4 v" O1 f# c' x+ Lfactorial(2) = 2 * factorial(1)
    % U. x6 m: A7 @0 _7 k! kfactorial(1) = 1 * factorial(0)
    7 a6 k, R$ Y3 v9 p/ _1 F3 T8 z( I: jfactorial(0) = 1  # Base case0 j% p) |) ^( c* ]" N1 |

    - x  ^( A: e+ R* F2 M' D; {Then, the results are combined:# s9 T5 e, }5 Y7 k# {
    ) }9 _( w* r( X8 I" k3 ?- ]

    8 a* M/ @. I  e2 z, ?$ i& {2 Bfactorial(1) = 1 * 1 = 1# G8 L/ q& C' n
    factorial(2) = 2 * 1 = 20 h! z# x. s% P1 X2 G
    factorial(3) = 3 * 2 = 6
    ! B0 w. a8 @( h+ N% s. J$ Mfactorial(4) = 4 * 6 = 24/ A/ Z% c, \6 X. I- k5 m; q
    factorial(5) = 5 * 24 = 120) e2 s4 S& G+ Z. \9 ]

    3 c: t# q4 F: d' ~! TAdvantages of Recursion
    & h: z. {0 q- o9 A  \9 W% L- e7 K5 _5 G; E* @
        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 k3 n+ q/ h) C( s  s
    " ?$ Y3 z' H. \7 k4 Z: W
        Readability: Recursive code can be more readable and concise compared to iterative solutions.* Q+ Y# j9 o5 Y% P/ h
    6 r* @. o9 a. d/ m6 L6 }8 S
    Disadvantages of Recursion' I  ?: r: M& }, k
    " i1 `; ?3 K# W- \- i4 V
        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 H( m' o) f% V+ Y; a  B# o$ K
    4 v1 D( t  B7 M, p
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).) C" w: w6 f4 r) f; A$ @

    , K* L4 q; B. d2 vWhen to Use Recursion  @$ Q  a% r% R( H

    1 f" P( }4 s: P: g/ ^    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    - Y0 ^! [7 ^, W# t0 Q8 O$ T! t6 @3 y
    : R$ `5 a* w! p) u" j    Problems with a clear base case and recursive case.; i) b" K& p, I
    % k, |( b6 D, F6 g4 b; p7 E% Z$ C- i
    Example: Fibonacci Sequence
    * d9 `0 L$ U1 F* ?0 v7 b
    3 G0 Y# a$ h3 c, _/ y9 qThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    . u# {9 p* _% a' q0 Q& _- F1 v8 A% X* a- [7 R, n  N# O
        Base case: fib(0) = 0, fib(1) = 1
    % s9 @. X; {3 O0 o$ H1 K
    : i/ Q0 ]0 f) N+ w$ N, w: o    Recursive case: fib(n) = fib(n-1) + fib(n-2)1 Y5 j8 ~8 r3 f
    ' d2 n' e7 p' l1 I
    python
    5 t: ~9 Y' Y/ W/ c0 T0 F8 Q" w( w* S; D* l. }
    % W& c8 _3 g' W8 T& t2 Z  E
    def fibonacci(n):! @/ ?- u; o+ P$ \6 g  w2 S
        # Base cases
    7 ]  C3 X" c1 `4 k( _3 E    if n == 0:
    - t4 r8 B. {* Q) |4 `3 K  w+ I        return 0
    : J& T; e9 c% D    elif n == 1:; X. z1 T% Q# n1 C* J+ e- z
            return 1
    % ]0 v1 R- Z) e" L+ o$ @, p3 S: Q    # Recursive case
    9 h4 t8 I; C6 K% h5 X+ z    else:
    6 |2 N7 }: r& W* m, k; O        return fibonacci(n - 1) + fibonacci(n - 2)
    0 V- g& r8 V& G" M. b7 o
    7 t% W3 h& C  Z/ w; S1 u2 g8 f# Example usage
    ; i; M( U- n6 ^& f, ?- ?- j7 P- Dprint(fibonacci(6))  # Output: 8
    6 a6 n$ @) _! u' O* a; k9 R# G" H( ^$ l; D# t
    Tail Recursion
    8 i2 I. h1 r! j9 m: |! r% h# V* `. n/ L2 l) y. y" m4 x3 H! {# c
    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).3 h% H0 |7 X  t# |  ~# t: ]
    + T- I; k0 m% b. T) e& n6 t
    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, 2025-11-29 08:34 , Processed in 0.033220 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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