设为首页收藏本站

爱吱声

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

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

[复制链接]
  • TA的每日心情
    开心
    2015-11-30 11:11
  • 签到天数: 2 天

    [LV.1]炼气

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 & R& s. v2 N: k8 x7 v: }/ N7 N2 c. S
    + b: d, _) u0 j: P% k
    解释的不错
    5 r7 F4 \% W0 y* n
    . F& l3 G( S% `6 H  p) b" R递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。  ?7 n0 d  d' U: e7 A
    0 Z" X2 P9 _" j$ _& e
    关键要素
    7 n9 ]* `9 s2 L, y2 w8 U- ?1. **基线条件(Base Case)**
    - M" ~3 I6 G& j4 \  \   - 递归终止的条件,防止无限循环- V# H: N1 ]/ J
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    3 k0 y& M) ]: n# H- g: B. K) W3 G( `: c. Q; _! L
    2. **递归条件(Recursive Case)**8 H$ J7 s9 r) H2 V2 |( b
       - 将原问题分解为更小的子问题/ G- K. L3 c1 m/ z. q# X* A
       - 例如:n! = n × (n-1)!; K4 c3 q. O& u# V
    4 g  z& l2 D: P8 ]8 Y
    经典示例:计算阶乘% S& l" G' f; L
    python: s+ M2 c) K. r1 l2 T: [
    def factorial(n):
    3 r* o8 J1 j) e, R5 L$ T    if n == 0:        # 基线条件
    # k% Y& N: J  L7 j- ^; ^9 F8 ~- _        return 1
    8 Q, W' h1 O* r( R2 e% G# C    else:             # 递归条件" C0 z- N/ k2 O1 D3 b
            return n * factorial(n-1)1 o4 k5 \0 `* S
    执行过程(以计算 3! 为例):2 D$ w0 H6 b2 R3 k. o! p
    factorial(3)
    : F$ h# h5 x+ J( P0 \7 [7 M3 * factorial(2)4 N& t$ N, R+ |- {+ w+ W
    3 * (2 * factorial(1))
    . y8 s3 o$ y5 N( v/ t. ?* N3 y3 * (2 * (1 * factorial(0)))2 a- }: t  [4 {) C% ]3 c
    3 * (2 * (1 * 1)) = 6, {% t# b; q- U% e2 Z$ a- L

    - m7 O1 L4 c2 u" K 递归思维要点, r  Z- o& D6 p( P7 A% m
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑5 j/ E: t' v3 p+ _% j4 i
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)9 h/ k9 U: s6 u! t3 B3 @
    3. **递推过程**:不断向下分解问题(递)
    1 u( }, y  \$ L  i4. **回溯过程**:组合子问题结果返回(归)7 [9 n5 z2 d) r, a  Y; U9 K: r7 Q7 r

    3 T$ m: Q; S7 t" i- k/ [ 注意事项  W- ^4 v: h3 D% C, U  r5 u
    必须要有终止条件
    7 o6 f! h5 K4 S0 `递归深度过大可能导致栈溢出(Python默认递归深度约1000层); p2 Q5 P! t2 E( [( I
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    " K8 |" B8 z7 G  `尾递归优化可以提升效率(但Python不支持)
    " t8 T/ o6 F4 {6 o" P0 Q  }
    : H, X% \. H( e9 F" j7 l: C( V 递归 vs 迭代
    # O* E& E$ K1 c+ k% ^; Z2 I7 p|          | 递归                          | 迭代               |
    8 A% Y' `) ]9 ?0 n|----------|-----------------------------|------------------|; f) K1 @) r3 E1 [7 Y" w
    | 实现方式    | 函数自调用                        | 循环结构            |
    $ |* B6 ^& y7 I& @: {6 L| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    1 K& ]! [; A2 [2 f9 f3 b| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    , s3 }8 N3 O9 w, I| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    ! G/ [' l$ K: _$ X5 i4 A
    2 V, E4 p* U6 S7 A 经典递归应用场景
    2 F2 @+ z: Y/ P7 E9 D, U1. 文件系统遍历(目录树结构)8 w5 b. [3 H& B' O" w! r- H) O
    2. 快速排序/归并排序算法! e, z# U1 d7 u3 b
    3. 汉诺塔问题
    0 R9 p8 ^+ D# B/ a" R4. 二叉树遍历(前序/中序/后序)+ D. y/ T, c# f- R5 i- h2 ^$ P
    5. 生成所有可能的组合(回溯算法)
    ) S( A+ J  K+ N! e9 F; m% t* j. H1 n# {  H% ~( f7 _8 g' d8 z, j
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    3 小时前
  • 签到天数: 2940 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,2 `6 L( @3 T+ f- W& s; c7 v
    我推理机的核心算法应该是二叉树遍历的变种。
    $ e* c* d8 y1 l1 b: P* S# e/ j另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:: \. L2 c% X0 h6 @# L/ N$ z
    Key Idea of Recursion
    - n0 e; [' _- \  U: P1 P3 {3 \$ i- a2 |
    7 y- j2 B% n9 Q1 K5 [% }% ~A recursive function solves a problem by:
    # j$ g$ t! Y3 f' ?' g. e/ R$ m- @9 u; X
        Breaking the problem into smaller instances of the same problem.
    " q- J0 X" ]# A9 p. k3 J/ A5 O2 G! X4 _- n2 e) F' u
        Solving the smallest instance directly (base case).
    # J! t9 l% K0 J9 Z6 V" p, N
    / S: u8 g7 e3 m+ U' u    Combining the results of smaller instances to solve the larger problem.* @2 c" u/ U5 g# z# |, d* u% m

    ) i9 P. z3 g- O* F$ J; Q: @2 UComponents of a Recursive Function- C  q4 z, n2 |) w8 s% H3 K
    8 o1 n4 K, g2 j0 P2 p% _  u
        Base Case:
    7 o0 v- k* l8 Y  A: z/ `( V1 c4 J4 J( F2 M7 ^1 g( o
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    6 O/ U# t2 ?8 X! c- N! G
    " g8 f3 T. z9 w        It acts as the stopping condition to prevent infinite recursion.
    ! s; I8 O, d9 g4 |) L) t. `' L! {! |$ v3 i6 h' O- c
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    + o- w" g1 R# h5 s* V
    . r* ?3 ^6 i# r$ N+ J( l  `) h    Recursive Case:
    # W9 e0 r  p/ s. w/ t8 L; Q+ T% t$ Z2 x
            This is where the function calls itself with a smaller or simpler version of the problem.% w, o) q/ z3 E4 d$ U, }9 D! @

    7 Z* V" @4 ~& B6 u7 l        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    1 Z) e% K5 y7 Z
    % _: c- ^: a( V, s1 @Example: Factorial Calculation
    # j1 x$ l- v3 i8 c3 K" g& T* x9 Y) z: I+ 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:
    ) v! k" v0 a4 N& f% S' q/ ~) J/ c( {" o
        Base case: 0! = 1$ l" A, E  @6 [* w: H; `

    - I0 `  e( [! i    Recursive case: n! = n * (n-1)!7 X7 ?0 ?! m$ v2 I) |! S

    2 ~  N: Z' S0 f5 n! SHere’s how it looks in code (Python):
    / b8 x, x6 j5 d5 s& P0 |2 Ipython! x, Y/ f7 E  B5 P4 Y
      Y; i7 D& R( N
    " v$ d  n4 N* P% d
    def factorial(n):; L5 N/ E$ S( v/ u* A2 s8 y4 o, E
        # Base case; w$ t) m4 ?  U& m7 }' k' \! l! x
        if n == 0:
    . G' {7 E8 Q, ~2 q' o( U" I# X        return 14 k  u7 Y; l" T- Z, I
        # Recursive case2 y3 z' e# w" v5 s: K
        else:# T/ I% K3 R, J7 P$ q* j. l9 ]
            return n * factorial(n - 1)$ H" D4 \+ e# T/ D6 i: ~+ K

    ' V& T2 m, L& f2 d' v: U# Example usage( h4 ^2 J2 t( }) @( F1 Z
    print(factorial(5))  # Output: 120
    7 k9 o/ Y# @+ _+ V  X6 }& k3 ^! p1 S5 h
    How Recursion Works: e" O( N9 {" ^7 ]+ _
    9 f- ?7 s$ C% b- f/ Y3 t* u
        The function keeps calling itself with smaller inputs until it reaches the base case.6 y% ^8 Z; p: u

    % K) t! D1 [1 }, Q4 G    Once the base case is reached, the function starts returning values back up the call stack.
    6 y2 W3 j; D9 ~. s- O- E- L! x0 u# I  o9 e7 `5 x- h* ?! i
        These returned values are combined to produce the final result.2 |  D3 w& g/ m8 ]. D
    / f" H2 P9 @4 s4 u; E  F/ r
    For factorial(5):
    5 z/ T' X. Q" F/ Z
    9 H+ t: d) w- X! Z9 b/ x  \% A' H6 e" t  B( c& G" n% T, ?
    factorial(5) = 5 * factorial(4)" Y6 M' N/ X2 x" S. ~3 a9 r
    factorial(4) = 4 * factorial(3); {2 T' i3 k. X
    factorial(3) = 3 * factorial(2)
    ' X+ ~6 j; ]9 q( b* O9 |factorial(2) = 2 * factorial(1)
    * ?, p# f, r  cfactorial(1) = 1 * factorial(0)1 o9 ]. u3 v+ y! T, H2 x# h: P& R2 d
    factorial(0) = 1  # Base case
    , a; e4 r7 O: ?+ u" Z: X0 C# z& i2 X6 Y  u1 g/ U0 k
    Then, the results are combined:7 I- F, S* i% d( O. Q% ^* T: T
    5 D$ C) j; {/ c; j

    0 m* c+ z: n4 `+ V* cfactorial(1) = 1 * 1 = 1
    9 D3 S1 d9 S, l; rfactorial(2) = 2 * 1 = 2
    6 p3 f+ `  f  r) v& jfactorial(3) = 3 * 2 = 6
    3 t1 l! a" N4 r9 @5 Sfactorial(4) = 4 * 6 = 24
    6 x7 G& y% M9 u6 i$ `) x+ O+ F3 C# ~factorial(5) = 5 * 24 = 120
    : v# y/ L3 k  b0 ]. u8 n8 D2 P, D( u5 q# t; m& I! q
    Advantages of Recursion8 ~, \6 D. L, G
    2 n3 C: E/ H( [0 I9 O
        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).
    6 M* v+ B* ^: d0 B
    ' [1 t7 {- ]6 m( o# K0 [$ v    Readability: Recursive code can be more readable and concise compared to iterative solutions.( e* f6 {; m' Y. P$ l( C2 ?

    8 {2 ?- Q8 p1 e% ?3 LDisadvantages of Recursion
    , |8 z$ s$ _1 L9 g; W5 I
    / Q% C. b7 c% {; r+ P. c+ L) j. V6 j    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.
    * [( V+ `, _/ _0 T& O  L  i
      R; v9 I" i1 m  ^6 X1 ?0 _  i    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    7 ~& u& C9 g7 a& {4 i& c
    5 l! D7 h$ J2 S2 _: yWhen to Use Recursion2 _, P! O6 c3 h' ]4 a' F5 v
    - l/ N: d; J# y9 W  n5 U, @" T5 Q) \
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    7 n! a1 q, G3 V/ c9 I2 V0 X8 @9 r! h
        Problems with a clear base case and recursive case.
    0 E% I4 ]! H, D. z2 {6 D/ ?: b3 R: [0 W- q9 u6 u
    Example: Fibonacci Sequence* n; \/ L" M9 ]! a+ A

    # X" }6 X  T: p$ ]The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    4 q% L6 \/ g( x7 G- K
    2 V( V- \& ^2 F# M) T( V0 B    Base case: fib(0) = 0, fib(1) = 1
    8 U/ e. B( G6 ^
    1 Z+ y1 U% X* }1 u7 R( c5 x    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    / W- j* [/ z, C5 f# c
    5 k5 N( ~1 [* N. R8 hpython
    0 Z4 K' _# P3 c6 z$ h6 Q/ F8 s1 h9 j
    9 M8 t2 ]8 B4 {! u% A3 H& l$ ~
    def fibonacci(n):
    ) D$ I& z7 C4 z8 D* p- b    # Base cases6 ?, g+ B6 A, _  L3 D8 Q
        if n == 0:
    , I, N! h# I8 Q- B% \        return 0! ?: s6 W& f/ ]& ^8 m, n8 Q% m5 n/ m
        elif n == 1:9 }8 _# r0 c* [2 q1 Q
            return 19 `# ]  A2 Y& V
        # Recursive case+ ?7 L" N8 S/ ?; |% O3 ^# ~& S
        else:6 Y* a: e" T; U$ ?: U; h
            return fibonacci(n - 1) + fibonacci(n - 2)3 u8 H2 \$ ]" ]7 N, t3 t

    ) B4 I% p( j" A$ [. ^; S  y# Example usage
    . m- ?9 Q0 D' b9 Y" ^9 Y# q2 Lprint(fibonacci(6))  # Output: 8% W+ M2 n' M, l) K- E

    % R8 ?8 X/ i3 l' A3 l# o3 STail Recursion9 s( {7 o1 \3 _1 }; O
    $ d$ M! p, l/ P9 T& G! l3 X
    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).
    2 P- Y8 G+ r' N) _, e* V: X" f. R1 X7 p* _. P6 r0 D1 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-6-4 08:02 , Processed in 0.035581 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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