设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    6 ]7 L) S. [3 C" }$ V8 n* n6 E/ U- s+ b4 C; b. w4 ^
    解释的不错& e/ }6 Q0 K/ h# B7 j+ L

    9 f: B; H- s& K$ d' L递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    * T$ P0 C% T4 Z# {+ |6 I
    / F$ \! N1 n4 L( D( F* v 关键要素
    ( u5 Z3 j4 T$ f- I8 g: j1. **基线条件(Base Case)**8 v; |9 s1 M. r
       - 递归终止的条件,防止无限循环, Q( q2 ^- i, }5 l% |4 r- l
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1, j8 }( ?/ s9 G) q4 A0 K

    4 `7 U0 o* y# H2. **递归条件(Recursive Case)**
    . t( B- _9 |8 ^   - 将原问题分解为更小的子问题5 `! N9 ?! W, g; i
       - 例如:n! = n × (n-1)!
    , F, o& N# P/ [, M8 M. U8 ?4 N
    7 `3 i* E9 `! O+ x, B8 k 经典示例:计算阶乘
    ( U) w6 H6 [* ipython6 B0 w! V  t1 M9 K6 a9 a% }( }
    def factorial(n):' w( i8 @" M0 u# R7 h% V
        if n == 0:        # 基线条件
    , E1 r" X3 u1 ]  A& Z& w2 b        return 19 w7 E: X: f! `# G
        else:             # 递归条件0 u2 h7 T) L7 `6 U) x5 ~. M0 ~
            return n * factorial(n-1)7 J% m* J6 X& n& X% E+ q5 T5 `
    执行过程(以计算 3! 为例):& @. o8 ~- c  K. N4 \6 s. {- H
    factorial(3)
    $ r4 @- m2 T; Z# I* H' m3 * factorial(2)
    " m3 |3 D1 u5 b) Z3 * (2 * factorial(1))
    8 `; I- H+ C" _0 \) Y3 * (2 * (1 * factorial(0)))/ _7 n4 L* J7 V' j# L# `% ]
    3 * (2 * (1 * 1)) = 6$ w$ M/ V5 C" `& f
      _2 K' W, J5 @+ {/ j1 q- N7 K
    递归思维要点2 B& `! Z3 F+ O, |, O
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    / B; ?- j/ }4 W+ v2. **栈结构**:每次调用都会创建新的栈帧(内存空间)# y( ^7 r/ ^/ R  T9 q9 X
    3. **递推过程**:不断向下分解问题(递)- U- w( R. L& U
    4. **回溯过程**:组合子问题结果返回(归)
    7 _$ m! k# o% ?9 _7 {- L# q9 d3 g. d; Y& q. h
    注意事项1 e. _7 w( s" B7 ^/ |) \6 F
    必须要有终止条件
    3 A6 l5 ~. g- [" z递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    * M9 ^% J! g$ M+ n某些问题用递归更直观(如树遍历),但效率可能不如迭代3 G( s6 p5 z7 \' p  c; a4 H' W
    尾递归优化可以提升效率(但Python不支持)
    9 E* s, q0 ]4 E5 V5 \/ q, \4 d% l/ K& e2 S& j) ?* T
    递归 vs 迭代$ E6 ~8 U2 c- Z& r
    |          | 递归                          | 迭代               |& j9 h# [$ k- L# L1 J+ I
    |----------|-----------------------------|------------------|
    - z2 ~7 ~9 G7 F: n5 [) n/ `| 实现方式    | 函数自调用                        | 循环结构            |# m1 p; |! K# f; b) t; ^, r4 W
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |+ i& m  b/ Z7 [  |4 g: z1 ]$ Z
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ) }  t+ i' g& Y: g| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |' t' G7 A* L5 |

    ; w4 A: ~/ W5 W8 g1 H 经典递归应用场景
    * v/ G" N8 X1 b* Z* A; H' t7 a1. 文件系统遍历(目录树结构)- t4 D" b4 @% ]2 [$ Q, |9 B* ^
    2. 快速排序/归并排序算法
    / P6 o' z& L7 N% E. S# Q3. 汉诺塔问题
    : E1 o* }3 M6 u5 k1 \  i4. 二叉树遍历(前序/中序/后序)
    / u) g0 U! ^( c+ D3 E, b  B. j* P) b5. 生成所有可能的组合(回溯算法)7 e6 {7 I( m6 y3 d8 I1 k; p! g

    - P( Z0 a! N, w4 p试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    昨天 06:44
  • 签到天数: 3104 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    7 [4 Z1 }1 {$ _# C, }" \我推理机的核心算法应该是二叉树遍历的变种。8 D7 }9 {0 T( u1 X8 W
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:) R$ K5 Q; i* R5 s; y
    Key Idea of Recursion$ D8 {( C. `$ F, N9 `$ B

    . I$ I: U8 T8 lA recursive function solves a problem by:
    ( M+ }( v1 ]6 S6 v/ @! T0 C& ~4 C# u; g, |  w
        Breaking the problem into smaller instances of the same problem.' t9 |: b/ b, ^) p  u6 y

    2 {- ~5 X0 }1 z  B8 e; S    Solving the smallest instance directly (base case).3 W  M6 q5 d- }( r  H
      @( I1 ?/ B* x- ]- {9 ^
        Combining the results of smaller instances to solve the larger problem.
    % @/ t4 \: N- p+ N( V8 j0 ?2 \! y0 g' q2 ?. ?4 D
    Components of a Recursive Function$ A4 t3 z# ]$ a* u
    ! O9 X. @2 J6 {! x
        Base Case:9 h; M; |6 u/ V

    5 K$ O- h9 t. [, Q8 X6 S        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.% _$ @$ z8 I8 H! G
      o, ?& M' v7 z% q
            It acts as the stopping condition to prevent infinite recursion.
    & v2 }) s5 w* Q: S
    - `9 U- F1 V3 L9 [  H3 Y8 q        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    / w( ?; F3 _* i2 f) h0 B, f
    ) [. t  ?9 |; E3 v+ t! o    Recursive Case:
    7 x/ N& m$ H" l2 r6 H8 i8 b9 Q+ o3 Z, q6 u, ?
            This is where the function calls itself with a smaller or simpler version of the problem.
    3 l" [2 ^& n# k* h4 B# B' V8 T
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    & ^* N9 g' D/ I5 t' H1 y( W( J/ `3 ~, a. k8 u6 l( w. L
    Example: Factorial Calculation8 E5 Q: Y$ w: s" G% o4 L
    5 A; H& }+ K1 m1 {
    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:
    $ _) c" F% v: D# V! O" g% s  K+ |
    ; U% ?- o3 @- U* g) w    Base case: 0! = 1
    ' _. k$ \9 U8 T7 L
    2 }( f$ ^" J& F" S3 a4 }    Recursive case: n! = n * (n-1)!
    3 Z" u6 p3 H. [. B) _* a2 s8 [
    6 z' H6 h6 r4 Z9 I$ LHere’s how it looks in code (Python):0 ?$ m) k+ Z! K: i6 V
    python
    2 Y/ k6 I3 x; U4 S
    3 i: g  B0 q# t8 K  ^
      P8 F: X; S& xdef factorial(n):
    : p0 }* R6 V9 y; `# a3 G    # Base case
    - ?) E6 t( e/ |, x6 g: E# \5 k    if n == 0:- @& i! r$ ~7 l* E
            return 1
    " m+ P& o& y* R0 I5 ?) |% b$ C; S    # Recursive case
    # D8 O8 i* j0 N/ D) J$ c    else:( B- M! ]  V0 N& I8 v. Y0 e8 D
            return n * factorial(n - 1)
    ; b9 b! I5 l+ P" E2 `* @5 O2 q6 {7 }
    # Example usage
    ; p3 z2 l' D" `; H9 x4 i4 vprint(factorial(5))  # Output: 120) n6 Z8 w% z  F6 U1 U2 a" H

      q5 f- d; J% h1 j  FHow Recursion Works
    9 @$ @$ ^% @0 {" X+ n$ _7 Y5 n2 H" S  V- S# j
        The function keeps calling itself with smaller inputs until it reaches the base case.
    3 }7 ~4 Q" j% y. g
    * g  N, e9 [$ c1 F2 K2 z    Once the base case is reached, the function starts returning values back up the call stack.3 ?. l  `  `) m! v" f

    4 h# H. C, G! I6 f6 m    These returned values are combined to produce the final result.+ a/ @  Q: ]# {2 O0 \0 C0 M

    & n6 A: L. Y. v) A5 w6 hFor factorial(5):
    ; B3 N% ~0 @# y  J5 R8 d+ O  k$ |! W9 c$ |+ `: ]8 z* w2 ]- o
    & T7 ], b7 q0 e7 F7 J
    factorial(5) = 5 * factorial(4)
    + v3 @* F4 n( w) D  t! d; Jfactorial(4) = 4 * factorial(3)4 D' v  b* \; g' G) ?8 _3 i9 h
    factorial(3) = 3 * factorial(2)% f8 i$ [7 C' v, H; f% [; c
    factorial(2) = 2 * factorial(1)
    # G* c. z. @/ L" {  I9 s1 z$ @factorial(1) = 1 * factorial(0)" G- D5 A% H* t: ^  k. Q
    factorial(0) = 1  # Base case
    . C# E- {7 {+ v) t& g" G2 ?. @: y: {! i" ?* `
    Then, the results are combined:; x& \9 ]% i! v# ~2 D1 M! i: {
    8 q- ^8 g1 Y/ \* z! {+ H+ a
    ! t# I  P* m1 M( C( ?4 _* U
    factorial(1) = 1 * 1 = 1
    % e1 A  W) v4 C) t1 d8 Efactorial(2) = 2 * 1 = 2
    6 P" r( ?7 S/ B) y# o/ A, Vfactorial(3) = 3 * 2 = 6* E9 Y8 B/ y9 Y5 I, j! G
    factorial(4) = 4 * 6 = 24. F# e2 f: f/ [% Y
    factorial(5) = 5 * 24 = 120
    5 w' s: b; ^, `' x7 S2 w, a! i7 h8 E+ k( \* H9 h, t
    Advantages of Recursion$ D! k& H, W& s

    - Z, k8 a$ O% 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).. f* Q6 D1 s6 B. j- x* ?( g/ [& g! z; B

    1 B4 s3 B8 W! d) C0 V, P    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    ' L, u) |" V3 X
    * `8 D( W; O6 MDisadvantages of Recursion
    ' L, ~, b, T% @( R3 U3 p5 y
    5 k# \( ?* @, O; k    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.4 E: T* B2 j+ L4 ?% r
    5 [. p- @0 j0 C$ A4 M7 L8 t# Q1 e5 e
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    , `5 V' b' f; ?& g, r8 E8 t) P, Y4 L( K2 g7 h0 c) W& d6 @. j
    When to Use Recursion2 m+ K. f7 q: V8 v4 S5 q

    - J8 _* v" o/ s* V    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).$ J5 a+ x  p) j# A- \6 Q

    * r  G7 f1 W# |, T+ e& t" o% J    Problems with a clear base case and recursive case." X+ _- r$ T: z* I' |( c/ R

    4 A1 ~- I4 v% o) r& o5 H5 L2 \Example: Fibonacci Sequence
    / M4 w2 @0 e) Y+ U( X
    5 ~9 v8 _/ E# a$ u) RThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:* u1 ~% h! y. X+ C% ^1 c- j: X

    3 `) H2 h7 ^, O( v5 Y% s. U! F    Base case: fib(0) = 0, fib(1) = 1" {: Y+ W/ x& d0 c

    5 u7 Q3 k6 z; T) y3 a    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ( ]- y" e+ T$ t5 M% z; c, g
    6 t% f( I( q& T, x: H) x4 d. s6 E0 |+ j3 tpython+ u' u2 z6 W- b* o
    / b/ ]; r5 p9 p1 p
    ' B1 u' a* {+ Y, z8 C$ X
    def fibonacci(n):4 l( t2 b  O  Y8 x+ f% g) o% f. Q, e' e
        # Base cases
    1 X( p: _: W0 V2 m    if n == 0:
    6 f# W4 ]6 A* l8 \        return 0
    , C9 v* v, J& s3 B* `    elif n == 1:
    ; x( |( @1 s$ v4 Q        return 10 \8 S/ S" j4 b- ]4 u: H' N% K
        # Recursive case
    ( b8 u, u+ V3 `$ r7 F( F; `. d    else:
    2 t" r5 n# G4 P* A( t: j        return fibonacci(n - 1) + fibonacci(n - 2): x/ h) U# i: T0 w/ i
    " k3 a! L; ?' A6 p6 ^; b, c
    # Example usage
    ' t3 w4 B. O% G* a! Rprint(fibonacci(6))  # Output: 8
    + S) G6 W" Q, I7 e1 D% Z% k4 o# a3 z0 u6 g7 `$ E3 }" _
    Tail Recursion
    6 m  l/ Z1 m/ L3 L6 @1 V% Z$ j0 D& }! F9 N7 h/ e7 Z7 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).2 G# _" K  b, p9 U" T4 Y( j
    ; \/ C. @! ~1 e8 ^# _1 s
    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-11-30 00:16 , Processed in 0.033878 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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