设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 7 Z; }8 @* W5 J* E. X/ H+ T/ {

    * `- z6 i$ C) E$ R3 ^1 F6 }解释的不错$ ~; o- j4 U  W

    : u1 I0 p5 j7 |: m6 T3 i递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。- c; d5 I7 Z  P, T+ d
    7 g3 Q% F0 W4 V  k" P" N% ]6 B
    关键要素
    $ }- g# Z/ [% P1. **基线条件(Base Case)**' \- N6 n8 C3 s1 F8 z( j& }, w
       - 递归终止的条件,防止无限循环6 k; [, v$ x3 [; U
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1  k5 `5 Y+ f+ D1 S0 {: k( i
    " M* z! ~# ]6 y8 w4 o' V5 }9 M
    2. **递归条件(Recursive Case)**
    1 S9 v  ?: J$ j& h. o/ x- A% u2 n9 p   - 将原问题分解为更小的子问题2 g9 o5 k0 A" O; W
       - 例如:n! = n × (n-1)!+ V3 t/ X# l5 v: R7 R
    4 R3 p* u* s4 b0 u  @" |$ ^
    经典示例:计算阶乘# t2 o$ E8 z$ x2 E
    python0 Q' }/ G, l+ l
    def factorial(n):
    ) j. O- O* C7 O+ J# T    if n == 0:        # 基线条件6 k' u! y: I' w, h6 X
            return 1
    1 X( Z/ O. K8 n/ z    else:             # 递归条件
    9 C7 Z; f8 u% e* @' o; m        return n * factorial(n-1)7 C9 @: U) ~% h0 `& P7 L$ c
    执行过程(以计算 3! 为例):6 P  N  x( ~4 u
    factorial(3)- e+ x* V7 y* a9 p: R- B' v
    3 * factorial(2)
    6 A- x6 c, m5 r" a1 X' d- y3 * (2 * factorial(1))
    7 D2 C3 h0 i$ s. v4 s+ Y) T. n" {3 p3 * (2 * (1 * factorial(0)))" X/ K! ?3 i2 m+ D& Q1 S: v9 W: V. I7 \
    3 * (2 * (1 * 1)) = 6* e2 X0 w) |0 d- P& f, w$ H! f' O

    ( _$ O* X6 V9 z2 B( U3 r; h; @: W4 t( x 递归思维要点
    % g, I1 E5 P" Z9 L: Y5 w  D& \& k1. **信任递归**:假设子问题已经解决,专注当前层逻辑0 {! ~: C8 F2 M9 M; ]
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)+ [+ x  W$ N9 e- T. v7 j: |8 E
    3. **递推过程**:不断向下分解问题(递)1 ~+ r3 Q: |; z, S' `  k# n, s7 r
    4. **回溯过程**:组合子问题结果返回(归)' N. H$ n+ }5 x3 o+ `$ `

    * Q2 L7 d% V$ g 注意事项
    : @- J' C# T$ \) H# w! `必须要有终止条件9 p0 `* U+ z3 [/ F; e( L
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)$ e. S! p' m9 E9 s5 u. Q
    某些问题用递归更直观(如树遍历),但效率可能不如迭代9 X4 t1 k- \! G0 }& V4 v0 e/ H
    尾递归优化可以提升效率(但Python不支持)( u3 e+ q& d/ k: n5 K

    . J- k: b+ Z0 {3 q# v 递归 vs 迭代; d2 z2 b  C6 i. x9 a( n, q1 q7 x0 r
    |          | 递归                          | 迭代               |# A; i4 k* E6 t+ U' e. A
    |----------|-----------------------------|------------------|
    " r3 Q6 [( H4 \; ?' d# l3 k| 实现方式    | 函数自调用                        | 循环结构            |
    4 y. k- H9 b) t' r) L2 F. O1 s| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    7 C6 f+ b3 a8 n$ w  z8 o1 \! W. E| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |& A* G0 d+ B. N+ }8 i2 @1 o
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |6 k- N, W3 G8 P5 h& O! d" _. [7 z5 f
    6 a: b& J& d+ \% U
    经典递归应用场景- f  M  T: [. x
    1. 文件系统遍历(目录树结构)
    9 Z7 S* j0 e" L4 X  R: I4 b: p+ n2. 快速排序/归并排序算法& g9 f; I: F; ~8 g" l' i! G" u
    3. 汉诺塔问题
    , a' H' L5 e4 W# {" _4. 二叉树遍历(前序/中序/后序). m8 l: c" N+ K
    5. 生成所有可能的组合(回溯算法)& f4 S+ J- _& O
    3 J8 g' G7 v+ U$ E' J% a$ K
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒," s' v9 i$ i( X& k, l( i+ L* I
    我推理机的核心算法应该是二叉树遍历的变种。7 A2 ?' P& L3 [$ @
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    , F. a4 `1 s+ x* uKey Idea of Recursion
    6 q& m( z# @2 o+ _# s$ k
    1 u& ~$ @# k8 u2 lA recursive function solves a problem by:
    5 p# i  L- `9 d) E' F) V- ]% i  [- j& @+ v* F! A
        Breaking the problem into smaller instances of the same problem.* u! t$ }* J* I( N# n3 b+ b

    2 L$ P' b6 B1 f    Solving the smallest instance directly (base case).
    6 Y; w, j3 b% t/ t3 ]5 {6 h0 j$ r5 Y( f) a: x7 X
        Combining the results of smaller instances to solve the larger problem.
    & K- X0 ~% d0 R3 q( h* E# j3 J# C0 i1 t: o! O
    Components of a Recursive Function* _1 t6 v* ?( u# c
    4 i$ Q  k" |! A0 |
        Base Case:
    8 N0 }$ h4 G. Y: i8 k- z9 W9 L
    5 N+ \# q" n! m$ Z        This is the simplest, smallest instance of the problem that can be solved directly without further recursion./ U4 i: q4 X7 i: E# b6 w" |

    : |8 @! y+ F7 O* j* s3 y, ^        It acts as the stopping condition to prevent infinite recursion.
    " D$ V* z- a0 S: L% m5 S9 H! Q7 q/ I1 T/ I3 F
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.+ x1 o& s% B# {6 @- f5 l# L# {8 ^) V

      T3 A. A. P/ p, g! w# i7 d    Recursive Case:
    8 Y; G2 R9 i, I- @3 N+ h0 |4 o) W! q, H. o! [6 a3 X
            This is where the function calls itself with a smaller or simpler version of the problem.% O/ i; ]7 J' |+ A0 z" w) o

    ( Q) K1 n# O# O9 j. G$ ?        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    & j9 p5 F4 h4 h3 U2 M2 \1 g3 j; w- {, w. i& F$ [! n8 d0 X) H& A
    Example: Factorial Calculation- ?( b! v  H4 @2 d2 x5 U
    " e8 [- D! L* ~: @" b0 a- \( y
    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:
    ! C2 r* F4 ]( N* a" _4 s
    : \  ~2 z/ I$ G9 D& P$ k+ r6 w5 o    Base case: 0! = 1( O# O, v; q: Y& l6 v/ R3 a4 l
    ) a' {  k  R/ B$ _, _8 w0 P
        Recursive case: n! = n * (n-1)!
    ) C/ b7 @( G/ z9 j" u3 j
    4 V- j) Z% W' E8 V; y4 J8 sHere’s how it looks in code (Python):
    * i. X/ s1 F/ {6 W( y6 e, g) kpython
    ( K+ _6 W! w9 R3 h# u3 \& Z
    1 J, @% Y* x7 D% o
    , w/ n0 w) X. s$ m% {def factorial(n):
    2 C! a1 A% Y' f    # Base case2 ^# F- s$ v& E( R3 z
        if n == 0:) |, v6 ^; A- J
            return 1
    ( P- a) j3 X6 W0 F    # Recursive case, J; D+ V9 k6 W
        else:
    $ A7 w7 [1 s7 Y1 u7 `- _        return n * factorial(n - 1)
      W; }, R: r4 P9 O0 f# @3 m4 x7 a2 R7 m" L3 g6 q; }1 U1 |
    # Example usage
    - g+ F* [7 C: i+ P/ wprint(factorial(5))  # Output: 120  |& e$ `4 [& }. \9 H5 c

    , w( w' d0 g% u: S' rHow Recursion Works+ |# r% b! y, f7 o. ?5 j4 W

    % a$ G9 J+ H4 `$ K8 O+ X    The function keeps calling itself with smaller inputs until it reaches the base case.
    4 f+ T) C. {! h- d( f6 ?' X( G' `; i) b8 p
        Once the base case is reached, the function starts returning values back up the call stack.5 N5 N+ q: O! Z! q
    " g3 }4 @# Q( U$ z$ e
        These returned values are combined to produce the final result.
    ! k4 `9 u4 Z- s, U  X( D, E
    + s: a# l4 W$ a* jFor factorial(5):
    8 r8 `& B+ B  j) v
    # q8 t, _9 o* |. V, u
    : u; f  X- Z/ p; _factorial(5) = 5 * factorial(4)
    " ^0 G2 U5 m4 `, c2 kfactorial(4) = 4 * factorial(3)
    : i& }" m4 c, ?; D3 U) Y% h) jfactorial(3) = 3 * factorial(2)
    6 ^4 Y3 C' i/ b, Q4 ?4 P8 ]factorial(2) = 2 * factorial(1)9 u' N+ ]. D* H( I- I
    factorial(1) = 1 * factorial(0)
    - P) A, e4 ?' @/ L; R, ~* F  U$ \) Lfactorial(0) = 1  # Base case. Q) _; l  {, P$ X" T0 F' S7 P

    ) ?$ H- e- ]" k" w" v) SThen, the results are combined:5 N3 _2 b! n2 \

    6 Y9 A2 v3 D  {" ?* B: ~- f: r. r0 ?$ i
    + S2 i, S: Z7 Bfactorial(1) = 1 * 1 = 1
    3 j$ t0 m* \! W+ L' lfactorial(2) = 2 * 1 = 2
    7 ?  k. S- u. G: y+ w, G# ?8 Bfactorial(3) = 3 * 2 = 63 j: x& ~3 ]- K4 Z! Z3 A
    factorial(4) = 4 * 6 = 24
    ) y  m* y( B% x! E9 Mfactorial(5) = 5 * 24 = 120
    5 {$ V: J2 F( V" x
    ) J4 `0 ~* x4 m4 VAdvantages of Recursion7 L( P0 ?3 z: F- A  \4 k$ u! s
    7 w' b6 c: K2 Z1 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).+ X8 j0 S6 }( r8 M5 L0 V7 J
    + @6 \# I6 u2 E
        Readability: Recursive code can be more readable and concise compared to iterative solutions.: y: u# p& J# a7 L" S
    & @7 A* S) @( p
    Disadvantages of Recursion
    ) p7 w1 ?4 f% P- `
    7 c: S5 V6 N& P' o6 L  y6 H    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.
    3 W% B$ s# W7 g! A- U0 p) N! G' `3 [5 k* I1 c# V; K
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).6 ?1 N; e" O5 K3 O5 s
    2 z6 C7 n/ x3 ~, T4 P/ w
    When to Use Recursion0 ]  s* O+ A/ A: a1 d2 \' G; m
    & K! l' U9 ^) V8 P& b0 t9 r9 Z
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).. ]  {; I: ~; X" t

    / V7 H! K8 X  {6 j1 s    Problems with a clear base case and recursive case.% W3 U' Z" o' V3 _

    - `6 l, @* h1 |Example: Fibonacci Sequence3 h, e7 i  k8 X  ]7 _

    $ w( t, [# R: l& p% ^. m0 lThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:! h: f' ?' Z8 Y, @4 i9 U
    + R: S' e9 z. t# t9 q' y
        Base case: fib(0) = 0, fib(1) = 1
    5 J5 i9 B% B8 n4 `
    ) X6 H% f9 p# \& ]    Recursive case: fib(n) = fib(n-1) + fib(n-2)# g8 }. @+ U% J- z' f

    % v+ s, J. O0 J; o% L, @python4 l. Z1 {' j5 ^* i6 L% m

    : I6 I! {! _. d* u$ G6 _, x3 o) N6 [* G# X
    def fibonacci(n):  l6 Z& t$ a# d6 i0 M7 q
        # Base cases
    : p  f) ~" f: {* ~+ i4 T    if n == 0:
    ; ^6 n  h/ ~) X& k4 O4 T& m. o. i7 T        return 0  X( j! p5 Q  e# N6 e7 W) j$ h
        elif n == 1:
    1 J( i" L: I* Y6 ^        return 1
    9 z* n5 I+ M; F4 y7 `2 c  F  y    # Recursive case9 K5 I0 p+ O/ i' a5 f
        else:
    + X; d1 x- f8 u: v( p        return fibonacci(n - 1) + fibonacci(n - 2)
    ) Y( k: L5 N% ^' e5 i/ g  m6 M0 Y
    * Q4 h3 W/ G' W- S+ q6 \& `1 C8 w# Example usage
    $ s; z4 A3 i. A# G) X/ qprint(fibonacci(6))  # Output: 8* o* v  {- M. t$ a( N' H7 ?  H! z# C- j

    3 B* `. S1 _( bTail Recursion: H/ Y+ k7 j+ B+ b3 ]4 G, C

    6 Q  G/ m6 W& [# _& W3 zTail 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).1 u- u- V8 S, }3 `8 q, H1 r& Z

    * {/ x5 v; g: b; c( |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-24 22:10 , Processed in 0.028390 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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