设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑   V3 I* q* |$ D2 W% l- k

    5 x8 \+ _: D* t4 U$ j& V. X; P解释的不错
    # L. [+ T& g8 D$ I* t, N, V/ H9 A
    . [5 x% Q' f3 S3 [5 D递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ' W; X1 Q' w% }0 ~7 r! e5 K9 r
    ) D2 v3 c9 d; Q& u 关键要素( S- e2 \- Q3 w" o5 P( O" B
    1. **基线条件(Base Case)**6 k6 W7 v2 r- E  ^4 _9 z- ?
       - 递归终止的条件,防止无限循环
    5 w/ Z( \5 A5 z, w8 e9 s   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1( i& Y; o6 q4 |6 J; a

    * Z, I6 {# h# a- R1 M) E0 Z2. **递归条件(Recursive Case)**
    9 D, `& T7 O6 |' c3 g# ]& _$ i   - 将原问题分解为更小的子问题
    + N/ g3 w3 m3 v   - 例如:n! = n × (n-1)!
    % V" r7 I3 i* v. v
    " A+ p  @4 e7 `6 Y2 e5 a7 j0 X 经典示例:计算阶乘; `7 n- D' H+ N: L3 h( L
    python0 |$ R: _$ d6 z8 h
    def factorial(n):
    4 }1 T% K, X7 n# O    if n == 0:        # 基线条件
    2 ^1 m# J* B' s1 j2 O( h# r        return 1/ A; M. i* Y3 C9 i- U& J2 G1 M  X
        else:             # 递归条件
    5 x) ]3 h+ I* U0 \        return n * factorial(n-1)
    - K; q+ W. A, {- d- e执行过程(以计算 3! 为例):
    $ ~5 A. n) j/ @9 j* Kfactorial(3)
    $ K7 I+ H4 Q" n4 v9 p+ D3 * factorial(2)
    9 q4 _5 {1 W. X: w% G# q6 j4 g8 e3 * (2 * factorial(1))
    + B3 p, o. {) s7 y1 w1 `3 * (2 * (1 * factorial(0))); Q. o9 D9 Y1 x+ t
    3 * (2 * (1 * 1)) = 6  u/ U8 I2 V0 Q: F1 D2 G9 D$ a7 E: ?
    # d+ L, X5 q5 i
    递归思维要点, }  B$ \* `, T1 Z- \. L! f3 Z3 P
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    3 N: a; r6 c* J, {2. **栈结构**:每次调用都会创建新的栈帧(内存空间)' e. n* X* X( Q) \4 l3 O# b
    3. **递推过程**:不断向下分解问题(递)  Q" J7 `3 t. d9 Q8 O; @) Y9 j3 D/ U* u
    4. **回溯过程**:组合子问题结果返回(归)
    ! c: a& m% |3 {% F! A- ^8 S9 \: p( o: }) [. M% u$ |
    注意事项
    % }; |6 f+ X& K; A) D$ t必须要有终止条件, U: q# V8 x$ V
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    " p% V+ D7 g5 p+ `7 M8 D8 {某些问题用递归更直观(如树遍历),但效率可能不如迭代
    " x; o% w1 A' z/ O4 S7 h尾递归优化可以提升效率(但Python不支持)
    ! |3 B, _2 _: q' W* Q# i' `+ \  E! q
    递归 vs 迭代5 d; l$ I+ U5 j5 [
    |          | 递归                          | 迭代               |8 ~% Z: p! e' ?9 x. m- z
    |----------|-----------------------------|------------------|; j8 C# ?  N6 _& Z
    | 实现方式    | 函数自调用                        | 循环结构            |. u; d) l( n( J  T+ b
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    * Z) l; I! y( q- m- E| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    7 p: ^9 g' Z# E  |6 j| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |+ t8 M* W' I6 C  P7 ~

    5 {! Z9 s  T( h6 k& I0 ? 经典递归应用场景$ V+ n, @; P9 g, I1 b
    1. 文件系统遍历(目录树结构), f/ ^4 Y9 G. a& G7 M
    2. 快速排序/归并排序算法
    ' F6 U6 [, _* Q# M" k5 J0 e- O6 H3. 汉诺塔问题
    , d5 \4 x8 m" t4. 二叉树遍历(前序/中序/后序)3 `# p6 ~8 D/ a1 }& x# Q+ b& M
    5. 生成所有可能的组合(回溯算法)
    + Z1 t9 e; R& I# C0 X( g
    0 T, t- m& `0 E5 W# j+ N试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    郁闷
    昨天 07:37
  • 签到天数: 3172 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,$ A( p+ q1 J8 i) K
    我推理机的核心算法应该是二叉树遍历的变种。1 Q4 r$ Y5 v& i* V/ O7 a4 n) a( P
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    8 b  v9 D7 r9 k0 zKey Idea of Recursion: P4 S9 [) \( m9 s

    3 n' Q8 s: e0 w. Y9 Y9 S( E& G8 ^A recursive function solves a problem by:
    , o8 @# F) x: W; N7 _: s2 s6 f& {3 d6 ?  I% L$ r
        Breaking the problem into smaller instances of the same problem." j$ i. Q3 }9 A6 B

    6 j3 I0 Q6 _" M( \/ a* B* T, k    Solving the smallest instance directly (base case)./ I0 ?5 N+ Z% g7 I

    % X. g$ X' D2 ?9 X    Combining the results of smaller instances to solve the larger problem.5 J' j* z" P4 o/ v2 v& n5 D
    ) M# m- v6 ~0 G
    Components of a Recursive Function% I5 V+ V. Z/ B
    6 t6 j6 }  h/ T' h
        Base Case:. T; L3 @3 y" t6 n

    ' w+ g) G% |5 k# ^$ w        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    0 d! Y3 ?9 _0 Z4 m% X6 k7 D: }$ t7 a
            It acts as the stopping condition to prevent infinite recursion.+ n) G7 K% Y; U1 x
    $ n" B6 }' O' @4 x, i2 l0 t: x
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.$ a5 c4 A0 V: L5 Y1 ^  P4 ^  R& V

    + ?: l; y( I) S; ~6 }! L. }2 f    Recursive Case:
    8 n0 m$ q  C8 Z7 f8 s3 V  g6 ~& o0 k7 Y, n6 `* E, Q' M6 A& L1 i
            This is where the function calls itself with a smaller or simpler version of the problem.
    ' G) W6 |( w. [1 p1 t4 g5 j( x* j- v' @7 N) v' G: |
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    4 N$ n- A! g* g: a8 t$ K' Y
    & m  [8 }4 f$ N. P! |  `8 i8 cExample: Factorial Calculation
    . Y. T8 ?8 Y! K# Z
    5 ]! A' M  _: u# {' UThe 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:
    + e7 T3 p% }9 R) a8 ^  s& d( H3 n$ x1 T/ @
        Base case: 0! = 1
    7 j! M. E9 }6 W: K6 h# k& q. l9 j! D# u2 A9 e1 C
        Recursive case: n! = n * (n-1)!: v9 q* U( a' Z% W: f2 S  `

    ' A6 E! L, x* y8 aHere’s how it looks in code (Python):
    : ^3 q8 i2 x& w" z3 q! n$ ?python
    + N" ~8 V$ ~' e; _5 B
    & d) t% }3 R! |
    5 V* i4 ]; q: sdef factorial(n):
    " Y$ s4 i1 v1 H0 ?    # Base case
    - {0 c  [3 b% ?# h. C( W9 W9 }: b    if n == 0:" e8 y; X/ L" I1 K+ Y
            return 1( o+ W9 Q& z! \/ o
        # Recursive case
    , [3 `% q+ X  F' g    else:& R2 n' b; R7 H4 V/ p! Y
            return n * factorial(n - 1)
    . H4 S9 H7 @9 Q$ m$ w; m8 ~) `# O4 t3 Z6 D( q
    # Example usage
    8 P+ ^% ~: A3 d' o" wprint(factorial(5))  # Output: 120- r" |9 K7 q8 v7 Q4 t# i

    $ A% O! F+ J9 a' v; A7 R$ @1 CHow Recursion Works
    ; c" G( D4 P" w  Q4 G; ^' S& g" {% f) b5 r" \
        The function keeps calling itself with smaller inputs until it reaches the base case.' S* Q3 O  m9 z0 R. k+ B: O# ^

    5 c& Z# i# C% b8 a    Once the base case is reached, the function starts returning values back up the call stack.) ]4 I- y5 [( ~" G9 F6 `
    % z6 Z9 n$ \/ H
        These returned values are combined to produce the final result.; G* c' e5 B0 l% j

    ' l. l! x! F4 v& e3 \7 e# s4 I$ dFor factorial(5):
    1 C/ k5 s4 [* r: U* z# n) |* R# G  c6 I# [/ Z5 p

    9 q& \3 Y4 S# s0 Ifactorial(5) = 5 * factorial(4)4 i; a. z. M& r$ o6 a: l9 b
    factorial(4) = 4 * factorial(3)
    ) J; g* t, ?: H5 |2 qfactorial(3) = 3 * factorial(2)
    9 H# B+ h8 z$ h3 v7 W( Lfactorial(2) = 2 * factorial(1)
    + G, l& o3 Q6 W) [3 Hfactorial(1) = 1 * factorial(0)% N! e8 ?# }" ~$ H. E& i! L
    factorial(0) = 1  # Base case' g* S3 @0 b$ c! P

    2 O5 {. l1 [- g2 E% yThen, the results are combined:
    5 c3 H! b) M3 z( w7 A3 V7 `8 c
    1 c" f; y- M. P. g! `& M
      Z! C% j+ O; Mfactorial(1) = 1 * 1 = 1
    : p7 ~" G6 j- Q$ u4 o3 Y% O+ Zfactorial(2) = 2 * 1 = 2, G* s4 A3 V$ a, T9 q
    factorial(3) = 3 * 2 = 6
    ; v: T& x+ p. Qfactorial(4) = 4 * 6 = 24
    & u0 W6 X( ]9 K0 o% k( N4 `factorial(5) = 5 * 24 = 120
    $ K+ e7 O/ M+ w8 h. w8 E
    9 r* z0 o2 B4 V' Z3 S3 F$ K: ]$ AAdvantages of Recursion9 [. C* Q8 @8 T/ ?# U) j6 \( L, Z' @2 v

    : v2 L5 O3 f1 s3 y3 c5 P$ 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).( E# v; ~% s: o% [" ~- L; O
    $ j- g6 d+ v8 R: E4 }, C
        Readability: Recursive code can be more readable and concise compared to iterative solutions.; X) j7 [$ p6 O# W
    " I2 v' a  [! G) k/ P4 _
    Disadvantages of Recursion
    $ s4 _0 Y$ b0 \. I$ c
    % N( q) w. V. y: }! x    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.
    : b( l  I+ j# ]% d: D
    & n/ Z, \" Z" k+ b    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).% g. l) C- l" o3 R8 o

    # }. x' L, G; @9 {! tWhen to Use Recursion' S0 K5 L: ]. z3 X) ?5 }
    1 x5 X8 X6 |0 w$ _" `% @! p
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    % j7 j% `$ ^9 |+ ?* |0 Q( a/ P! Y; ?8 P7 J, D2 ?2 p1 v) \2 h" D/ O. ]0 g* O
        Problems with a clear base case and recursive case.
    4 \# @/ f0 z: f: V5 ?  B  G0 H3 c6 Q- T2 ~$ Z: M1 q2 n" `# S/ i
    Example: Fibonacci Sequence1 c4 U2 `; A: u" H- F
    & v9 R' G8 {# ]3 s" @) {
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    ! [: {9 c% J2 _0 y9 \! S7 \! }
    4 F: P. B6 J8 m! K    Base case: fib(0) = 0, fib(1) = 1  R5 A4 W& y( r* A- ~, X/ D

    4 d7 r9 ]" [/ Y1 o6 {7 h( J    Recursive case: fib(n) = fib(n-1) + fib(n-2). v3 k+ z2 l7 u* G
    % x) T4 _% h; O4 o& W1 H
    python6 X1 `, h2 C5 z* [$ l! N% [5 q5 K3 z( P
    ; o6 g6 M. p0 @& Y# i

    9 N! m, }8 v- \- k- Wdef fibonacci(n):
    # k& @& \% A  L    # Base cases
    4 z3 @9 X3 ?. e8 w: k' z    if n == 0:+ T/ N& B+ ]. O
            return 0! Z% V( |! ~$ |4 n  x" d/ Z0 w
        elif n == 1:" T7 z& T1 [) z( @3 Q1 \6 n3 _
            return 1
    8 ^+ t' _# W) w0 i1 N! N& \. `- V    # Recursive case! a: ]' D8 b! T+ W
        else:- f: c  l  P( y* T
            return fibonacci(n - 1) + fibonacci(n - 2)0 F+ K0 i$ J! ?" }
    . j5 Y* ?6 m1 b: n) @! J9 ~! z
    # Example usage* a; \/ [: [4 R
    print(fibonacci(6))  # Output: 8
    . {1 \0 D. J% K% p! b1 s
      L  [& W. r# yTail Recursion
    2 S/ C4 R; ?" u1 z' g8 {/ {) T& m$ `! `! N
    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).
    3 f4 \5 S0 W3 J( S( _+ k0 R) B7 M
    3 y& j1 A& L/ o7 K, U/ S" IIn 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-2-14 00:43 , Processed in 0.054021 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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