设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    - B* f* @* F9 |, R3 A
    ! D: Q8 `  V' j解释的不错! f. c) B. }! f$ R1 S
    3 S" E0 @% y! _4 W) r
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    + X% ~8 l, l6 z! n' A/ H+ e
    : p6 m5 e+ m; _  {9 ? 关键要素
    . i; F# z; u% }: Y7 Q9 X5 V1. **基线条件(Base Case)**
    2 f. ]% w8 {- V7 g  |% g) k* o   - 递归终止的条件,防止无限循环
      ^2 s  I& s: Y6 W   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    + s( y2 B$ J; H2 o; {
    & f& ]4 @& F+ }/ R: x2. **递归条件(Recursive Case)**: r: @" i6 [, C2 d; K' |7 d- V. n6 M
       - 将原问题分解为更小的子问题0 t1 a# j) V+ `( K7 |2 ^5 O- y
       - 例如:n! = n × (n-1)!% r& R+ ], u6 y3 K* ~

    7 V  L+ }9 V0 |! j( H& i) E5 ^ 经典示例:计算阶乘+ `2 q. k3 T+ d. |% g2 B- W
    python. o; z5 S: r+ T
    def factorial(n):
    # I/ v( t5 `  K9 ^3 }' ?    if n == 0:        # 基线条件
    2 o/ a3 i9 G1 h- m9 ?! y- Z        return 1
    : U3 w* E$ ~! `& n" h$ d: u5 ~    else:             # 递归条件& D" \/ _: w; f! v; @' H
            return n * factorial(n-1)
    $ v+ _/ {) U9 {0 o执行过程(以计算 3! 为例):
    6 T' E& g8 g) H" s# f% g: ifactorial(3)" F9 S8 t- M% y% q+ m( I4 E  S! `
    3 * factorial(2)" d& B: A0 J* O) a( B) @% b0 }
    3 * (2 * factorial(1))
    ! S2 N! ?3 Y. @8 z& j3 * (2 * (1 * factorial(0)))
    ) t- C( b9 O! R* D  _0 q  W& l3 * (2 * (1 * 1)) = 6
    $ i8 ~6 w2 B5 Z* M! v$ W. Y, o0 o- q4 l
    递归思维要点8 L5 A* D: e; S. @0 Q! i
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑# s( D+ m4 ?& @) n+ m7 A
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    # W; X$ c$ W7 {8 V/ o" `/ Y" k+ ^3. **递推过程**:不断向下分解问题(递)
    . ?& m9 h$ @" ]0 m% \: _4. **回溯过程**:组合子问题结果返回(归)
      D* ^; t4 R( m: N
    % n5 q* e. A3 n- k( x1 J 注意事项) q4 k) g' f; a0 H0 w8 ]# Q
    必须要有终止条件
    % ]( N- t5 I# r9 r递归深度过大可能导致栈溢出(Python默认递归深度约1000层)% B, A: L6 {& l5 A3 t
    某些问题用递归更直观(如树遍历),但效率可能不如迭代% r6 [6 y) @' `: h) w2 V8 l
    尾递归优化可以提升效率(但Python不支持)
    4 g$ v* }5 T6 d5 j# a# h4 N* `5 E# W$ k$ C/ P" O$ v8 l
    递归 vs 迭代
    7 k) g; U# ]- S7 `! p* o3 Q|          | 递归                          | 迭代               |
    ( W5 e  Q3 W9 B# ~9 ?6 F# f3 z9 R7 [|----------|-----------------------------|------------------|& Y7 b& p+ w/ B2 h  C/ X& y
    | 实现方式    | 函数自调用                        | 循环结构            |
    ' E% e$ \7 E$ e% o: x8 k$ f) r| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |% P3 Q. d: T: |( b" I7 {
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |: p' Z" A" y0 z% b/ L$ u( S2 L
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    1 G* h) b4 e0 l$ p, `" g0 l: J3 m5 y. G' M7 @" I8 d+ l4 f
    经典递归应用场景' u  r6 u& `2 `: i' S! F, C! N
    1. 文件系统遍历(目录树结构)# _( _- j1 g6 y4 ^
    2. 快速排序/归并排序算法) r5 Z& c6 `7 }
    3. 汉诺塔问题. W. |, H1 h* @! n9 r. y
    4. 二叉树遍历(前序/中序/后序)$ M4 T3 V; X: g( K
    5. 生成所有可能的组合(回溯算法)
    3 b( h  H- p9 `: q/ A
    $ l9 B/ D, r0 w$ w& l0 w试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    慵懒
    昨天 07:13
  • 签到天数: 3112 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,0 Z' Z4 Q& y4 k! @' ?
    我推理机的核心算法应该是二叉树遍历的变种。3 H) [8 e5 M" c5 s9 }! Y$ m
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    $ q7 m$ a+ K3 N4 Q  d# _Key Idea of Recursion
    ; q/ C, s, x6 ?! c5 J/ e8 F, L+ @+ W! j/ T9 V9 P
    A recursive function solves a problem by:
    ( T' q3 l* Q- K# Z
    ; l/ @# ~+ R! K% g3 w    Breaking the problem into smaller instances of the same problem.# A: L+ E! t4 S8 n+ G

      k6 t: I( P9 x1 q    Solving the smallest instance directly (base case).
    * u) C  V# E- ]4 G- |* O0 T( r' m- f& V
        Combining the results of smaller instances to solve the larger problem.- r1 `$ q" ?1 c, t. G% l& @0 ^1 D0 N

    ! W/ [8 l8 }; z8 IComponents of a Recursive Function" R# P  H6 C4 s% Y/ y; q  K
    , \; F2 _; ~3 P
        Base Case:
      {8 ~) B4 j7 m2 _% a
    + w7 f! G1 q% H7 r9 L        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.: E0 l% r4 J/ t  v" W; \

    ' w, E. K2 R9 _2 C6 w        It acts as the stopping condition to prevent infinite recursion.7 e* v4 ^$ v- r8 j2 ^
    : n$ I6 o5 V- Q' J9 a8 L; J
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    4 l; ~7 N% M$ z) p4 l4 C/ @; z8 N( u2 \: Q* d1 T# s& y
        Recursive Case:
    / H5 F* ?1 o" v; S2 T
    1 b+ N1 d) T  i% }$ P        This is where the function calls itself with a smaller or simpler version of the problem.6 u. f) z0 M# u, c1 A

    4 Y8 a+ K( W% }        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    : M; s. i9 V( ?* ]3 @4 p4 n, O5 B8 [# J  {+ X% J1 ~
    Example: Factorial Calculation
    ) H4 n, [( a& h1 Z" Z. ?
    $ e5 X% A4 c) ]' \5 X# f* ?( wThe 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:9 H' f8 o$ b$ E

    6 S- I' K7 _/ J! s" @7 `' U+ j    Base case: 0! = 1
    0 p1 t' \) N# {$ I
    8 f$ t5 q* Z8 v: f    Recursive case: n! = n * (n-1)!
    . \' d1 x% C) Z* W
    ( ~+ p3 p. l/ V9 [. {Here’s how it looks in code (Python):
    / m5 e2 C6 _, @7 ^7 bpython
    ! A0 T( p% s7 G) {" {( t3 e, E  A0 N2 s$ p* ~) X
    ) a! b/ a: B/ ~- L3 \
    def factorial(n):4 O0 e- F; T" h) h1 H
        # Base case
    % b  d7 N4 V: l3 {6 Y% ]0 A; n    if n == 0:8 I/ y" j: x3 b0 G, g
            return 1/ D1 P8 E* G; ^4 h* r" [
        # Recursive case
    ; i: H3 p& U# }" V# C    else:
    ( e" n% [8 s5 @6 C% w' d1 R        return n * factorial(n - 1)) U* s) u9 O4 e+ g, k6 g
    ( W0 q2 o) I1 ^. d. T. m
    # Example usage
    2 l0 y" I2 w* K) e; O  uprint(factorial(5))  # Output: 120
    + }" ?: U9 J8 t% C& z: H
    9 G1 u# a" y8 Q0 C3 z. vHow Recursion Works6 g( o) Z8 N4 v, P( `  D1 s  q

    . P2 z& T+ Y# D/ I. S    The function keeps calling itself with smaller inputs until it reaches the base case.! m) v& v. S8 N. ^8 v& n; ^& `  c
    : ?" z7 c' O' U
        Once the base case is reached, the function starts returning values back up the call stack.
    8 z5 p& K  y# ]. A3 A1 w) U/ ]! f: {' q8 V2 A5 A! }4 Q* z7 {2 |
        These returned values are combined to produce the final result.- T3 O1 A. c: y

    9 x( k0 N( Z$ X3 p4 XFor factorial(5):% b" A* w. g4 Q/ a

    " A" m1 h% C0 r: q) S+ u7 a/ }9 y' l* y% \/ N( M) i' Q
    factorial(5) = 5 * factorial(4)& h! ]7 t0 I5 O+ E/ x, P
    factorial(4) = 4 * factorial(3)
    4 ~3 W4 u; y$ `factorial(3) = 3 * factorial(2)& K. P. W$ x; W* S* S; {) c
    factorial(2) = 2 * factorial(1), a4 ^# f; @0 ]$ u4 x' ]: Z  {  w
    factorial(1) = 1 * factorial(0)2 `8 ]* V' i. K3 W+ ~
    factorial(0) = 1  # Base case9 t$ l0 R% W6 J, {
      q0 L, T. x* P& j2 W* `
    Then, the results are combined:, a+ P% t  ]' N* m# \
    0 o. v- t' a+ Y, d6 R
    2 t: ~( \7 ?1 f% e
    factorial(1) = 1 * 1 = 1, G) x* |% {' e  y: d7 z' I3 [
    factorial(2) = 2 * 1 = 2
    & H% U) s9 V% G# ?4 Afactorial(3) = 3 * 2 = 6# p, v, a" K- B) X) ~9 N; C# a
    factorial(4) = 4 * 6 = 24$ Q# X" `' w7 r2 I
    factorial(5) = 5 * 24 = 120
    ; C+ n# u0 N( h2 I* E8 _
    : g( X* F2 r+ E7 OAdvantages of Recursion
    % n1 G. g: N7 ^8 R
    3 n3 u- \8 q7 C0 d    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).6 J" o" c, i+ g+ O$ O

    ; p1 \0 g& a. x. ?* Z    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    * e/ V' D& _) F- v' I0 i9 z* J4 W$ e8 d
    Disadvantages of Recursion9 n3 W) X* g2 g: D

    " e9 {5 I4 i, Z* M) }) b! C    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.
    9 |5 ?$ t+ n  Z+ C; W5 f8 {; }: H7 s8 D
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).: Y% C& u5 h- w8 D5 z

    - d( T1 W; R* h: p- Q8 x* V2 h" yWhen to Use Recursion
    , B  ~2 A  {( A, V# J: N- p' Z
    ; v) k# l6 O9 s! d, O2 [% Q2 q7 }    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    0 j/ ~) z+ K$ Y& \
    5 J1 W! |' e$ j0 D. i' J8 ?    Problems with a clear base case and recursive case.
    : v* `4 M3 l; q. ]) F7 k3 C9 t4 W$ ~0 F0 N
    Example: Fibonacci Sequence
    1 b4 y' T$ g7 w& F7 M1 I$ f) Z" s; ^) Q" |( K  U) o( ]
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:& w7 J5 n+ z: k7 L+ k' \- ?  k

    & k' G5 d4 I# e- C* p2 A    Base case: fib(0) = 0, fib(1) = 1
    7 Q# z! K0 m1 F  M- _. r0 V1 }
    , C0 b# m2 w" G  Y7 W+ r6 M; G    Recursive case: fib(n) = fib(n-1) + fib(n-2)" e, L) C. M( O  s) N8 j8 D1 d# l
    / }7 Y8 N$ L) I3 b7 d0 J8 }
    python
    3 M) q1 ]! m9 a
    2 I$ G$ o+ \6 u" b& A
    8 d& k5 S0 H% m% R" ?def fibonacci(n):
    0 J% v1 d3 ]8 r& ^    # Base cases
    7 \6 q  Z' ?4 Z  ]- H    if n == 0:) P: Z( m( m# J0 m: t0 p
            return 0
    0 S( B, _/ z6 N1 u2 ^3 n    elif n == 1:/ O/ c" b; P% o, O  k9 I
            return 1
    * P4 s" R" }' K* P8 B6 ]    # Recursive case. i& u0 ]& H! O' `: j% G! \  N
        else:
    ( S# v3 I/ ]. _# K8 Q5 z5 s  ]        return fibonacci(n - 1) + fibonacci(n - 2)  `' W6 m2 L: S( e
    3 u2 i# W, e  q2 i9 y
    # Example usage/ i0 O3 e5 F% O2 B5 {  u
    print(fibonacci(6))  # Output: 89 B1 }5 f: B0 f6 ?$ F' @

    $ I* }2 T8 x1 QTail Recursion7 |! M% {: b) _: T1 H  Y+ g

    # B& g/ Q+ f3 i* STail 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).) ~8 g! r7 f% w$ g# \/ [
    , v/ ~1 e/ M& ~4 w6 o
    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-12-9 01:50 , Processed in 0.049658 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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