设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    2 |+ [4 c! e8 ?- b2 k
    6 V5 J3 @$ @9 c3 a' P2 C& y5 H解释的不错/ @2 I* T4 L0 g
    6 \: I2 m* C* I! w' ^+ ]! V
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。, V* s" V4 V! l5 \: D; Y# i
    1 z  \- c# m- X0 r
    关键要素6 t  {5 p( {9 w5 w" o. h
    1. **基线条件(Base Case)**
    . O5 c: ?: F, I   - 递归终止的条件,防止无限循环
    . u& F9 {5 j! ~& |. t   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 17 S- T; ]: Y5 W# t, \

    . v- X5 B% M* f* h: X5 B" x, b2. **递归条件(Recursive Case)**' r  m% g) B7 v9 X
       - 将原问题分解为更小的子问题
    ) _6 c/ u% k! t! p   - 例如:n! = n × (n-1)!
    ) f' q4 U! T1 v4 v
    ! [9 x- a/ [  } 经典示例:计算阶乘
    ' \3 O9 O% v6 ^1 f! M2 [python
    8 q2 L4 O4 ^& ?9 tdef factorial(n):" a- R/ |0 U" |5 O6 N* r* I  C- i- }
        if n == 0:        # 基线条件
    ' w9 g! y5 @( l! C! a, _        return 1
    3 W( j" I, d5 E" {5 ?, r    else:             # 递归条件! p+ v. }2 Z) g8 ]4 x2 u- @
            return n * factorial(n-1)
    $ Q# T; t, o6 @# ?执行过程(以计算 3! 为例):
    8 W6 C0 ?) f/ c5 j  Q( d) q0 }- tfactorial(3)
    ' }- ~. i! z3 p$ R- o- u& x, p3 * factorial(2)! |0 H* `% s+ v% M( x9 B
    3 * (2 * factorial(1))
    & z) \  a# _  I1 F+ C9 u3 * (2 * (1 * factorial(0)))5 G5 ^5 T' T5 r& ~
    3 * (2 * (1 * 1)) = 60 R) r& w1 A% a' d* |* R

    5 c) ?3 p0 ]7 V. w9 u 递归思维要点
    " R0 a; u# j! l* B4 K1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    3 g: N$ y% T" w: A& c2. **栈结构**:每次调用都会创建新的栈帧(内存空间)9 n  r, v5 u; ], I, `
    3. **递推过程**:不断向下分解问题(递)
    + `6 c" N/ Z( E" U5 t4. **回溯过程**:组合子问题结果返回(归)" l, p5 N0 }  D; ~/ @
    6 Q' l  @9 w9 I4 B) J" b) [
    注意事项
    + i7 q9 A2 {( X* g$ c! j: _必须要有终止条件5 c$ J9 H. S4 k5 U/ i5 B' T4 z* S
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    . x% f9 V! J6 B# c9 A某些问题用递归更直观(如树遍历),但效率可能不如迭代
    # H8 {& E9 S+ c4 C* I# M4 }  O尾递归优化可以提升效率(但Python不支持)
    % z5 x) s: h* o0 ]6 ~& Z* p' G+ _  u; Q; y9 g9 G1 A9 n8 G" a
    递归 vs 迭代
    " B& G2 F" w0 U- I  ~|          | 递归                          | 迭代               |  |* O/ t! R! I/ g4 Q
    |----------|-----------------------------|------------------|  q& e. T* q! f  V) z
    | 实现方式    | 函数自调用                        | 循环结构            |! K. u7 g0 M) e" V9 B
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    6 a2 G2 q9 D# n| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |8 t8 |7 d1 M4 J
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |7 B) z* ?" F7 r9 @* z

    ) [- K% w2 s9 z) E 经典递归应用场景
    2 {2 p: Y1 z' H4 j1. 文件系统遍历(目录树结构)! {- F6 q* n9 N9 J( l) W  z
    2. 快速排序/归并排序算法
    / ~# n$ @5 R" k% L3. 汉诺塔问题
    # i9 ^, {7 i- I* [* D8 t+ I4. 二叉树遍历(前序/中序/后序)) Z) T. O3 {. d: M. b& B
    5. 生成所有可能的组合(回溯算法)
    / w8 t5 [6 P( q; }& r- |  Z: O; `  v2 h' k5 h* e0 a/ {$ R
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,9 f  ~2 K5 t$ L8 w( r& F8 G' r7 v/ G* L
    我推理机的核心算法应该是二叉树遍历的变种。' ?0 H" u# h9 M. o( y
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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 Q' i3 F# t9 a9 l; Y
    Key Idea of Recursion
    ; N0 B3 n/ V) K
    % P9 B' t3 |2 {, j" S# H3 I: ?( iA recursive function solves a problem by:2 P/ V( g; }9 B3 d- s6 C

    " I! u3 J* i4 ^. x2 ^    Breaking the problem into smaller instances of the same problem.
    ( t/ O# F6 `7 T* ]+ h7 ]7 U+ L) z4 H0 H. X1 U3 N
        Solving the smallest instance directly (base case).7 z3 g: e8 e" f* y) b7 p. s& i  V

    1 g6 V0 c, r; g5 l1 A! o" K    Combining the results of smaller instances to solve the larger problem.# x8 W# w) f! a7 \& P, h( i0 O

    $ V$ K% {, N1 @) w! WComponents of a Recursive Function3 T9 o5 d( Z( L" r& \* c8 r
    1 c  A6 `4 a( n6 T2 J( y1 N  ^! e
        Base Case:4 d& S0 g6 Z& L; T- P& w; b" V

    " p, w8 Z8 y9 K' e6 \        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.# Y$ A) u+ [4 ^! X/ ^

    ' J( V3 G3 D5 N2 ~+ ]        It acts as the stopping condition to prevent infinite recursion., f" o) p5 h- C8 Q+ U# |$ G
    ( `* g; j2 i# Q3 n) K. y
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.( w: b; B1 u3 Y/ J% i
    ; ]+ ~, p3 ^- T6 [) a+ i
        Recursive Case:7 i/ [; j* T: G; [) E/ J
    8 _( x% Y; ?6 {( W$ o
            This is where the function calls itself with a smaller or simpler version of the problem.
    8 `" g5 U; F* K! H( k, ]$ s  v6 S0 Z$ W$ k) [; ?
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    # {8 C3 p. K& C: I, G! N# @$ e* X8 R# @; Y/ A
    Example: Factorial Calculation( b4 l8 l2 K0 T5 Y3 s

    - u2 h) d' U  G, b  i5 J2 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:5 b* C5 I- n, i* O# q2 ?: [
    3 i+ m  s- A  t8 K, J- l
        Base case: 0! = 1
    % E; }0 i# l0 w
    8 Q# c. X  G1 L# W" B    Recursive case: n! = n * (n-1)!- A! a7 Y5 Q4 k8 V8 n
    - v* M! V: F2 A9 L8 `# M% |* W
    Here’s how it looks in code (Python):* @9 y3 {  V  D$ {) @- N
    python
    # N9 p' v  B" _. Z3 k0 t1 b0 y- l  Z% V8 Y

    $ Q" U) e# {! p( Q  wdef factorial(n):
    ( @9 L# G8 O3 [" P    # Base case# e3 r) b" g# T1 b: A$ x% S
        if n == 0:: G" T( C. [: g
            return 1" _, ~! y- a) n3 o2 |
        # Recursive case
    ( k7 R, x6 p0 o: u1 Q2 h    else:
    + A$ Q  {& n! x( J6 x# ~        return n * factorial(n - 1), u, j$ }+ E, o4 Y' G6 Z7 X

    5 ^; C) ^$ N7 ~# Example usage1 w2 r; U6 a2 L4 g, x! n
    print(factorial(5))  # Output: 120
    ( m$ Q6 `; e# u" b* h1 O; h0 m, F
    How Recursion Works
    / \( v9 |( e1 G3 n. p. D9 i3 c6 I5 ]+ i- D
        The function keeps calling itself with smaller inputs until it reaches the base case.
    9 d# |# Q5 O' ]" |$ P$ `' V) c& h" W( D- z
        Once the base case is reached, the function starts returning values back up the call stack.
    8 w# @! o( {+ d( l4 i7 C
    4 M% e* H1 J, S. ~  t* t    These returned values are combined to produce the final result.
    " t2 P. n! ]0 B( o  q: o+ ]2 \- z8 x( i9 I4 ]: g
    For factorial(5):  T; I+ C/ P# n  K/ P" o

    + _/ Q7 O7 S& {: k" }/ j- m
    2 n% ?5 E" G9 `factorial(5) = 5 * factorial(4)  `9 M( C- G4 f. F9 c2 M
    factorial(4) = 4 * factorial(3)
    . x! r, ]; ^- B  d# j. tfactorial(3) = 3 * factorial(2), O* P! G- N. b3 L9 C3 j
    factorial(2) = 2 * factorial(1)
    ) i% R. ^( Z; ~3 ^, rfactorial(1) = 1 * factorial(0)# g9 n. |$ t2 n* C
    factorial(0) = 1  # Base case2 f% T" Z3 B- y: C: K7 V
      G) \6 y: A6 D, s4 p$ R. v
    Then, the results are combined:
    , v& @* c* u  ]1 v8 ^
    0 T4 A" L  B2 ?! U7 O9 d) ]
    - k& {% K6 ~9 ?" ?factorial(1) = 1 * 1 = 1- U  g3 L, t" ^9 q6 T
    factorial(2) = 2 * 1 = 2$ y  o+ m. p' `9 Q
    factorial(3) = 3 * 2 = 6
    - o! Q+ M# k' I+ \: ]8 z3 H4 ^: @$ xfactorial(4) = 4 * 6 = 24# L7 A' P: p" ?6 b& z
    factorial(5) = 5 * 24 = 120
    , l9 G* q8 H% `4 Z3 i8 L# ^1 `, i6 Z
    Advantages of Recursion  b, \# F, ~( B% m$ Z& s6 T: J) ^

    ! j2 _( {: \6 V- L8 n* t4 M    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).
    & O, z! ?6 O& y3 `# N6 |
    ' j1 u& L+ U& m+ t* p4 W! S    Readability: Recursive code can be more readable and concise compared to iterative solutions.: ]# j9 S9 p; o. J. z# @' o" L
    ' e- v+ [; i" l" i+ c2 i
    Disadvantages of Recursion6 V7 d6 ~, R5 j7 ?$ p* s( x

    ) r& ]0 Q4 o: x- k4 y/ k+ q    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.5 i+ e% J, b  R4 n: e% p
    . g# g" X2 t# e) h- a: y. e
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).1 ~4 |) m! u- T0 K

    " ?! S# m7 r/ X$ y% h5 WWhen to Use Recursion
      K1 S% O% K+ ?" f+ D9 z3 O
    " m0 U' [4 y1 z% y    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).: `4 ~5 h* X7 V, H) f

    ; \( t9 A8 d4 G( O% @0 r    Problems with a clear base case and recursive case.
    8 y$ y! s" T5 d6 J) Q7 k! U
    $ R3 {% G  f" _: u+ S8 TExample: Fibonacci Sequence& ?1 g- H  Q% G" P3 x, r
    ) C: L, f# s+ L5 [, h- D$ K( b
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    6 P& |/ S0 q( z8 f$ }) {* H& e* a. y; h3 x% [/ {) s6 r  e
        Base case: fib(0) = 0, fib(1) = 14 v! J* C3 L& f

    # Q9 s; p* V$ {  W+ O6 N4 R7 s8 E    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    6 E  O" j+ W! T3 I1 y: h2 f; \6 B
    python
    : N) D/ F/ S) C3 r1 H5 L
    * q+ a& g; U# q: |; O9 S2 a, [/ T
    ) z9 M1 Y. C7 i6 L1 K: r7 q& Rdef fibonacci(n):9 X0 ^/ M; [% A" F: `
        # Base cases: r8 M& j# d$ B# z& @
        if n == 0:
    6 k: |2 j4 _- u) s7 [; d' G, b        return 0
    ( }% B6 |5 c% N/ a' U! a+ g    elif n == 1:
    % n% h! ~1 V+ E$ W; g0 w) l$ r: V- v        return 1
    ) o+ A" S" k2 `/ s; ~7 w2 u! s    # Recursive case6 d: y3 [$ {$ B) F) p
        else:' a0 N1 t6 h5 S9 h+ M7 o
            return fibonacci(n - 1) + fibonacci(n - 2)/ L' c2 q: K% u1 o6 _. `

    9 G0 p1 n2 R4 H! [) ^) o# Example usage
    & ?+ H' [: M- g$ j# hprint(fibonacci(6))  # Output: 8! S2 N' T0 Y0 w5 @$ N5 P
      E( F' ?8 @- P3 g, }
    Tail Recursion# f+ S. H( U) h& M& s4 v% i

    5 Z2 Y$ `" u" @; dTail 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).
    * ^- U' v. l8 ^/ G3 s
    ' M8 w7 B: G- LIn 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-12-24 18:32 , Processed in 0.032791 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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