设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ) u/ U2 U9 G! V$ w5 o, z% j& `8 G& g. [- m6 H" ^' P( e) _
    解释的不错. U+ e5 ~& X+ X6 I

    ; y# u  F% s6 k; j5 H- S4 p递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    . j  z6 c( A* _% L" a
    3 I8 k$ x; k; H: \5 m 关键要素
    4 B5 X! j  v( y# L% V) g  Z$ }0 P1. **基线条件(Base Case)**& T) [$ U0 o# }7 y! \5 w$ a" X
       - 递归终止的条件,防止无限循环
    : f3 E' N3 @: j  b   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1+ h4 V9 u6 X4 |+ B1 g
    9 Q) m4 d7 S9 p! f+ s
    2. **递归条件(Recursive Case)**
    7 \9 n, o" D6 s9 x. ?1 F   - 将原问题分解为更小的子问题3 Q" x3 h# \$ v2 N4 x4 E3 ]% t
       - 例如:n! = n × (n-1)!7 z5 Y8 w$ g* [$ ~' c

    1 N; j( r5 ~' j9 r. m7 o# T 经典示例:计算阶乘
    # e; E% N- ?9 ~# I$ \7 jpython
    8 }- [/ E. ~8 \' z, B" {  vdef factorial(n):
    % i& p4 ]+ I! Z0 ]8 L9 D5 b    if n == 0:        # 基线条件
    7 v8 M* j' J, W) Q( `        return 19 Q/ l4 l* S/ E% B+ {- {
        else:             # 递归条件: y1 {- T- F$ |. g, O' _
            return n * factorial(n-1)
    3 [8 I! e% u1 o/ ^& {执行过程(以计算 3! 为例):$ E# [: c, t6 H/ n+ D8 R" Y8 @
    factorial(3)& c% h( F8 f' u2 I. V: v
    3 * factorial(2)
      L( D' r. }( y" f  A  l1 x7 x3 r3 * (2 * factorial(1))
      S2 j0 G. I8 T* \% D1 n3 ~. i3 * (2 * (1 * factorial(0)))
    - ^# E2 b: o% M& @4 |3 * (2 * (1 * 1)) = 6
    ; Y9 q5 X$ `- b  E7 l9 ~
    . o4 l( {6 i1 C- X 递归思维要点( V6 M7 T) s$ b9 p
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑+ `8 G% \: d! ]8 Y7 ~
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    / L* j4 m* V' J" Y' n8 c3. **递推过程**:不断向下分解问题(递)' a( j4 W; @- {! @: b
    4. **回溯过程**:组合子问题结果返回(归)
    : _4 a2 b: {5 s) ~3 a" b
    % P7 `' z, @4 L+ A 注意事项9 f% N% V- h; e1 a4 T" a' ]
    必须要有终止条件
    % f; C& D; N# z, ]/ A( `/ t, g递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    5 }) n0 l# M* d! k3 Q& m* K- X某些问题用递归更直观(如树遍历),但效率可能不如迭代) v, T  b$ a1 W, x* }1 m. M
    尾递归优化可以提升效率(但Python不支持)' ^% P# x: ^2 i0 A8 M  ?
    + \1 e: ?- u5 e, p* D; \, C+ i
    递归 vs 迭代5 K2 u3 _7 I! J
    |          | 递归                          | 迭代               |, \8 S9 C2 j) h1 E3 J
    |----------|-----------------------------|------------------|
    ) B( G2 I4 C" H9 G) `7 k| 实现方式    | 函数自调用                        | 循环结构            |
    & g+ ?% w9 R$ @# s. V* G( @| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |6 g$ E: n7 D! P0 T, E
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    2 R9 Y9 x' U+ C" B| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |& V; T6 O2 R! `6 B, L7 @4 v+ A, `

    - j4 d) Y! e0 V, ?6 ` 经典递归应用场景% ?; _* G* R' g+ n3 |2 C
    1. 文件系统遍历(目录树结构)
    ( _* w; i( |, W, L6 d2. 快速排序/归并排序算法% p3 b2 C" Q7 x9 x0 E
    3. 汉诺塔问题
    4 F, r  m  q. p- E4. 二叉树遍历(前序/中序/后序)
    % q: |* |+ }! w" P) n; [5. 生成所有可能的组合(回溯算法)
    5 U9 o) o% X/ q* [: \1 c
    6 {: M" ~$ h2 h1 r3 L% J试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    难过
    4 小时前
  • 签到天数: 3337 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,8 a1 s' ]  h  D. R
    我推理机的核心算法应该是二叉树遍历的变种。5 J" i. v" I5 q
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:( I/ }) ^  s# z1 N2 K) g' E1 i0 d* a
    Key Idea of Recursion4 y8 u) r* k: F
    " x" t$ D. D; Q  j, P: h( z# ]- Q
    A recursive function solves a problem by:' K/ d+ `( e  m: S7 Q5 `( m# W
    2 r: T5 ^+ q+ A0 Y
        Breaking the problem into smaller instances of the same problem.% m: D" S( r7 Q5 g% v/ P$ S

    , v& [& R5 B- D5 o  z6 O. L+ `5 p    Solving the smallest instance directly (base case).
    ' M# p/ o: b: b1 _0 r5 H5 E+ N- T( D% ^$ d: ]- f4 W
        Combining the results of smaller instances to solve the larger problem.
    # c  t! s6 C, ~- a3 F; Q, {6 T! X! @' |5 C
    Components of a Recursive Function$ H- \+ q/ ?1 I5 G6 {: Q5 o
    0 U9 H8 J  V! O
        Base Case:4 \. \" q3 T7 X

    ( D( _; c  s: T+ B# ?        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.$ Y+ ~% R  J3 u8 |3 ?5 d) [" Y0 I: x

    ( p" G2 T, @. F/ u        It acts as the stopping condition to prevent infinite recursion.
    . U( P3 D  H( P2 Y) [) O( i( F1 [9 S- @
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.. U" }$ m0 o' K7 Z$ B

    " \( a, G2 g/ U( ?' Q1 V. y) f+ Z" j( X& P    Recursive Case:
    - `& }/ e/ f* D$ W* H
    9 z: d3 N' d; [  t+ C$ g        This is where the function calls itself with a smaller or simpler version of the problem.
    6 N* x8 c1 @3 k' ^% H; }/ E: P5 X6 U0 J% z
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    6 l( g- U" O4 S. [- j0 m$ J1 X- @/ i. v, k- Y9 m0 H' k
    Example: Factorial Calculation
    " c$ @. W) m4 E8 H) z* K
    ( i3 U& M  m' Q$ t  c. U- xThe 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:4 d. `# G0 n6 G

    7 R& `$ k% Z0 L+ L    Base case: 0! = 1
    % R+ O) G/ e1 ?6 o9 j
    4 l) t; t  {# X% d( f: I+ t    Recursive case: n! = n * (n-1)!2 ?8 h) \# k7 V. r1 M9 j/ \

    : ]& X* N) B/ v1 K8 JHere’s how it looks in code (Python):
    1 u7 f& j0 S- cpython
    7 ?7 Y2 m) `  a: ]
    8 `2 l6 a2 y" D( w% A! |$ L" A$ l" _, F0 u  N
    def factorial(n):
    8 X5 M& r4 A" n* S- z    # Base case2 }- N, W& ^3 K# L
        if n == 0:0 H$ a) X8 f9 c/ k
            return 1  h, E! y) s! d4 E
        # Recursive case
    1 u8 I. G/ v$ b, h( Z    else:3 F5 Y! r, {" I+ \9 ]' {+ F
            return n * factorial(n - 1)- n1 L, o' V, m; ?( s# b$ x

    / o: W$ m* x! A' y6 i( X# Example usage
    . u8 M. v' O" _+ C' p9 v! tprint(factorial(5))  # Output: 120( Y% A& L0 ]: x: C1 I

    8 D' Y$ W+ t  l! x# E+ jHow Recursion Works3 c; L7 q( ^7 [4 I3 C
    + r) M: m9 J7 Z0 C) G; X" V# x$ [
        The function keeps calling itself with smaller inputs until it reaches the base case.! J8 S' v: z7 h

    3 o/ V7 B. e- C& R/ j& Y2 n5 E    Once the base case is reached, the function starts returning values back up the call stack.# f8 M1 d/ j$ i4 v0 a8 Q3 G

    ) D) l! o, `$ w6 w' E9 _    These returned values are combined to produce the final result.
    ! _/ T8 a, f( l1 O. m$ y2 U2 Y" F& D+ T8 i$ m
    For factorial(5):
    0 f- s7 {( R3 P$ B2 ^& O4 a/ t' d- r$ K0 [) M4 B  F9 _' x1 F! L
    " W4 C+ o7 P) t5 M# G8 M  v+ H" n
    factorial(5) = 5 * factorial(4)
    ' j1 e8 F0 c1 A5 Kfactorial(4) = 4 * factorial(3)
    8 j' _$ u8 V5 a9 Sfactorial(3) = 3 * factorial(2)
    $ I3 \! o0 J. x' J( O' {factorial(2) = 2 * factorial(1)  H' G# C0 U5 P2 V0 o
    factorial(1) = 1 * factorial(0)
    & I8 K" R* Y) b, ofactorial(0) = 1  # Base case& r7 V. i; e: ~8 I& @& b

    5 F0 B# T- N3 e$ MThen, the results are combined:
    8 n, O' J7 N5 o& H9 ^  W5 N  s6 T  Y/ b0 f- i

    + t* Z3 j: V* Y& ^* h* |factorial(1) = 1 * 1 = 1
    7 z# K4 W8 G2 @8 gfactorial(2) = 2 * 1 = 2
    * X. Q$ S1 H" q' [1 ]" _factorial(3) = 3 * 2 = 6" H5 j8 p8 Q# X
    factorial(4) = 4 * 6 = 24
    6 R6 G+ j* j3 @6 gfactorial(5) = 5 * 24 = 120
    0 s& g8 h4 ]) e
    ) ^9 w9 u  T8 o5 q2 }/ N1 tAdvantages of Recursion8 \2 N  [9 z7 {) K: e7 c

    9 v. Z8 V3 I  ]- [    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).& V: f' W' w) A+ s8 z# R

    $ K7 _7 q( r+ h2 N: N- k; r7 X    Readability: Recursive code can be more readable and concise compared to iterative solutions.% B4 F6 ]! E$ A( i

      k: ~: c4 P4 iDisadvantages of Recursion
    6 G& k" d: G2 C) ^
    9 o, ?1 g& s9 r, c( W) N1 e    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.9 ^+ w' d% \# w2 o8 c

    6 J& I% B4 y$ H# V0 W6 }    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).4 U; c# s) ?& H: k3 r" K3 e* C
    - p/ R: X0 k% }6 \6 e, ]! q2 K
    When to Use Recursion
    0 N! H7 j: y" Z! D  v) T
    6 ^4 I: [+ K- T    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).& _3 n! a9 y" \: o# n8 ^) s+ D
    % Z7 h6 f7 q3 U. n$ l( j$ |" U7 A3 o
        Problems with a clear base case and recursive case.1 \/ B4 Y! q6 [/ m; ^# e+ r) d" D

    . H4 T- E+ Y- P* ]Example: Fibonacci Sequence5 K, I2 g/ z1 m
    & I& t  M+ G7 l. L; T3 A
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:2 u# ]  A' t) e

    ; `8 a; V; P+ N# E* h8 z    Base case: fib(0) = 0, fib(1) = 1
      j+ e* f$ a6 ?7 w+ _/ o) F
    - U8 X2 c0 i1 ]" B/ O! S& ]' R    Recursive case: fib(n) = fib(n-1) + fib(n-2)& f+ T5 W! {/ v
    , i' Q: ?- v8 }+ S
    python6 S9 f3 m8 ~6 t8 U" _& [

    + q8 X' K+ e) K4 V, s
    ; z3 b) |4 h9 c1 o8 w" hdef fibonacci(n):
    0 V2 M2 M, ?0 |9 K    # Base cases* U1 w3 }. K4 M5 ~
        if n == 0:
    ( E! ^. w* i  G% v5 N        return 0
    + R4 X9 I+ m* k: ]: j. B$ M. Z8 _    elif n == 1:5 W0 o7 Z6 i: v! _
            return 1
    ' D( Z5 k7 h0 H1 u! j0 y    # Recursive case
    ; h- ~1 R- u8 O7 N    else:/ ~* F; ~: z" m. D8 Y
            return fibonacci(n - 1) + fibonacci(n - 2); u( j. L$ @0 w" B1 b6 |

      i& ?5 P. y6 O& R$ O3 C* j# Example usage
    5 O% o4 ~! M, J( n, ?print(fibonacci(6))  # Output: 8( ]( ]$ l0 E3 x& B6 a$ `

    5 B3 b! B5 T6 H$ Y- T" M3 DTail Recursion
    % X4 x; H& ?! p! h% I) D
    4 a2 [. ?0 D  `# c# R8 FTail 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).
    , i( T. ?+ g$ s' t. r
    - Q8 r+ ]3 t9 T( uIn 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-9-1 10:40 , Processed in 0.072309 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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