设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ! {' O0 }# w/ @: F- \+ u8 B
    ! D# _; W" H2 |' }: I$ w解释的不错
    2 `+ ^0 _) r& q* R2 J. X6 @/ h6 K4 J! k* Y! |6 ~: k4 `9 s1 T2 _* U
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    . r6 f: _" H0 ^8 Y) _- s
    6 z' ^2 ~' `! C$ D, q: q+ Q 关键要素
    $ p$ Y5 K& G- v1 L4 ?" o: M- }1. **基线条件(Base Case)**7 X; W' O* T( ]; n/ [
       - 递归终止的条件,防止无限循环3 X) g2 A& P. t; T
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1; |  C0 G1 P8 v. o1 _

    ( v5 t, ^+ F% z1 M- m2. **递归条件(Recursive Case)**  i* d: J5 B$ r% \: Z% B( ^
       - 将原问题分解为更小的子问题
    0 A2 R5 ~8 ?5 n9 J   - 例如:n! = n × (n-1)!9 y5 L7 ]' l, {5 R6 o

    ) A* b' `/ @) e! e/ N( t4 l 经典示例:计算阶乘1 d/ x$ m5 C- K
    python8 s" k- p" B) V  z0 F3 l/ c
    def factorial(n):
    # U4 \; `" T" l* Y) z4 W    if n == 0:        # 基线条件
    , h1 w) j/ g% E1 \8 J0 f        return 1
    5 r2 e( E3 F& J/ N+ O% D  K    else:             # 递归条件/ W; Y) R% J. v2 E: |, e
            return n * factorial(n-1)7 a' K0 K2 W' s$ J
    执行过程(以计算 3! 为例):8 \! F$ @- k! T; r1 {. p  d
    factorial(3)9 o+ N0 Y' }: [. w  E4 G' K3 E
    3 * factorial(2)8 p# O. P3 n* S4 D; s  I0 s
    3 * (2 * factorial(1))
    + `4 P: w6 ?: R+ i3 * (2 * (1 * factorial(0)))
    ! L5 ]2 B# C& \$ S. q* T" t3 * (2 * (1 * 1)) = 6
    & w  Q( k/ N  C1 F8 x" j0 s  k7 ?0 Y2 ~- b
    递归思维要点8 g+ s( K8 u/ A
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑' \5 Y6 j! X0 w+ J% j% g3 i
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)9 ^% Y# i* `( v# g$ U. q2 Z
    3. **递推过程**:不断向下分解问题(递)
    7 L1 f. B- r+ D1 i4. **回溯过程**:组合子问题结果返回(归)4 p* {7 Z3 [5 F$ X7 h

    . p$ ]( U) O7 D% W 注意事项
    5 J, E  d! C* J) v, f' v必须要有终止条件
    , Q9 s& Z. y; n. R2 x& \! P1 l递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    : O7 Q4 `" B5 P& w某些问题用递归更直观(如树遍历),但效率可能不如迭代1 Q$ Q9 y  r0 I2 ]7 l
    尾递归优化可以提升效率(但Python不支持)! I; C( q/ D. d9 X) c: U( w! X* A

    4 y1 m9 @) k5 l) O- `: d0 M 递归 vs 迭代. [. d4 x' e1 Q# X( M2 u
    |          | 递归                          | 迭代               |+ G# R# @! e4 A; v. A
    |----------|-----------------------------|------------------|9 ?1 W1 D4 k6 E( p6 x; u0 U
    | 实现方式    | 函数自调用                        | 循环结构            |; l6 j/ O, w0 V1 l* e, V# O9 `
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |0 j1 n- l5 ?2 t% L% }# Y% q& X) L
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |% @6 \: I" V" E" c* T9 P" q) q
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    . a* G6 G$ R! k' i" X( Y% t3 I8 a$ O, p/ y  h+ N
    经典递归应用场景$ G% I0 @1 w: y" c0 r* q
    1. 文件系统遍历(目录树结构)
    * F3 @# t" c7 b& N6 b3 p: h2. 快速排序/归并排序算法
    7 x1 b0 s0 i" r$ C3. 汉诺塔问题
    ' j  K4 s0 Z* `8 q( F4. 二叉树遍历(前序/中序/后序)9 H9 s+ U" k! C3 S, I8 M' N: h4 H  m
    5. 生成所有可能的组合(回溯算法)
    7 M) V! W+ R% [2 g9 g  C# a
    ( i5 y2 P" ^7 j1 I试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    昨天 06:39
  • 签到天数: 3105 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,; D% k0 Q* ]! w. X4 A2 g
    我推理机的核心算法应该是二叉树遍历的变种。9 O7 P7 p6 r& M" [; N4 v
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    ( R  N3 K- r6 @Key Idea of Recursion
    ! y/ W1 m0 W) |6 X4 F9 g0 _" P" b' Q% z, L" c- l' G6 X
    A recursive function solves a problem by:8 }0 p( h3 L- K! H6 M+ T, b

    2 c' v, o5 x4 b' v! k    Breaking the problem into smaller instances of the same problem.
      B; H+ ?& x7 }5 _: E0 k7 `8 L3 g0 W8 w/ J% X* N/ A' O6 r
        Solving the smallest instance directly (base case).
    : L. l, ^) m& T  J# h# c1 h0 L
    # C) s' R6 ~% ?4 V( d$ ]/ H    Combining the results of smaller instances to solve the larger problem.
    : A! s- K7 J% r2 Y' F' l3 a9 t7 X: W& P6 A* ]- ~3 t  b* V
    Components of a Recursive Function1 j: @4 T& g9 @; a, v
    ( f( R% q$ k# S& C' _- B) v
        Base Case:
    8 X! `  p3 q. ~' k7 L. T  r& {7 @9 S* {: S( b, [! s1 D
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.' _- \3 i" k2 k- M1 z9 w
    . A: f# ^3 G5 Z1 z
            It acts as the stopping condition to prevent infinite recursion.5 \$ T& X, L# q" c0 U4 @

    & k4 a4 F& N: x! G# e+ ~        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.8 {$ h% F2 `6 ]/ D9 E- P

    # G, \! a. h& C9 m' ]    Recursive Case:
    ( ^1 R( `5 K+ u* N; Z# S0 M( \1 @$ {5 Y8 F: P
            This is where the function calls itself with a smaller or simpler version of the problem.
    $ P$ X+ N2 I/ J# a+ }4 ?
    6 J0 k$ O  d! t$ O, ?' R        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).7 a1 X, B" D. h" B# p, C
    ) z3 x+ x5 P$ l1 r' W
    Example: Factorial Calculation
    ! ~+ @& T9 S# y: X. b- r: z' \3 n2 Y6 Y# L) ~* ^3 x
    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:5 Y5 _5 [/ }1 ~, m2 E. ^

    5 _' \" H2 W- J    Base case: 0! = 19 i: L7 d  r$ T" [+ W  m" _

    & }2 I" g9 ^2 e% R& c0 z9 |1 c    Recursive case: n! = n * (n-1)!
    . D% t6 P1 [- b9 o5 I/ q3 X' o1 R5 [
    Here’s how it looks in code (Python):! n" F% `# R% Q* p4 Y8 h
    python
    7 Q4 Y$ [2 o$ M$ V1 Z# c8 g. J6 V) t6 @; p+ R5 b
    3 ~' ~* E/ ]$ u  z7 _5 |8 J
    def factorial(n):  i0 E) r3 D8 W% J
        # Base case. W* L9 Z% P9 Q( e& A# S
        if n == 0:4 H8 R8 }/ p9 Z  L$ ]0 l5 f
            return 1
    - `3 R- r; y: F9 t    # Recursive case
    / r" j! ~# {7 T/ _$ T( @. a    else:
    & V% H+ u+ G. `+ U& M8 }6 j6 J        return n * factorial(n - 1)
    * Q% D9 q2 u  `! x, C/ J8 N, e5 e4 Y; l7 w4 |6 J
    # Example usage1 A1 u- }, L$ A
    print(factorial(5))  # Output: 120: ?( ~' ~$ A- m
    " r$ [4 i1 h  @; h" d$ ]- n
    How Recursion Works1 F7 v  D$ I4 T& K9 e2 c. o

    0 _) d; W; W  ^) w& B9 p- v& F    The function keeps calling itself with smaller inputs until it reaches the base case.
    & d" K& H8 n( r. X! a+ a6 }. N+ X+ y6 u# R
        Once the base case is reached, the function starts returning values back up the call stack.1 Z4 d. O) ^% B. X/ W+ L

    8 h3 z1 i2 g0 B    These returned values are combined to produce the final result.0 U- f+ T$ G) I: Z, F6 n

    - Z4 {& v2 a, x+ C2 r: q& |For factorial(5):
    2 S- R* H7 l! Z& y8 \* g% v0 b5 a: j6 z

    6 j* L# ~9 V- R8 U: ~factorial(5) = 5 * factorial(4)$ {0 |, x8 p; B" d3 v) s2 O
    factorial(4) = 4 * factorial(3)) R. g6 S) `$ }- v( W0 u
    factorial(3) = 3 * factorial(2)& H: B/ N' z9 F
    factorial(2) = 2 * factorial(1); n+ r$ \9 O2 K; q- n
    factorial(1) = 1 * factorial(0)4 O, m/ m- S5 ~+ Z$ j8 @- J
    factorial(0) = 1  # Base case! B9 Y4 g# L9 m: a$ g

    # {% s% h# l. ^- hThen, the results are combined:" L6 v) Z4 s- \
    : Q( j, C1 R2 `/ l9 L

    ( D! U8 k4 o8 s5 u; I5 ^( efactorial(1) = 1 * 1 = 1
    1 D/ d9 Q* P3 B9 x1 c6 tfactorial(2) = 2 * 1 = 2) Z7 v% z( V- D: c: q
    factorial(3) = 3 * 2 = 6
    6 }/ b* V' C6 E0 {* `* j+ a  Y) pfactorial(4) = 4 * 6 = 24
    0 y) c' j/ A) X% p$ xfactorial(5) = 5 * 24 = 120
    ( x3 z$ T1 {  \: q
    ) ^0 W2 M# H4 T: vAdvantages of Recursion, w, ]6 ?+ n- I1 L" n2 J- `

    0 _9 c- M$ W& p  ~! N+ h; w    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).
    , s$ l6 g% h) v+ p
    0 ]0 Y. x' _  y( a5 i! w    Readability: Recursive code can be more readable and concise compared to iterative solutions.0 j! `6 r0 c; w; K9 i+ x) |
    ! X8 O( h4 q" V  w3 W
    Disadvantages of Recursion( `4 s% b3 C  I6 E
    2 f+ j/ w  E/ B# f4 l. t( 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.. j. s6 y; b/ i- T4 r- _
    3 k1 S1 n& \. z
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).. T& k2 ]% d1 b4 W6 O3 a

    / a5 _2 y9 @. s4 X$ EWhen to Use Recursion
    4 n4 @+ H. v- X5 H0 D! _5 W  l, G/ X- J
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).. D, e! i: L: O; A  ~" j
    3 f  O$ _6 u2 p2 F
        Problems with a clear base case and recursive case.
    % S: s3 K: U, n  T+ [' J& t: w8 z9 G1 q% d
    Example: Fibonacci Sequence4 W1 e! s4 L' h' K  P5 E0 M

    ) y) U6 T, C* {# o" sThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:" N" _. O4 R" D8 s+ z

    6 T& h% j- P! p7 b2 l6 Z    Base case: fib(0) = 0, fib(1) = 1
    ) ~$ u- a8 x! U, W0 V2 E
    3 X, _) W* d: @4 }    Recursive case: fib(n) = fib(n-1) + fib(n-2)+ n: `) B/ T  C' I/ T- }* b& T
    $ Q* ]9 }9 U1 q+ ^
    python5 M4 y1 w+ o2 |# C) [9 }- ]

    ) H9 L& Q2 c. l( H
    7 l. Q8 ^/ r* y6 K, s1 U" Odef fibonacci(n):+ [! p1 }4 M4 y; N+ Z6 c* A
        # Base cases
    8 x' ^! s# e  `( ^4 ]* @1 Q  o6 ^, e    if n == 0:
    - ~" a5 h1 g% O" c  w' W        return 0
    * }9 A+ z0 O8 M8 Q* ?5 R8 X5 s    elif n == 1:1 Y6 @9 A( ]0 L# W+ p3 M# l& M1 w
            return 1
    5 _5 k. |$ }9 T0 N9 }    # Recursive case
      Z9 Y  ~: y3 v6 }. I- g  ], W  j    else:/ k0 u9 B$ d/ O/ s) ^$ x
            return fibonacci(n - 1) + fibonacci(n - 2)3 P3 j8 O4 `* J8 q, Q. p3 ]/ Y
    7 z! T6 x0 ^" [7 y% Q
    # Example usage4 V% t& U* M9 c2 |9 {' N
    print(fibonacci(6))  # Output: 8
    ' M6 f, N+ j, m/ H& Q! i: I; N! e
    8 f% ]8 W" `0 E$ p' |Tail Recursion2 W7 e6 c( `9 S& F/ t
    * Y0 [5 L; y2 o  H3 @7 S
    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).* W* A4 \( p/ Y7 Q
    0 i  f- q9 Y# K% S% d3 C( h- 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-1 08:26 , Processed in 0.036125 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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