设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    , @) U$ N8 o( _7 W/ [
    ( ^1 `0 Y% c; P9 B, B' D解释的不错
    2 b8 |! Q/ D' K$ t
    - Q3 [( k7 c& T- Y$ J% s递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。* X$ A8 `1 \, P7 w! t6 Q3 @* g  Q5 V

    + y! M; e( ]( |1 l" V 关键要素, Q6 W$ k* f* H6 F4 p+ Z
    1. **基线条件(Base Case)**
    % \& j% T0 F: d) Q" Z/ D5 `1 Q/ a" e   - 递归终止的条件,防止无限循环* D, z' M- U# n3 `, }
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    ; p& j8 [/ m1 H8 x- q
    1 s! w& W3 a8 t8 ~5 E7 L2. **递归条件(Recursive Case)**/ b& }' W9 ?0 l! H, }. d; {8 ]
       - 将原问题分解为更小的子问题
    6 X6 g+ X; }. M) v4 a9 T: H4 [   - 例如:n! = n × (n-1)!: N" Z  V! n4 D1 T* s( E7 U

    0 w" j- b8 a: U8 v" b/ g6 X8 |8 f 经典示例:计算阶乘9 M0 w4 y: }6 Q) H7 q- R
    python
    1 X9 T, C8 S8 X7 D, edef factorial(n):7 s  }5 d0 L' }& f8 J. N
        if n == 0:        # 基线条件
    4 S  i, z6 [3 y5 l; E( j4 i        return 1
    4 z1 u% Z; e6 n( z0 `    else:             # 递归条件
    1 ?5 q: b" l& c, H2 g- z        return n * factorial(n-1)* D% F9 X: |  B  q
    执行过程(以计算 3! 为例):. T5 {, P/ G  B- k) Y  n1 k
    factorial(3)$ o7 ?- J- g+ }# L& N' ?% n
    3 * factorial(2)* T& @- n$ r8 d0 T; A# v( s
    3 * (2 * factorial(1))/ _& U% l7 x( g4 G. _
    3 * (2 * (1 * factorial(0)))2 _/ t, `. k/ J* a) n
    3 * (2 * (1 * 1)) = 68 [4 [. _- `1 T2 A* N4 K; T
    " T! p8 t+ U/ b
    递归思维要点' \/ U3 I, U! ?8 ^1 k4 z
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑8 I4 S% R4 F: a; L: {
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    ' Z( ^/ j2 R- ]/ u5 b3. **递推过程**:不断向下分解问题(递)9 h  ^4 m" l3 M9 ^# M0 q
    4. **回溯过程**:组合子问题结果返回(归)
    1 N! `8 L, l. n& Q( S3 v: E
    + f# W6 w! ?; w- P 注意事项
    1 p* R. f& A/ A, p必须要有终止条件
      }: ?3 s5 U" ^6 o递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    3 D& n! c5 B5 U! W, [: W/ \某些问题用递归更直观(如树遍历),但效率可能不如迭代
    * c  k% `4 d1 M: K7 L& r3 c+ w1 R尾递归优化可以提升效率(但Python不支持)  z2 `5 u  R! G2 n9 L5 p

    / X, k9 k  _2 T# P3 {$ |% j4 T6 z: x 递归 vs 迭代# \# f/ c, \2 l/ o7 n2 D
    |          | 递归                          | 迭代               |
    . h" [, v( d0 {, F6 m) U|----------|-----------------------------|------------------|
    ( W( ^- K" o( H( D$ @" e: N| 实现方式    | 函数自调用                        | 循环结构            |! \9 Y8 ^1 w' O# S) I
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    7 A, i  K# i6 Y$ T) N& U& Y| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |( `- \2 V3 o4 Q4 I% h# O4 t
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    / |  X- U2 l& J' U$ W
    ; }; _$ L8 r# D% j$ x 经典递归应用场景
    - D6 K% f9 _4 H3 G- J$ v1. 文件系统遍历(目录树结构)
    4 q% r8 W0 T5 c9 z' @2 w6 o2. 快速排序/归并排序算法( o" b* t$ B! F. V5 u5 R7 F
    3. 汉诺塔问题/ X3 n( m6 a! @! u
    4. 二叉树遍历(前序/中序/后序)
    ! t; t' C& m/ m  j2 G5 f5. 生成所有可能的组合(回溯算法)
    ) Y- u1 }6 f0 k1 q. ^
    7 c" W1 F, U! h试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    , P8 O2 S8 x# t" r- S% n. ?9 O我推理机的核心算法应该是二叉树遍历的变种。
    0 |: m; C4 i! E0 k6 m8 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:- m7 _9 R" u  t4 k9 `
    Key Idea of Recursion$ ]0 @; ?* H( w$ p

    $ r$ A( D' ]0 T+ ~+ b( T( f8 nA recursive function solves a problem by:
    ' X4 {: n, m2 V  z( i4 f9 g; A
    # V& N" y' L4 M8 R    Breaking the problem into smaller instances of the same problem.
    3 M3 ?) ~  Z& h8 U$ o: g; G8 d" U
    * P: F1 \6 p0 G& f2 A: _! d% i    Solving the smallest instance directly (base case).; T- L& U2 U: m$ w& S3 k

    5 L& N; e& m( d    Combining the results of smaller instances to solve the larger problem.7 C; E: ~( K$ c! o

    / F) G" Z7 s# s4 IComponents of a Recursive Function5 W( j- E; C5 v/ b3 }4 n

    2 P8 `2 w$ F# h( }    Base Case:
    2 R' K" D" J) E) l
    6 @, z/ O. d* r3 S& B) O        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    0 Q" w* J& V% D* X* q/ V# y
    0 n6 p' ^& g0 f: _& p2 l        It acts as the stopping condition to prevent infinite recursion.4 o. Z+ I5 f' h% A/ O) l
    - k" T0 K. U- v; x" J
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    / {2 _0 b7 v3 t1 I* K. g+ @0 k7 \' I
        Recursive Case:
    ; R- U0 C) c& G: [1 [0 t9 U/ M/ r& r  W1 U3 o! `& V1 T9 @
            This is where the function calls itself with a smaller or simpler version of the problem.
    3 ]& d6 Z  |/ L5 ~7 }7 T1 i
    5 I' Z# I. k9 t; M# K; o        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).( o; V5 G$ L6 \% g, X' ]
    ( n( C3 @- o3 h' |6 V
    Example: Factorial Calculation
    , h$ X; F+ A8 n0 p2 L, s
    3 i& t+ [) A( c* }( S+ fThe 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:8 R1 y& N: S. ^" L4 h
    / Q( b" m4 C* m
        Base case: 0! = 1- X( C3 C: O! R! t

    6 C8 T" O" G* q: A% a$ v1 y% m; }    Recursive case: n! = n * (n-1)!; \( d0 Y$ S4 Q
    ( U2 X& x6 d. a" p% t( r
    Here’s how it looks in code (Python):
    # e2 H  s: D. `+ w8 ?python
    , P7 [# \% P! `- a6 |* b. A( H5 y" C7 _% E9 n: V& g# k9 B

    1 f( ?- t3 Z4 a3 c9 Wdef factorial(n):7 q8 l, |% n% w% w) _2 H# \9 ~
        # Base case  H- J9 c( H1 j- e
        if n == 0:3 y' n9 l% l7 D
            return 1
    / N* E2 J& |% h9 P/ ~) n0 ?    # Recursive case
    / M0 J1 Z2 x, P- S) R    else:, {3 E) F' x. G  c7 q/ N& O
            return n * factorial(n - 1)" ?! u% }% f% j( |( x

    8 d. a2 ]! H$ K$ p  a! b; {! ^# Example usage& v: M' y1 w; T6 @
    print(factorial(5))  # Output: 120
    1 N# Y$ K+ _# Y: [
    3 n: N& }' @" vHow Recursion Works
    . L- |9 U: f& I0 S2 T$ V( l4 ]. H- w$ @* T( @$ C& l& q2 Z8 x
        The function keeps calling itself with smaller inputs until it reaches the base case.6 t/ k7 {4 b7 ]  p
    $ G) O1 [" _# y9 r* D' |0 j
        Once the base case is reached, the function starts returning values back up the call stack./ S( C$ z8 e6 d5 }
    9 O4 j( f4 a4 n# v  M4 T/ `) J+ H7 F
        These returned values are combined to produce the final result.% n# \. e( t; ^3 Q/ b6 _0 \/ d6 Q2 G4 m

    ( R' L: w, Y4 K4 j; HFor factorial(5):* A6 j' A4 C: `8 t; u7 ]

    - G  {0 z$ e: c. F+ s% m
    8 {- ]- G4 d3 s$ t; g( \9 dfactorial(5) = 5 * factorial(4)& c9 g3 U% d: \6 m$ q( ~
    factorial(4) = 4 * factorial(3)
    - w% x6 l6 c; ^2 t+ _% @  o6 hfactorial(3) = 3 * factorial(2)3 V( ?4 u8 o3 O8 _- Q
    factorial(2) = 2 * factorial(1)3 {$ A& d9 m* p* O
    factorial(1) = 1 * factorial(0)
    1 Z: ?/ |3 A; y9 o$ I2 yfactorial(0) = 1  # Base case( G, L# E' p- y: v" Z% O+ n
    ( ]" b( q; P8 z9 N
    Then, the results are combined:
    : G9 _" O0 N8 Y1 M
    8 S4 |) l- n+ E
    - j; F5 P$ N/ M# N5 qfactorial(1) = 1 * 1 = 1
    1 M  C6 f" o/ ^, E. H8 q) s7 ?7 _factorial(2) = 2 * 1 = 2
    ) d: q2 m$ b5 ]8 B& j- ofactorial(3) = 3 * 2 = 6
    8 n$ l- k- X: v: d% _% L. ffactorial(4) = 4 * 6 = 24
    4 [, O( @3 F/ @7 l- |) j, tfactorial(5) = 5 * 24 = 1203 @4 X3 P+ u* Q: J. D7 M
    6 Z7 e2 b  O: t8 b/ w4 J4 L
    Advantages of Recursion7 H/ W/ A) O; U

    . t7 f# f. \1 b% u9 ^- [& v    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% C0 |9 k7 u$ [$ @5 V$ R- F  H: V. Z3 s: p/ P3 \; W: a8 V
        Readability: Recursive code can be more readable and concise compared to iterative solutions.( p3 \) x# A: g" Q# R) ]1 J
    ( S' @7 H6 J5 A) L, ]. E
    Disadvantages of Recursion3 v, O$ T, T* \2 k+ M( y

    ! E/ }' ]6 i/ o* s8 g% z6 ?    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.
    , ]# ~# Y( |5 p+ S4 j9 B/ ^6 r0 z& m" s/ U! o8 V
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).$ Z: u" x% R' ]: H- `3 s* d: g
    , S$ d: O% q, l5 X# Z6 A% C! P
    When to Use Recursion0 d2 w7 L8 Y. C3 P# p2 X; _

    - p+ ^" h0 H( L% S) p    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).8 W/ I- T# M0 a5 K. ]4 a
    ; a9 F# v9 \; Z( {- z& t
        Problems with a clear base case and recursive case.
    : _0 [/ x3 \& V
    % `% y5 C8 }; Z. TExample: Fibonacci Sequence- C) S$ v* v; o: \9 @) t6 ^: M
    ' s4 T2 T: I" m2 m5 |
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    % G! v6 n) H# I& L$ x. }! C. V+ N) h' v: o9 Y' x
        Base case: fib(0) = 0, fib(1) = 1
    ' [: Y% S1 @5 H! f/ U2 b
    . X% B( J- }0 Q# B7 ], [  C    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ' v; n) n8 T) _! R9 W3 h& }7 f
    python
    7 w8 R- X# \, d; L( F2 f/ M8 r
    " E( ~# V+ o: j- `. R9 R+ Q$ U: I+ L1 E
    def fibonacci(n):
    9 n2 n' H# A% }! {- |. C    # Base cases  W% \% M" \7 S2 x; B
        if n == 0:1 ?" M/ X6 |% ~8 c, b! B& r
            return 0
    1 \5 B5 u3 C" D: ?4 o, q. R    elif n == 1:$ i) B4 c; h' v3 I8 V! z& y
            return 1
    + _* F' n9 z, ]    # Recursive case( u2 U: ~( j% y2 [+ Q
        else:& D/ g. s* N& V$ Q4 C8 N( }
            return fibonacci(n - 1) + fibonacci(n - 2); I  O9 ~" }8 G) S

    " Z5 K( K# ?$ i- I" O- Y+ c# Example usage
    1 i  O# ^' |  j$ x; k4 Eprint(fibonacci(6))  # Output: 83 Q) z/ [* L  T/ m. q

    6 U! x7 U" e( \2 KTail Recursion+ O5 K, Q2 D, t) V* w* m

    ( @2 C4 u9 s/ t7 ~/ Y  g% `/ v+ q2 hTail 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).& V, |1 k' L' x, N
    + l+ p" t; L3 U) G0 s( I: M, g
    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-3-10 19:30 , Processed in 0.075945 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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