设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    2 @9 s) s6 ~0 L; r  A) U
    : J- o9 Q% J! `$ s$ \解释的不错
    $ F5 K" ]7 x9 {4 v# |, |3 |. P4 r: L6 i
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。/ r; P$ p; H8 n: D. u9 ]

    ) ]* W$ |6 F! z3 Q/ G 关键要素& X8 j+ S/ a1 Q' y& m
    1. **基线条件(Base Case)**$ t. e) N7 q# U
       - 递归终止的条件,防止无限循环
    $ C! C0 w) U, h) `   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    ! [' w  `) J8 o4 d/ r9 g
    7 S6 g8 `9 u: w6 T4 |' c* Q2. **递归条件(Recursive Case)**: g+ `, `' g% h( r1 `7 T
       - 将原问题分解为更小的子问题1 @% {& P! C9 i* A/ i
       - 例如:n! = n × (n-1)!" k2 g, n  `" _
    5 U. p/ P6 [: _$ v3 [
    经典示例:计算阶乘
    6 t2 E3 d7 m& tpython
    . `4 c6 H7 J  p, j: [8 \def factorial(n):
    " z8 ^5 c8 k7 Z/ Z, T' m    if n == 0:        # 基线条件
    7 U8 N$ m# I2 _% k- r        return 1
    + ^: V, Q: w8 [+ ^, T    else:             # 递归条件
    8 @9 O- b5 q- ]4 Q$ B& D        return n * factorial(n-1)
    / v/ R, v) s' S! c5 L0 |执行过程(以计算 3! 为例):& q9 F# Z5 J0 l) e
    factorial(3)" b1 \& o: _! a% `9 O; Y# c* X8 n
    3 * factorial(2)
    5 u6 ]2 |% D- p6 A* U# V' Y2 ?- T3 * (2 * factorial(1))
    1 C1 |& Q5 }$ U# G' W! d% N3 * (2 * (1 * factorial(0))): c0 \2 d# U7 V5 n1 @( k! M  {8 M
    3 * (2 * (1 * 1)) = 6
    + d6 k7 G2 r, d6 b  d! O( F8 \' {" H! C4 h. k: p4 q9 S
    递归思维要点6 O, G5 _0 i9 a
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    / Q% E' ~' Y; F2 S2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    ; L: V- F+ k: v! m2 v5 t1 A3. **递推过程**:不断向下分解问题(递)
    ' a8 b# X6 W/ E3 M' B* \4. **回溯过程**:组合子问题结果返回(归)- Y  ^! w/ H) \$ l" ]# r5 I  |
    ; {. z; g  l( g6 B
    注意事项! C0 a$ s8 {8 z1 H, C- p/ N# A
    必须要有终止条件) a+ O9 P5 R# w2 v' x* q7 a! [8 |
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)4 W/ u7 }( k" ?* @; @- {) r
    某些问题用递归更直观(如树遍历),但效率可能不如迭代1 [6 m$ r! E. M+ g# n, K
    尾递归优化可以提升效率(但Python不支持)
    7 W5 I4 c  v- _2 q% o) t4 t6 m- R" {) S, A: U  A/ p2 `, Z: u
    递归 vs 迭代
    / t( g) x& P; D* z|          | 递归                          | 迭代               |$ ]; M9 B9 Y% F
    |----------|-----------------------------|------------------|' N" G4 h0 K9 S; |& @
    | 实现方式    | 函数自调用                        | 循环结构            |" N4 |* E$ |; F& C4 i5 A
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |$ P/ \/ J! H/ g- y- C
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    $ _# ]& o5 H1 H" ]$ f| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    ! B9 N3 t7 J  J3 ?' ]/ \7 v5 L
    * ]- c) I) h7 x9 f) W 经典递归应用场景
    1 [. D3 j! H  a# Y# R3 q: p1. 文件系统遍历(目录树结构). X7 b% F  l9 |- l0 o
    2. 快速排序/归并排序算法0 \% U/ t$ b  D# h
    3. 汉诺塔问题
    % k% A( u% J4 M, E4. 二叉树遍历(前序/中序/后序)' v3 r: P: X  o
    5. 生成所有可能的组合(回溯算法)$ u1 L1 u- p+ F

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

    评分

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

    查看全部评分

  • TA的每日心情

    10 小时前
  • 签到天数: 3157 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,0 P: B+ f1 l# g0 Q
    我推理机的核心算法应该是二叉树遍历的变种。1 n& v2 Y( L7 K- 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:& E2 o$ n* [4 ~% c( g
    Key Idea of Recursion
    ; i, \: o+ P: E. n( d8 C9 W( \1 i' @* P% L4 v
    A recursive function solves a problem by:  @" ^# O4 \6 H8 N" l
    + C, G& n( H; V, E2 n9 G
        Breaking the problem into smaller instances of the same problem.
    ; y1 l- y/ h# v
    0 C* A9 A. ^4 Q& g5 s7 N    Solving the smallest instance directly (base case).
    6 K! b; \" `1 V( R; @! E& A, P% t  m$ k
        Combining the results of smaller instances to solve the larger problem.
    : {/ Z# V- L( o& e( ?9 }
    * B$ ~. i- M) T6 cComponents of a Recursive Function" b1 y0 G* B4 Y( V5 h* ~9 m" f
    1 i3 `" T' v) {( u( d/ U
        Base Case:
    5 P  Z+ K6 e! `5 H& ^+ G! @& i1 s6 {! x) W- H* S
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    $ o3 W- ]$ a; T% f' Z$ p1 p6 {0 V/ P) o0 @6 z
            It acts as the stopping condition to prevent infinite recursion.
    3 f% j4 ~. p- g1 [2 ]' [! J, B' s6 ?8 z5 o! a
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.3 H+ }5 }/ B  ?0 g  ^( l2 c

    ( a& I+ C( o, M7 [4 r# x6 p    Recursive Case:8 o  _, q8 N  }& }3 f# p& N! i
    2 X: i( j+ p1 [, _: m3 b, P
            This is where the function calls itself with a smaller or simpler version of the problem.: q* E0 ^) [/ ~  Z3 e

    3 w9 R4 c. f2 A2 ~2 X) P        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).5 I% a. S2 l+ E. w
    6 x" f) W* P0 Y# [+ w! O) T4 p
    Example: Factorial Calculation# n% B+ o+ {" a8 s( a, Y
    9 l5 A! R7 l4 ^. x( J
    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:
    0 E, `; f1 C! V# A- g" a" J; a. p: h' c- o, F* ^
        Base case: 0! = 1
    6 }4 q7 O7 s) S/ [% Z5 r. w
    , y5 y; v9 _7 y0 K    Recursive case: n! = n * (n-1)!* N/ G4 z( j* b5 q# H8 n- E/ w

    2 j0 I- W" c5 d; j: `2 U9 ~" h4 \Here’s how it looks in code (Python):
    9 A, _( M' P" K3 L' |# P" E# _* fpython
    ' ?7 z! I" Y0 Q6 s. F+ C, D
    # B. A$ ]4 ]* i& H
    - K8 e9 w& F5 l/ f0 S: {def factorial(n):
    " R5 w& }* `( v1 k- m    # Base case
    2 T& T# J7 V; Q- |/ b    if n == 0:
    % T6 s. Q: f* b5 H        return 1
    # }8 \+ V9 R3 r" O. `. i1 E( f    # Recursive case0 G9 a  ~; G7 t0 q
        else:) u' W( c( \- H( {- K/ r8 x# Q1 T+ Q
            return n * factorial(n - 1)* _+ F) p+ n# i" |! i7 V

    0 w0 r( \  [3 ]/ Y7 {# Example usage
    9 f( h% m) ?$ }2 a3 mprint(factorial(5))  # Output: 120
    % L1 N; I( i! L  J3 [, ]2 S& F( R1 Y) Y2 j5 W! \
    How Recursion Works; Y6 l8 I3 q  X& N: a
    3 J9 E% r& f+ u" P" Z# w
        The function keeps calling itself with smaller inputs until it reaches the base case.% ^, q: P8 Z- h" d, Y
    1 c6 z1 W' F6 J8 j* G# I7 n
        Once the base case is reached, the function starts returning values back up the call stack./ G3 p% B9 h+ S7 g$ Z  Z/ Z

    # v7 _3 J9 d6 e' v0 B: v    These returned values are combined to produce the final result.
    8 N' O! y) [, v- i+ c' {1 y1 i7 i6 \7 }4 B$ F$ v! I" J
    For factorial(5):, F  a" h" |6 x3 X. I2 r

    ) A3 e: l& f. q1 W* ^4 J$ o7 {1 t" t& N' C5 D; Z' j7 q2 \
    factorial(5) = 5 * factorial(4)7 p) u) {" K. s- y5 }3 {& _
    factorial(4) = 4 * factorial(3)
    . i5 t6 E2 I& O' c# jfactorial(3) = 3 * factorial(2)& _* k% _& S& b% _
    factorial(2) = 2 * factorial(1)
    " h0 @% E: j0 t- Jfactorial(1) = 1 * factorial(0)
    * t( L9 m9 {% h( p2 Nfactorial(0) = 1  # Base case+ b( d5 _5 i% g* n* j+ L0 L
    7 _7 ?" x$ T& z, ?5 M' n/ H2 D2 b4 L: H; f
    Then, the results are combined:
    " i# k* d' d7 u+ o: v
      ~, i( u/ @- R
    7 Q# _0 ^4 k, W1 }% Z( `factorial(1) = 1 * 1 = 1. C8 T5 U3 [1 a& ^* j
    factorial(2) = 2 * 1 = 2
    ( C2 g- X% t0 \& z6 X' i. ~factorial(3) = 3 * 2 = 6
    4 w3 P2 A& \3 ]- C( J3 dfactorial(4) = 4 * 6 = 243 t3 L* ~. `0 l+ l  r
    factorial(5) = 5 * 24 = 120
    4 U' Q/ X5 G* {2 F, x0 A% D3 A4 y
    : V+ o5 a1 c# ~) ^, xAdvantages of Recursion; _5 w; y+ h! _( q& E
    4 b! T& `! g# X% }: R- a
        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).
    , ~5 Y3 o8 g: D% V- v8 K6 i: Q4 G# r! y0 Q& \) c6 A, \- q9 \  n
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    $ s% Z7 t* j0 X1 |5 x; q* |0 k. i" P
    Disadvantages of Recursion
    0 N% e" s4 [9 O
    7 r/ u# ~; u" L, J2 g7 C2 J    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.0 N/ @% l3 v7 h5 C- C' h- K

    / h6 @" ^/ U0 I. W2 `* N    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    - w1 F7 S, W% C9 b2 w1 y
    1 R& U' u$ c- c: g6 N1 vWhen to Use Recursion/ Q5 [& Z9 q) s  C5 b2 m& n

    , D( C! ~" V$ P# l* O' D  d& ]% C    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).  U, X, ^# _7 f7 {, Y! {
    2 b  ?4 l# j2 `& ~& g- V
        Problems with a clear base case and recursive case.7 x6 M9 X$ N2 }* x: U
    ! j/ ?/ w6 ?: s! L! O
    Example: Fibonacci Sequence
    . h1 s6 h! d( e, F  m. d8 Z1 Z6 ~% H& N1 _! u
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:* _. l5 a9 ^$ ]5 ?& c$ k4 b  q9 C+ y
    # M. }( i1 K3 t
        Base case: fib(0) = 0, fib(1) = 1
      t7 @; L  ^# y6 F) A7 m% y0 ~+ c" y0 U& Z6 |( ?8 a- }% k0 c. P
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    : F4 _. X7 ~7 `: M0 J3 t& ^; _; N; i5 I0 Z3 r5 o9 \  K; \
    python0 a: }: d+ h1 o& ~, [

    2 l8 @3 F# a0 G: A) j# z' _' v1 o9 V6 C: ^" x
    def fibonacci(n):
    & J* a8 s% v4 a; f# k& \% A* |    # Base cases* I) l; G  W% s
        if n == 0:5 X$ E! m) g) t5 U$ S
            return 0
    ; |3 ]2 v% y4 T# i6 n    elif n == 1:
    7 Q2 S0 a/ k; F. W( _        return 11 ?" W/ I9 t) L: g
        # Recursive case
    / f) W; ]" {8 ?1 u" g    else:; A! f/ z9 C( i
            return fibonacci(n - 1) + fibonacci(n - 2)
    9 N2 w9 d2 y8 v! I3 q1 b5 h8 V" B
    , _. B2 V# P% }9 ]5 k9 l( Y# Example usage! e1 l; h) @8 W7 \) u
    print(fibonacci(6))  # Output: 8
    - M8 z" M9 |- T0 Y( s
    2 C/ S$ v/ T. S/ x( s3 ^* ATail Recursion3 h* G; n# z6 b, ?, Q4 R5 z

      [# m3 [) P$ TTail 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)./ ^7 `4 H& a8 n2 P

    % J) q- l' Y+ k8 eIn 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-1-29 16:16 , Processed in 0.091687 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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