设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 $ |0 a& E4 a6 _0 f& e* a

    3 K+ i0 B8 W4 A% ^1 f6 }1 a7 p4 d) D解释的不错
    ' p1 C1 S4 H$ ^! l, k- R
    3 P+ F7 z2 c* C递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    " w2 `) Z* X; }( D2 e  U, H5 E8 z$ t+ t
    ( g: Z: H+ `  @& q6 w6 B! p1 L1 d 关键要素
    + w. {" m* j, v: \; X$ |2 U1. **基线条件(Base Case)**
    # g. O/ _) v' ^( h+ m/ u$ A+ b   - 递归终止的条件,防止无限循环
    3 j  N/ z2 K6 f* Z   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1! ^1 r) ]7 h  F, z
    ' ~& p8 Q! U* ^/ @2 \& g
    2. **递归条件(Recursive Case)**
    ( W  O  o. R  W* V/ A  q# T   - 将原问题分解为更小的子问题
    & U- w' }! J7 i5 S   - 例如:n! = n × (n-1)!
    5 P0 l0 p' z, a8 T( p
    ( i( a6 i- g2 ~) q# ^; i9 C& v6 U 经典示例:计算阶乘
    5 h& `9 X/ u1 h4 O& Ppython. E$ ]% V1 i* U- q9 G6 q( U" u
    def factorial(n):
    5 D' E. J) h  |4 H8 {    if n == 0:        # 基线条件2 D7 [; l4 J# p: z, |4 w
            return 1
    . A! \( H4 p% M4 b7 e+ p    else:             # 递归条件- c( ]$ e( E" X: `- t% b
            return n * factorial(n-1)
    5 G# Q, |" n( i2 k: V& u* h执行过程(以计算 3! 为例):
    * a1 u! f' s8 e( }factorial(3)
    8 @. d* C" Y  @/ V3 c5 j& }' Q' m3 * factorial(2)
    % q) W0 a. T# y, Y1 l5 O3 * (2 * factorial(1))$ w; I# c' m" v3 G" ?
    3 * (2 * (1 * factorial(0)))
    ! w1 x. |) l' ~3 n0 F6 N& v3 * (2 * (1 * 1)) = 6
    $ v# U5 K# j" b( \6 R% @% s8 h% y
    ! ?/ Q9 j1 q# L( p& ` 递归思维要点
    & S, _8 B. P% T: _2 h- g/ P! g1. **信任递归**:假设子问题已经解决,专注当前层逻辑; p/ z; q5 H0 x+ B
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)8 o) k: q' x; d. ?7 V. ~, ?
    3. **递推过程**:不断向下分解问题(递), |! D0 K4 {* B% c9 ?# i" w: i+ ]
    4. **回溯过程**:组合子问题结果返回(归)% F6 i, K% R& {0 t5 F$ j# `
    8 q$ t+ m5 I: t& ~. e
    注意事项
    5 D% C: q, {. p/ m* O必须要有终止条件
    " s% h9 S+ U2 G- V递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    $ J) x: k2 t+ a9 h% y* M' k某些问题用递归更直观(如树遍历),但效率可能不如迭代9 e7 o! u, P$ d* _. ~
    尾递归优化可以提升效率(但Python不支持)
    4 |2 v: O6 r% e& G( W& M5 q& R; m  o0 i& C, ?# ?
    递归 vs 迭代$ ~0 Y( r3 P  h+ ~' r" v
    |          | 递归                          | 迭代               |
    4 V) u$ K. X! D- l: m# Z' ]|----------|-----------------------------|------------------|) b/ |: l7 a" _
    | 实现方式    | 函数自调用                        | 循环结构            |9 M% o; D2 o# m% a8 ]
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |# ~7 b1 _6 d/ S
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |" V9 e. u+ G0 F3 ^
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    7 I$ G% p% a' }% `/ H0 I; F' v
    1 O3 g& L1 ?4 N7 G; f 经典递归应用场景! }. p9 f3 q. u+ _5 l
    1. 文件系统遍历(目录树结构)( _3 Q9 Z% ?1 G* M
    2. 快速排序/归并排序算法$ S7 _* D, i* r1 I. Z$ k
    3. 汉诺塔问题
    * s( Q" F: c  W5 i4 P4. 二叉树遍历(前序/中序/后序)1 F+ ]& r- ?& W# f6 o! b! x- @  e
    5. 生成所有可能的组合(回溯算法)
    ' a% p  l. j0 O( h$ B8 ~- Q1 p0 ^; o) I( t
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    开心
    前天 06:54
  • 签到天数: 3210 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    , D( k* N- N4 w" ?; ?我推理机的核心算法应该是二叉树遍历的变种。
    3 A6 R# |0 j% H另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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( I" N" ?' I$ q! X4 OKey Idea of Recursion, {$ I& |# X. `

      }5 f' c, g& Y. XA recursive function solves a problem by:1 f' B  G& D. u* [# O' ]2 a

    : I% h  {" }" c4 Q6 L. o* E    Breaking the problem into smaller instances of the same problem.
    5 U& F% d% T* F3 `' U" N7 Z- F0 B2 X% ]& u7 Z8 [' ]3 b9 r, Q1 Y0 A2 y
        Solving the smallest instance directly (base case).( m+ F0 R( Q0 n, h" W" m4 t* [
    + P) {0 w* z7 T' W  c
        Combining the results of smaller instances to solve the larger problem.
    0 w. O7 I# t7 {* V& w" j/ v; K- }" `! Z' j8 S( P- k
    Components of a Recursive Function, ]3 z, y6 t7 i+ }! k) ~5 t' g

    ( W) U# k4 A; L; q# @    Base Case:
    3 D5 a$ [$ ^# J" N$ f* f/ v4 H4 Z* S7 c) }
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    1 P/ |- W$ @( O8 j/ f& \) o( y' O. W4 U" }7 G
            It acts as the stopping condition to prevent infinite recursion.
    3 T  L3 M* u* c, Q6 v0 ], L
    # U% G8 {5 r$ v        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    , L$ B; w! f. ]8 L
      t. e: O! i" [0 Z3 i, ~" w. M0 A- E    Recursive Case:
    , k1 I  I3 H' e% J5 p
    . p7 C4 I9 w1 }( p3 g0 Z% C1 N        This is where the function calls itself with a smaller or simpler version of the problem.# k! N, j9 i( I! z
    2 m$ X* Q- \- ?2 q4 C5 v
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    3 ?9 m% I1 g1 z" y! ~# m+ ^, m& S7 M
    Example: Factorial Calculation
    ; u  h7 `  b7 S: O: ^3 k9 {8 G
    " u' ^% G3 B1 v, e& zThe 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( @) @; x+ S) i2 l. j# }5 g8 C! ?3 J7 N& b: ^8 `  u/ V
        Base case: 0! = 1
    7 j- g/ N, U+ {: g8 S; q5 p- L0 |* I& \( e$ G$ F
        Recursive case: n! = n * (n-1)!
    0 t) d- K9 G- y( \4 V! w! C+ [% f$ {/ k
    Here’s how it looks in code (Python):$ n+ @$ |/ w6 B% W, R
    python
    , g1 f7 I* V8 Y: y. k, |  q
    / n6 ?: r& h6 L# g- S. c$ Y. z0 c& u% ]4 c* j" r( w% U- G
    def factorial(n):( t/ [" w) [9 w( }6 O+ M! }) x8 o
        # Base case
    3 ?3 L& y* N, o# b6 Q    if n == 0:
    ; Q3 _  R- j$ o, E        return 1
    9 v/ q4 |) x) k0 w  w6 L3 \5 C    # Recursive case# ~# Q: F8 u( O, K: {, Z
        else:" o! ?; B( J3 S* N% @# r8 M
            return n * factorial(n - 1)
    " f( V" S5 M- x) \1 M
    , O. p& |8 A: ]4 c. E$ e3 y, |! V# Example usage
    & ?" s( ?0 M, \, p, Z; bprint(factorial(5))  # Output: 120  X9 Y# h1 u! X. o) ]% ~* l, [
    4 {. ]# x8 K' b* ^6 ^' p. g
    How Recursion Works0 [" c9 Z! E1 ]/ J
    & @' s+ d/ D% |
        The function keeps calling itself with smaller inputs until it reaches the base case.
    2 i4 [1 ^6 L# c8 K0 O* d- R, X% @
    - m# L0 p; V. R( @    Once the base case is reached, the function starts returning values back up the call stack.2 D" _: I  H* I1 h
    3 G* O# J( W, m6 j- A& W) B: q
        These returned values are combined to produce the final result.- q1 T) e5 b2 ~
    - |1 S0 H$ g' J2 O: }6 S. T5 o
    For factorial(5):( [" y, W  n  q& M: U( d

    ( U, c  U# B( c  P5 E3 n2 O% B1 w" c- Z9 T" i
    factorial(5) = 5 * factorial(4)
    # i5 k* ~- D- V) y; A1 [factorial(4) = 4 * factorial(3)
    ; r5 r) @+ ]- U) a: F& r5 o* sfactorial(3) = 3 * factorial(2)' F+ D  E+ m" o" k+ p1 |
    factorial(2) = 2 * factorial(1)5 a, B2 h) I! {- u& Y
    factorial(1) = 1 * factorial(0)& P: L$ ~4 L1 Z. T6 S
    factorial(0) = 1  # Base case& i/ C3 c4 |2 X! X8 L+ L
    - O  I  F0 R/ U
    Then, the results are combined:4 ^& J, F- M& V0 O+ }
    % k% c; T3 `4 L; i
    ; e; f% ~; w! J: G3 O/ X; V
    factorial(1) = 1 * 1 = 1
    & q4 r; ?  l  J5 Qfactorial(2) = 2 * 1 = 2
    * K) d+ ^& H& q9 [1 J; \factorial(3) = 3 * 2 = 6$ ^8 p# j4 M0 N$ N
    factorial(4) = 4 * 6 = 24
    8 W* y; k8 ?  x6 c, Pfactorial(5) = 5 * 24 = 1202 n+ e- e4 c8 ~1 |# a& d- C0 w

    5 n7 R$ m8 j* z7 I5 JAdvantages of Recursion
    " O; ^6 d7 z) _9 }" k
    3 C5 v: |# Z6 s7 u; _* W" P! \    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).! D) R' O) w5 v, d4 f4 N+ O- T
    0 f( e! N* [# I+ i0 M8 `
        Readability: Recursive code can be more readable and concise compared to iterative solutions.1 k, e1 V# g3 C& N: m1 w; W
    % V$ o- |6 e* y$ h, ~7 _7 M
    Disadvantages of Recursion( A: ^' O( F: [! I9 \" h
    1 y2 l. z- ?- @
        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.; u2 _  v& ]7 R* e& z/ J, i
    $ b! b1 B" {% h' N
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).: h% Q2 y' \3 Y4 N) H

    : O6 Q- }5 J( K8 Y$ l" e/ vWhen to Use Recursion$ g; L+ x  a4 n. G( a  |8 p
    ! e# V6 X$ t* }# a$ d' H! z
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).% ~& [# f8 }% _) y3 P
    1 `6 Q1 G4 p  L% f
        Problems with a clear base case and recursive case.' {! ^: M. T( z6 E6 g$ i
    & I# t6 R/ l3 ], s1 v/ `
    Example: Fibonacci Sequence
    ; i- T2 N1 R1 k- G: f* C! A. q. [- i& m! u4 v; P2 k, Z; b
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    , ]. g/ U% c7 a7 F; N
    0 U' |8 Y& d0 [' H% e$ B, r    Base case: fib(0) = 0, fib(1) = 1
    9 w5 i) @4 ~2 j: _2 V3 e: G7 N  ?6 R
    3 v' o6 W! k+ r- b: t    Recursive case: fib(n) = fib(n-1) + fib(n-2)' x+ n/ m9 T" j4 E
    ) e. n- ^" C# e; r) w8 H5 C
    python" g9 e7 H) n9 a+ n6 ?6 J8 s$ b
    : r# D0 g7 Z4 I

    " }0 N+ H$ Y! Rdef fibonacci(n):
    " Q! U. U5 r0 k8 T3 w, f* F" ]    # Base cases
    # [* h5 \/ i! `, f    if n == 0:
    7 G+ \0 @9 X) f6 Z: _! w& |' h* Y        return 02 F7 S9 Q* k' Y( _+ b- j
        elif n == 1:
    # V* o! z$ F( m! z3 ]* P        return 1
    , ^  R4 }( Q; b, I  x: \    # Recursive case
    4 @( p1 i) V- o    else:9 y  {9 n1 S- B$ J3 ^* C& F
            return fibonacci(n - 1) + fibonacci(n - 2)
    1 m  o( F# V7 w8 }6 t) z$ u7 O/ }' ~* x: M: ?0 b
    # Example usage
      w1 m/ ?/ z. x# f" `( Tprint(fibonacci(6))  # Output: 8; S& B4 A4 v6 p2 x& U7 ^
    ) |6 m/ I/ B* V' Y! k3 p- k/ O
    Tail Recursion# h- r. y7 d( L9 W2 i: M! w
    ( ^3 n1 c" g/ G. f; }. R3 G
    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).
    6 h  _( {. I. g/ d+ i- |$ P6 L/ d6 x9 m, `0 n( |. K2 B( O6 Q' u
    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-2 23:09 , Processed in 0.069735 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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