设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    - z" i0 v) y' x  r. C
    + U$ p& h. W3 w- }解释的不错
    3 z' h4 U- W4 R9 _. E6 i. G& r" V' v1 e$ {
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    * z- `( i6 r8 X6 N: q0 M, I, J2 t3 ]* `+ O8 u' x$ \
    关键要素( o/ ~; Q  O+ t$ P2 n
    1. **基线条件(Base Case)**8 k! e) Y8 N) n& C! S. M
       - 递归终止的条件,防止无限循环
    . c2 J) J; d% y' H" l: }. ?   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    . S( h! N  h4 r: p0 `9 M
    2 l* r* q5 f; b+ q5 g/ s" e/ r3 t2. **递归条件(Recursive Case)**
    & V" ^( M1 D" A- @( y7 ~   - 将原问题分解为更小的子问题* G: ]6 N( \& `! L* e2 D
       - 例如:n! = n × (n-1)!, k% [% \  Y& D! M9 x; v

    * g$ a8 l. F3 j0 W8 { 经典示例:计算阶乘# x2 Y9 z& a' t
    python
    3 ?" m) M9 B# d$ a! P' Bdef factorial(n):# K4 P0 }( `4 t$ e5 N, w& [' H: L; R' o
        if n == 0:        # 基线条件' F2 g" T6 F" [- O5 ]
            return 14 x. a; |4 z6 e1 c1 a1 o* H
        else:             # 递归条件2 g1 i; }' C1 v, @6 R% l
            return n * factorial(n-1)' O" u/ ~4 c8 h
    执行过程(以计算 3! 为例):1 F$ A- p8 z% E4 t3 a1 z9 i" V
    factorial(3)% f$ r# F2 V; V4 ]3 y- d
    3 * factorial(2)- Y1 S' H2 ^/ e- G' K$ T
    3 * (2 * factorial(1))
    8 x0 S. K: I0 a4 N& q3 * (2 * (1 * factorial(0)))7 E+ E9 F6 _* W( t! b8 F
    3 * (2 * (1 * 1)) = 6
    $ Y6 e5 f. J( _$ V0 }+ b2 a0 r! v& _) I0 N3 _5 H! w! M
    递归思维要点, j- }+ d) Y# [/ u
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑+ E/ |. {6 T) a! }
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)3 d- a& R, L! \+ r' \7 J
    3. **递推过程**:不断向下分解问题(递)
      N6 z- D# l+ \- G) ^+ J: b/ O4. **回溯过程**:组合子问题结果返回(归)
    7 j0 n+ w- C9 o6 Z* \" V% k2 z
    & c. F5 Z# i3 z/ z; h 注意事项# o) t- m# Q" l
    必须要有终止条件4 |6 o, V$ }1 ~6 c; b- {5 W, E
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    + N4 s3 I$ `0 K* c某些问题用递归更直观(如树遍历),但效率可能不如迭代
    5 B2 y4 F' H! H4 k8 g1 b2 K尾递归优化可以提升效率(但Python不支持): o& d- P" o7 O( V! i2 M9 L, F
    ) w- I3 ]$ f8 D) X1 z4 E, F' }
    递归 vs 迭代
    $ X, r4 b6 E; d0 `|          | 递归                          | 迭代               |
    " u2 m2 ~! W; A4 `# h& p! `) {: \; O|----------|-----------------------------|------------------|* ?( w6 Z) i3 {  _& I" s. _
    | 实现方式    | 函数自调用                        | 循环结构            |
    2 T/ |. W7 M8 t$ c! J| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
      N  A9 [' f3 ?4 H, b3 L: y, P* ^7 Z| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |1 ]: I2 J! m% b$ q- z% Z2 I) d" A9 W
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |9 B+ I" q/ n" M

    " x$ q/ V9 \; |4 v9 R 经典递归应用场景
    5 g/ R- q% f3 J5 n$ q2 x1. 文件系统遍历(目录树结构)- U' o) q7 q7 a$ ?' ?, C
    2. 快速排序/归并排序算法
    # k7 [1 Z4 N1 k) P5 K* w. ~3. 汉诺塔问题/ O" ^* Y& q) U; ~; O  ]
    4. 二叉树遍历(前序/中序/后序)
    ( c7 N' y2 X3 P5. 生成所有可能的组合(回溯算法)
    / A9 B  P- X3 H+ v! w6 Q# v: b. g. R' M+ T7 {: V
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    郁闷
    半小时前
  • 签到天数: 3145 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,7 Q0 l; z2 r( |' N
    我推理机的核心算法应该是二叉树遍历的变种。3 f/ o: P* O+ u, U9 h* [3 x  A
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    4 H' W- l1 ^) Q' U5 sKey Idea of Recursion& q4 y. {4 m( c& u- r
    9 G6 F" ^- y% Q0 Q) L6 [
    A recursive function solves a problem by:
    7 O  B: N6 G8 i) Y) w) ~+ l2 [: g* {+ V7 c2 V1 x
        Breaking the problem into smaller instances of the same problem.- [0 B/ i5 ~  g* n  H  x

      ^  H0 o3 C0 c" ?9 ?9 V  M    Solving the smallest instance directly (base case).
    ( c2 O- \5 p4 p
    & q2 ~, J" x$ E8 R' X    Combining the results of smaller instances to solve the larger problem.
    $ g+ ?3 b7 i" V9 f+ l4 Z, T  _7 g" E/ ~
    Components of a Recursive Function
    1 |. K  S/ N8 V3 Y2 Q. w  p. x8 R; G" @' j* e$ O( l+ x
        Base Case:
    ! x7 X/ l" H: f  e% y( r: P/ \9 Y: I
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    / G+ ~  T- D$ x8 y* K* E! e. q  \6 {$ ^' a5 {7 q
            It acts as the stopping condition to prevent infinite recursion.& i) J! E3 V$ w0 ^  {

    ( j8 y  U4 p3 X! ^* l. V+ J        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.' ?2 x5 Q- [$ H

    5 ]/ t: M; X7 Y* P    Recursive Case:9 Y. |! Z' r# U1 x- k

    , Q7 S/ @) F- K        This is where the function calls itself with a smaller or simpler version of the problem.
    7 }" k4 W: Y& P  U2 ]7 p2 p5 ^+ ^1 \
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).5 ~$ s: \8 P! S2 T* [
    7 [0 ~# d' Q& l+ c
    Example: Factorial Calculation
    . G& G! B9 O/ D1 \( ?' K
    0 z+ v4 c" b7 R# i5 Y. g$ o# U! [" aThe 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:" X- q  U9 U0 T& X) j

    7 Q# w+ w: O; [1 t    Base case: 0! = 1
    1 `1 |# @% G, p5 O9 E" N1 r% x# C; r" V6 k5 n' C
        Recursive case: n! = n * (n-1)!1 i9 b  K! Y4 ?' X3 z" Q0 @
    + j  e# \4 e2 c- Z' I) r
    Here’s how it looks in code (Python):
    % Q% j+ d4 q! V; p5 v7 |0 Y5 fpython
    8 o1 B( E% f) Y1 t( ?/ K: q! `0 }& E' `- C

    3 z' `6 F( i" V- Zdef factorial(n):
    & u4 T7 R8 t3 x/ j" _4 e/ h; u9 ^    # Base case9 c9 J  b% E# v0 S, r4 B
        if n == 0:
    9 ?$ u: r! Q; ~$ u) S2 h* y        return 17 c# l, _7 E; F* A7 L
        # Recursive case) z( g6 S2 d6 [2 [
        else:
    ! f, q- f2 i& ]1 e3 r0 s* i) N        return n * factorial(n - 1)$ p% h" ^: W5 M* u1 F% l

      y) `/ z" N6 c* s8 U, I7 O9 I# Example usage
    + R: ~8 M  g' b$ x6 Qprint(factorial(5))  # Output: 120
    7 ^6 H( V9 R" x; M, `; y
    . K' X5 O- }9 v4 |/ QHow Recursion Works0 I6 e& P) A1 L& Z

    $ j3 p  r. _; x( c# u) J) ~    The function keeps calling itself with smaller inputs until it reaches the base case." S$ K4 r( C+ a5 x

    3 l2 H$ Z% l  k    Once the base case is reached, the function starts returning values back up the call stack.' s" `- _& Y! o, L3 [! a$ n

    3 d7 o) f3 Z. O0 a8 x    These returned values are combined to produce the final result.
    ) F' V) r6 j# g" _! ?. q8 n
    6 S/ X1 P0 _2 q" y; A1 s1 _2 A6 d: DFor factorial(5):. I% y1 b1 }( V) b

    8 j) k$ Y, p* \1 P6 S1 @6 t: Q5 T4 @) w
    factorial(5) = 5 * factorial(4)* ^2 q9 }+ J( l9 z# C# H
    factorial(4) = 4 * factorial(3)
    $ e5 D9 S8 m2 M0 K0 o$ Y9 z- W2 dfactorial(3) = 3 * factorial(2)5 L" j1 R* W/ H& h7 |& J
    factorial(2) = 2 * factorial(1)
    $ k7 Y- L' v1 l1 k3 {5 y+ @. Y" T3 Efactorial(1) = 1 * factorial(0)0 ~: ?) r! D& v# w8 L
    factorial(0) = 1  # Base case
    ! @4 l/ Q4 d5 b" l+ R9 U1 g. I
    1 b" O& _1 {1 G( O' kThen, the results are combined:
      b4 q! a6 C! K1 @& |  L2 N: }% V; |) l( o
    ' Q+ C" M0 f$ U# u. C5 J$ s+ F
    factorial(1) = 1 * 1 = 1" B( S6 d) ?9 R/ ~2 T6 C
    factorial(2) = 2 * 1 = 2/ |, k! _4 C0 {! ]1 A
    factorial(3) = 3 * 2 = 6/ _5 w7 x9 b& c
    factorial(4) = 4 * 6 = 24+ c/ f0 G& b6 Q! ^! _% a! W; I4 ?
    factorial(5) = 5 * 24 = 120/ r& j" }) V& q- Z: K

    1 B8 Y; @% h- f# n% _; Z! x) NAdvantages of Recursion8 Y) a$ ^7 K5 x2 f# _$ }5 F6 J

    9 ]% Z: o" E' T0 A/ i: r& L8 e    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).! \1 M$ V1 p5 {8 {/ p' T
    8 x0 _; ~' v) S. ?: n2 X1 _. @
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    1 e4 Y! [& Z5 H( N2 o6 S' m6 {6 k' f! ^( b2 C  U4 v8 S
    Disadvantages of Recursion; N/ H6 A$ \, l+ M1 m

    5 M  ]6 {  {1 I" b; c6 f    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.
    ; J4 @% Z+ u* ~2 _, J# S7 Z
    0 p- ~3 B6 K+ q1 p    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).9 t7 r6 n. o. m3 G( L

    # Y/ s& e1 t: B9 x; lWhen to Use Recursion% k# D4 b5 k9 f
    1 Q! s$ G3 |/ f+ k
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).; e3 `) y9 i9 U$ N+ _* u4 T
    $ k0 e+ h" d$ ^( |7 ~/ l
        Problems with a clear base case and recursive case.
    9 n7 U4 W$ i9 N( `2 N& |
    & w* V& l- ]8 @" V2 q& [3 y- s. PExample: Fibonacci Sequence+ _2 u4 I$ F% \9 l3 _& f

    4 `0 {3 M' v' U6 @; @The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:( E. l/ @( D6 {8 L6 @" }+ }/ r& i6 t

    * e5 W9 ]- I) u# Y! g. p" I' e+ x    Base case: fib(0) = 0, fib(1) = 17 f7 o0 |; R  G$ F$ X* p/ \
    4 {: z, w- S: E' P3 L
        Recursive case: fib(n) = fib(n-1) + fib(n-2)$ g$ ^, y! K. n' K- Q

    # P* P, b9 n$ \* ]" V, J/ Xpython
    & D7 ?  M1 ~" U+ G: r! n  [& U8 }5 o9 w) x

    : U% K) v5 n8 `" U+ B# r% k3 Bdef fibonacci(n):" W0 x) Y, Y9 x0 i3 n8 K
        # Base cases8 C: N) m# v) @8 a% v8 d
        if n == 0:
    # c" N9 \1 Q& |5 H5 E        return 0
    3 X$ f4 N* O5 r' C/ c+ L/ ?' e    elif n == 1:7 U3 G3 }4 T: j2 }1 D8 f- k
            return 1! O4 i8 n) k$ t' f  P3 v
        # Recursive case3 l8 p/ F: I) s
        else:
    , M3 b/ D, [( I0 S" P; \* I9 Y        return fibonacci(n - 1) + fibonacci(n - 2)2 x" ~+ J9 L3 C4 a9 J

    ' K* c9 U) }$ g% W- @( O! {$ R# D# Example usage
    4 \0 Y4 L' }( d. i' _4 |5 Yprint(fibonacci(6))  # Output: 8, |2 c( E! ?8 v4 L5 V# k; m
    ' N+ @& A+ h2 [6 v; S" f
    Tail Recursion
    ) T: M7 `+ j9 W5 ]  u  a' w  @4 K- V! @7 D8 }3 G- i1 x
    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).: Y6 E2 s, [: `# F
    $ i+ W+ }& s' j. Z- v" {& A
    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, 2026-1-13 08:16 , Processed in 0.055832 second(s), 21 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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