设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    : o4 o$ K, U, C1 d& e& M; Y# m+ U) h& B1 R7 }
    解释的不错
    1 i+ G% L0 b$ l, ?7 h0 z" E: f$ L5 Y% W! S/ S
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    * K. A" i; s$ @- _; w6 q. Z( C, m" K$ f' p
    关键要素, V# l3 U3 U/ U; M
    1. **基线条件(Base Case)**5 }. ?/ k7 i. p% x
       - 递归终止的条件,防止无限循环
    0 V" i. l" n  O2 O2 ?0 j: j* c   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    7 `; @" B, t3 H
    / s, t/ V2 S' M1 n9 o3 }; j2. **递归条件(Recursive Case)**
    0 V# y( W1 |. n# J$ U   - 将原问题分解为更小的子问题
    1 `7 T  {" B/ r7 z+ B   - 例如:n! = n × (n-1)!
    5 w* u, S9 `2 Y  [6 q
    + R' X" f3 r  G# U6 M 经典示例:计算阶乘8 ?+ O/ x2 k( E- [4 l; G
    python" C/ R1 E" _4 [4 }/ a$ H' {- P% \
    def factorial(n):
    9 z( g5 R6 b2 ~, c    if n == 0:        # 基线条件
    ( r2 a$ B. _5 L& B: D5 |+ M        return 11 R$ V5 @8 o4 o9 ^& H
        else:             # 递归条件3 G- ^8 N& n2 c
            return n * factorial(n-1)
    $ N3 i- ?7 |! t1 ^" F执行过程(以计算 3! 为例):% @. l9 a" N7 h, Z, i/ F
    factorial(3)
    ; R* X& ~& J' J! E3 * factorial(2)6 G& D$ P( E1 ?( m0 i( q, t' U
    3 * (2 * factorial(1))
    & I5 T1 l# b, z# J9 |6 }3 * (2 * (1 * factorial(0)))
    4 g1 F2 w; Y! O4 e$ V& H4 F3 * (2 * (1 * 1)) = 6
    * `# s$ Q; I( J4 l8 M, {, X6 u$ I& g3 e- y& T2 p
    递归思维要点; c+ e7 t' o; i/ F
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ! Y' s% k) ?9 |7 T; o3 D- f8 w2. **栈结构**:每次调用都会创建新的栈帧(内存空间)2 h7 @4 y( g1 I7 _6 f
    3. **递推过程**:不断向下分解问题(递)1 n8 J/ n8 Y( `
    4. **回溯过程**:组合子问题结果返回(归)
    2 e, A& v  |, z! S8 |: e$ o% t- t
    ! D; W) u1 a7 u9 {& H3 o 注意事项
    9 ~6 d) O: ~4 _" S5 `& Q. N& w必须要有终止条件
    1 T1 _- E2 ^* K6 p! o3 \9 g递归深度过大可能导致栈溢出(Python默认递归深度约1000层)5 J% V# [  ^% P0 T7 r1 q( T1 w  ^# L
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    ) }0 Q* A& G4 z  H5 R尾递归优化可以提升效率(但Python不支持)/ d, Q# F- L  Y1 H. ^

    ' k: _0 [& ~) O1 C: L& q- E6 G 递归 vs 迭代
    4 Y3 g2 d7 [/ @3 W|          | 递归                          | 迭代               |% j& g; p$ i6 o( \
    |----------|-----------------------------|------------------|2 h1 R- V% Z' Z' \8 x
    | 实现方式    | 函数自调用                        | 循环结构            |
    7 Q% i2 u8 t4 D; @4 ?6 _* p5 d| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |6 I' x+ E' a' w% ]6 }4 `
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ; {/ l5 u" h+ n) S# W( q1 H| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |4 {' H9 W4 T* o0 ]! ~3 d  Z: Q+ |
    - V4 ~9 ?: n) D
    经典递归应用场景
    ; h- T* Q1 ^1 ^1. 文件系统遍历(目录树结构)' K2 E9 _' a9 z5 A/ a! M
    2. 快速排序/归并排序算法
    5 V8 s' ]7 ]2 @" N$ t3. 汉诺塔问题- o; [: b0 A8 j- H9 D
    4. 二叉树遍历(前序/中序/后序)
    / S- \/ p1 j" N" x5 h' ]5. 生成所有可能的组合(回溯算法)
    % U7 a2 [& J: R7 i" o7 |2 X& h/ {4 D! |6 a( I; Z. ]
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,' @8 l+ }5 z' c1 t3 O+ \
    我推理机的核心算法应该是二叉树遍历的变种。' Q& f4 i/ O# I0 T) E, r+ v4 [
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    6 E1 P; d% f6 IKey Idea of Recursion, n: j! }  @; y, T$ l' j7 K2 M
    $ G3 Y9 D5 J! c3 W0 F
    A recursive function solves a problem by:
    - u7 w, B( H' D8 L0 V* n( J) G  q
      d; S1 \/ o+ t    Breaking the problem into smaller instances of the same problem.
    6 e  f6 f( w2 \, ]! I: C
    1 {' M1 T# I& K% L: O9 `2 Q    Solving the smallest instance directly (base case)." h) j& w: f3 k; K
    ) _$ s) ~& q$ l( r  T9 J+ _$ f
        Combining the results of smaller instances to solve the larger problem.* o- U6 N: V, i! P5 Q
    $ N. O7 ?% I* O
    Components of a Recursive Function
    1 i& ]. S! [& A! R
    $ P; c- G+ h' I: I4 Q- K0 g. \    Base Case:% L2 g3 y7 j3 r
    # {- Y5 h& A6 Q" |& _; b
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    + {& |  P2 O/ X% D
    & u& a- |2 T5 i/ I# X        It acts as the stopping condition to prevent infinite recursion.
    $ H+ V/ N( ]& F: ?- ?7 M9 k* _  d
    / Z5 ]3 q$ i6 M/ ^8 |. h        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    ; _- p. Q3 N, \+ `( }: \2 g  R8 J$ M+ s) f; ?8 b) ]
        Recursive Case:
    8 \8 Q0 K0 Y  j4 s. K, S
    / X0 ^0 N( b0 W, s2 k        This is where the function calls itself with a smaller or simpler version of the problem.: E4 u" g/ V& ?2 ?. ~4 T! x
    # [$ D& F; z1 ^) Z9 H/ ?: L
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).0 e0 }, J/ Z7 r! u, q0 P% n( A% Z

    : u( s0 M$ R6 e1 zExample: Factorial Calculation
    + ^" |- c/ g. P9 A9 p! y: n4 s+ d+ b
    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:
    1 c  V5 n% P5 A" {" \' X. U6 |, ?" }. [
        Base case: 0! = 1
    & J7 d9 }" E" q; s; A9 W0 S& n$ F( @* l/ m
        Recursive case: n! = n * (n-1)!
    6 y2 F, X' P" J/ F
    % n) Y8 ]4 N6 i5 h7 _0 H2 x3 PHere’s how it looks in code (Python):2 {$ E+ r8 S. e4 H
    python
    : t4 `& ]3 [( o9 e. P/ C! m% C# I0 u7 F2 {) z
    & O$ c1 c' C. B$ ?
    def factorial(n):
    % Y$ Z+ D3 U8 t3 y1 ^6 R    # Base case( x# c, }; [5 |8 S, h( T) W
        if n == 0:
    $ J, T. N' O) k$ f; B4 F  Z3 Q6 y        return 1
    , H* k) ^- t+ |: |* M$ C; ?    # Recursive case" j2 }" p  v, ^* O
        else:0 _# S) ^* Y2 b  }9 o5 U
            return n * factorial(n - 1)
    - _4 ~/ Z# |( N5 w# ~' B; A: I# `5 m2 ~' z% P; n4 e
    # Example usage
    ( |: w, W, M  M) [' A4 W7 X4 hprint(factorial(5))  # Output: 1202 K7 Q# @3 M3 J' O  K0 Z# G
    ' o) K5 ]8 G; }1 N& G7 J  k/ r$ o
    How Recursion Works8 I- t3 A' i) t* ^, Z2 G

    & g! Y: O0 J4 W( b; R    The function keeps calling itself with smaller inputs until it reaches the base case.
    & \6 U& {8 ?) J7 h9 x) e
    " W, ~, k1 P& R- \: ?0 I6 ^    Once the base case is reached, the function starts returning values back up the call stack.$ B- A, M6 O3 e% Q9 i2 a$ _
      q% K: b7 e+ |' F7 t! l  m
        These returned values are combined to produce the final result., _: ?2 j. X- m' j, W% z8 S

    , ^& G$ `0 s# J0 t' U7 M3 i& o4 b6 dFor factorial(5):
    , J6 E6 ]$ G: ?: ~6 D) @  j4 d) x. E- q) r
    1 w$ Y+ I1 ]' M
    factorial(5) = 5 * factorial(4)
    $ g, _2 A7 o5 ?; j/ n( gfactorial(4) = 4 * factorial(3)
    . n& U+ v* f7 g" zfactorial(3) = 3 * factorial(2)* U( d4 e8 c+ h+ e
    factorial(2) = 2 * factorial(1)
    , W+ p$ ~  i. t- n5 S6 |3 ?factorial(1) = 1 * factorial(0)3 a  |/ b4 J1 ?9 \7 h
    factorial(0) = 1  # Base case. Q2 L2 X! X: v2 u

    ) {$ G9 ~# g- y4 \1 j% {; BThen, the results are combined:5 Y" ~& i4 F) S3 M; X9 ?

    2 K  M6 l% r1 V" c. \7 ?5 w" R; C7 R/ w$ x! b
    factorial(1) = 1 * 1 = 1
    8 E& Y' s) U  Z, Ifactorial(2) = 2 * 1 = 2
    , p) u; e5 D& ?( Pfactorial(3) = 3 * 2 = 6* C; P5 y$ P3 Q5 a/ `
    factorial(4) = 4 * 6 = 24
    * L; ~! A  Z; r. t' f2 H$ afactorial(5) = 5 * 24 = 120
    4 ~! l; W. y% ?8 V  @  R7 n0 r( P$ z! T4 _
    Advantages of Recursion$ V; U+ w/ w5 D

    1 }4 V* c2 G, s8 j    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).. I3 y7 f! ?9 m9 @) r, ~

    / H( v# t1 ^+ y5 p  H- a    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    * x$ w2 j) k1 I- V7 _
    1 z/ \! ]& I& H8 M! bDisadvantages of Recursion
    ( x7 R) x8 C- d! _7 x7 @& n
    / f! n! l0 z" a2 H, C    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.
    ; Q+ `; a+ S+ K' v) ?7 l5 m5 m% d
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    : ?/ z: N8 L0 I# i+ J  I& k3 ]& }+ Q& r- {2 }" v4 Z
    When to Use Recursion
    - g* J! h& i1 b
    % }) d: b9 @5 n* c& {' K    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).( `* g- t- T3 l4 F9 }2 b
    * S: R9 }# I" h. \& ?2 j: D
        Problems with a clear base case and recursive case.
    0 I% q  {9 |6 ]( J
    : F& q3 U4 T; s# q$ f% t; ]Example: Fibonacci Sequence
    & W3 i8 w4 Y9 Y- _2 i: w& d9 Y7 I3 P, q0 q( i) T6 D. F* w
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:& j( o" }9 [' W7 |

    9 \! Q$ }6 z: W    Base case: fib(0) = 0, fib(1) = 1* a4 b& K7 V1 k" z2 d7 r* t

    5 Y0 J7 l" k% Q1 |    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ( }6 Z5 h) }# v: M4 _/ L+ @. ^& Z* H: e/ s' i
    python0 q4 M7 G. X( o- ]  ?; |: W
    . _% z, \3 G- i7 U2 b+ b0 A% K

    + y. g: @/ i5 G# q4 v4 Udef fibonacci(n):
    : L) x! U. O0 {" p6 D% r- }' t" M    # Base cases
    6 _+ N9 a4 Z: [/ B    if n == 0:4 O3 P' n* V6 J# Q
            return 0
    / p# |+ I  X! e    elif n == 1:, W6 ]2 @0 L; }9 u7 w3 y
            return 16 r, S3 v- G  N
        # Recursive case! W. }* W/ Q2 i. K; Q
        else:
    * E9 D1 s+ u& o8 M- \        return fibonacci(n - 1) + fibonacci(n - 2)7 h9 B: `- J% W$ |: \* Q% ~* _

    - ]$ Y2 t: E8 d) U# Example usage; e) y( f& ?# Z' |* \
    print(fibonacci(6))  # Output: 8
    7 B5 n+ `: o  f% R/ H" u& O# G' R( C
    ! ?- i) N; v% x' XTail Recursion* j9 x& i" V1 s& t

    $ t% M% W: u: s* ~' H* WTail 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).
    ! K. q$ \& D% N5 y5 K# R( B$ Y. T6 R5 ^1 {
    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-4-29 00:43 , Processed in 0.059437 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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