设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 5 n) D' M0 Q" J( M8 ]

    * x& g" D8 v) ]# v1 i解释的不错0 Z, i' @' P7 I6 ]- c) ~- `3 Q
    + \, E5 _3 c. y% a! H+ A
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    " q  k1 L7 {- f- L9 D; O+ y2 u
    + u% N4 o4 v4 f# W5 D2 Z 关键要素& N" z" }5 s, b4 `3 n8 `% t/ ?
    1. **基线条件(Base Case)**. ~  a+ f; {8 d* q. x. e
       - 递归终止的条件,防止无限循环
    * s* M0 W7 I3 G" V' ~; h   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    1 e( j; o$ [! b2 p  i9 `
    4 E2 C) P$ P: U2. **递归条件(Recursive Case)**. s" q5 M  S! h. s: M: H( G' C
       - 将原问题分解为更小的子问题
    / n8 ^2 r5 k6 A) E9 o2 ^   - 例如:n! = n × (n-1)!* p/ F; D  G* r8 C" T5 ?5 U

    ' g# y3 J1 o9 b! O8 Z* w 经典示例:计算阶乘) B" K0 D5 o+ o1 T+ C  s
    python% x" C. n# d- y# o! [5 V0 ^( p8 D
    def factorial(n):% F3 C  o# g' H) @: ^4 i' V6 Z
        if n == 0:        # 基线条件  R' m* s6 K6 w/ G$ x
            return 1: N7 z* B2 v0 o5 C
        else:             # 递归条件" B, ~7 H" ?/ b& j1 [% h
            return n * factorial(n-1)
      \% L( q+ Y3 C) |3 b! h+ a执行过程(以计算 3! 为例):
    " U/ |+ G+ S$ L# [! n: k8 |- u1 {factorial(3)# k" ?/ b% X! Y( F
    3 * factorial(2)5 I3 I; T' E4 }* e0 D
    3 * (2 * factorial(1))
    8 O! M. o9 e  T! [8 W  a* L3 * (2 * (1 * factorial(0))). z4 r6 X0 R# {  C
    3 * (2 * (1 * 1)) = 64 A$ j% y: B% a! x. k3 G
    4 U* _6 Y: S9 ^8 }
    递归思维要点5 j0 L+ E$ W/ A( R
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    5 B2 L% B7 c8 b( a2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    $ r% z* x. d0 B1 @3. **递推过程**:不断向下分解问题(递), X8 e5 I+ D4 }  t' n$ z
    4. **回溯过程**:组合子问题结果返回(归)0 i4 v; Y9 `8 M. N5 G; _; |7 O- t
    5 ^) l8 W2 L$ k( M6 _: S* `
    注意事项
    , v) s- _( _* W必须要有终止条件
    ) [  d: W( U) z: }递归深度过大可能导致栈溢出(Python默认递归深度约1000层)+ }. p; P$ L6 z
    某些问题用递归更直观(如树遍历),但效率可能不如迭代& ]" S* n0 r* _" z4 S+ {( L
    尾递归优化可以提升效率(但Python不支持)" C( o+ }. f$ k: {6 \

    9 ~9 `( R. F9 j6 m6 x5 y 递归 vs 迭代$ P' Q5 i2 c( I5 w
    |          | 递归                          | 迭代               |
    5 F# V+ q" S* k; s/ D! u$ u|----------|-----------------------------|------------------|
    ( ]2 ]: X6 p5 _. Y' S: C: w& v- n| 实现方式    | 函数自调用                        | 循环结构            |$ [; e) V5 o% l. G; K
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    : U) o' q5 x: `; l( K! C# M| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ; `7 ?3 u" y" T2 j% x2 E| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |  \; X% l. ?" T* g* l

    5 O) ]+ m  L, |" d6 y$ O1 g2 A 经典递归应用场景
      g$ G. D" K2 v. @# ?8 u3 `1. 文件系统遍历(目录树结构)
    " q. c6 A1 l, p+ A2. 快速排序/归并排序算法
    / N5 T  [0 L. R6 O6 E" A3. 汉诺塔问题! t3 M* ]# F3 I/ B" t0 W* X
    4. 二叉树遍历(前序/中序/后序)( \+ `# T; ]+ `2 l
    5. 生成所有可能的组合(回溯算法)2 t4 w, X+ ]. y' ?3 G3 C

    + M2 w. [+ ?, ~试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    擦汗
    昨天 06:41
  • 签到天数: 3102 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    4 J0 w( h3 ]. z( y我推理机的核心算法应该是二叉树遍历的变种。
    . J# P% O$ R$ l. N) q" U另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    * z! }# ?( L' @! k6 Q3 oKey Idea of Recursion. j* J% h6 ?( Y) n; O1 g+ ^9 k4 U
    # h& q4 y7 G5 D) H3 ?" m  \5 _
    A recursive function solves a problem by:
    8 Q8 y! \! T4 h2 f6 q3 D) M6 S9 k' a# f( N2 S- E
        Breaking the problem into smaller instances of the same problem.
    % F) i( o# p# M; W; _# k- n: y) ^. P8 Y- o, A' u9 e
        Solving the smallest instance directly (base case).) M+ O! ^& V$ e' P
    7 i. z! _! o3 U. t$ C% T
        Combining the results of smaller instances to solve the larger problem.
    ) k2 g& g& m# o6 [- L
    : _0 G5 `9 p! J, b" I3 a5 iComponents of a Recursive Function  c7 j1 |' S% G8 M

    8 g7 q3 d- r5 W& w% W: K5 Q1 K    Base Case:5 e: s! F+ a2 N( u* m2 [1 G
    3 f) V" w- }, u# B" `
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    % _7 W8 s: n  L  F; M8 e) f7 W1 N# B% X
    $ P) |6 d5 h; r+ n' H9 w2 n        It acts as the stopping condition to prevent infinite recursion./ f" n4 Z& X' A# J

    / K( u( x9 D' w3 v        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    0 m0 l. z; W/ G, C5 o- z) F
    8 u0 _2 h! Y$ ^1 G2 v! |    Recursive Case:
      P% b6 K) e' w1 `9 r( Y
    ) `& d: M2 A) Q+ s* j* J) q        This is where the function calls itself with a smaller or simpler version of the problem.
    % `9 D8 z( W$ n; W3 w5 A- f/ B+ M6 n$ }: A
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).- c+ A3 A% G. e$ ~) }# q/ S
    8 O' v7 G1 a8 J: D" [  R; k
    Example: Factorial Calculation
    ) m, S( [, G3 e) R/ p) N" y( _9 {
    ; i/ ~4 i6 G# j7 m+ LThe 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 I  X4 ^5 m( G

    8 ?( G, u6 D8 |. A: H0 l! `    Base case: 0! = 1/ v; l. d9 c% I; `9 X6 \
    - R8 _& Q1 w; K6 c
        Recursive case: n! = n * (n-1)!
    / e  v0 i7 O5 W, f" E* E4 \  G! k0 I0 p( u4 Q5 |/ {$ V
    Here’s how it looks in code (Python):
    0 m: g% o- ^9 Ipython' @  o3 J. \3 x9 Z* K( R: S6 p
    , S* E* f- z, ~$ P2 q  M0 c. H8 v
    4 B& s; [; }$ x' S0 s
    def factorial(n):
    8 x$ d1 T; X! t  P$ A; ]    # Base case- g7 \& z7 ^+ i1 L& ?
        if n == 0:
    ( j5 O* L; J0 ?% P# [- B        return 13 T0 T$ {( i" \
        # Recursive case
    0 |3 a1 g* Q/ W* z# @, z" s+ K8 @* I    else:1 P: ?: R" u7 d3 {+ F6 F; p
            return n * factorial(n - 1)% o2 A: E* [$ J3 |9 d' K
    0 F( p" V0 G# N$ m: M+ {2 n9 N
    # Example usage# P6 Y. T4 ~: \8 B( D5 y
    print(factorial(5))  # Output: 120
    3 n) m: Y7 k: j0 l3 M6 s9 X# C( p9 ?' J# s2 m$ C  z8 R# T
    How Recursion Works! g3 V; Y; x* J) h$ S$ `
    4 X3 f9 {# e, U" l  r
        The function keeps calling itself with smaller inputs until it reaches the base case.
    # r* }: L9 o. Z2 l7 A" d
    ; {: W, _- N" A7 E    Once the base case is reached, the function starts returning values back up the call stack.- t% T0 i' F1 E* J
    % H8 B/ z. q% R3 N, @& k% F8 Q
        These returned values are combined to produce the final result.
    # G3 H' a5 i0 C$ z  Y) V! `8 X9 Z
    , @  J# l- h9 V2 U) g* cFor factorial(5):  q# Z8 v/ D! _: T' x' }

    & [+ L7 u% V. b( u% Y* r8 i
    8 D- F* [/ e8 S* ~+ ?: ], {factorial(5) = 5 * factorial(4)
    % B; d1 `* Z2 j* Q/ z6 hfactorial(4) = 4 * factorial(3)
    ; E# [  Z* `& Y! j7 Nfactorial(3) = 3 * factorial(2), Q$ H  V4 S: s
    factorial(2) = 2 * factorial(1)" ]# A+ `3 g  Q6 g, N: W; W
    factorial(1) = 1 * factorial(0)
    3 g3 B" d& m& x7 Afactorial(0) = 1  # Base case# v' Z/ g$ ?! X7 b- f$ K

    % n! F! a7 H2 D0 l& e/ ]Then, the results are combined:
    . ]9 C5 m$ O# T5 u
    # k: C5 ]% I8 Z  ?% `. U1 {( V
    # B# S1 U/ r0 C+ L: ]2 }: M" ufactorial(1) = 1 * 1 = 1/ V0 ?) }+ _2 n) t1 s0 ~8 J9 N
    factorial(2) = 2 * 1 = 2
    8 l: T- W# Y' j9 I4 Afactorial(3) = 3 * 2 = 6$ @0 o; ]2 U6 i" e
    factorial(4) = 4 * 6 = 242 n: E! E; U- S8 \8 ^5 t( v
    factorial(5) = 5 * 24 = 1206 y  C5 }- c" ]' @4 C

    $ B( B0 [; ~& B5 }, G5 aAdvantages of Recursion; R4 q$ Q% e) o" Z: ?

    5 A: p; P9 q+ M! w# K    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).! u7 W0 I5 N, Q. R+ N+ q- V$ l7 W  C

    5 h# d& I& ~8 ^3 h& h8 Q    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    , E' Z# y1 _! e% r" G7 W! w8 n! [  q7 [
    Disadvantages of Recursion5 \& }3 r7 b9 t4 R* H

    ; A2 Y# _$ Q* a7 J9 T    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." r. n$ [$ M, b! X+ U
    3 U/ ?# o  _# ?2 s* h$ Y/ J
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).; l9 ]; {; y; J( ^

    ) Q" `$ q! l0 d7 B( EWhen to Use Recursion8 s$ }. _7 Q, r5 W9 h( @

    . z: x/ y, n  ?. h8 M    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    / s/ S! q9 a1 W! Y8 f. n# j& `: ]4 D0 m& q* f- @
        Problems with a clear base case and recursive case.4 g* P* ~! W! g! l9 u
    ' b, z% F6 e% u* Y6 ~- t; B# x
    Example: Fibonacci Sequence
    % D# g0 w/ A1 x- k8 ~0 p+ ?7 D2 N, Q4 F3 w# z# u2 N3 @0 }
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    ! L0 w" B" O- T1 p: v
    . h6 L* ]7 H- P    Base case: fib(0) = 0, fib(1) = 1
    / G# z& R; M  k7 K: z
    4 V  A1 T/ m: Z8 c1 A    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    1 q% U, b; e/ _* M$ r$ p
    ' j) K9 K# a: Fpython
    / d3 d5 U; Q. \3 G
      E" B( A& w( @& ~& Y* Z
    ( f7 w% Z3 u( a& c/ Y. k1 o9 kdef fibonacci(n):
    + |6 p5 U1 d, Z    # Base cases  Z1 \/ t; V" Q% O6 j# z- P
        if n == 0:9 `' Z% m9 v/ ?# n/ a
            return 00 X# u6 q8 F( M6 t
        elif n == 1:  \  i: ~% `9 C7 S/ Z1 a7 ]7 i
            return 11 `+ y( x2 W; \4 p9 P) {- s
        # Recursive case9 \1 @: I' `% a0 H) `' H
        else:; {2 V0 i3 b) e
            return fibonacci(n - 1) + fibonacci(n - 2)3 y+ {# a. S- B5 h8 g

    * a- v# C! m0 g; d( L+ M0 }: ~# Example usage
    ( [2 x& n2 H, v, y1 Qprint(fibonacci(6))  # Output: 8
    ; n+ y, l: ^  a) v3 O) A4 r- e: N" ?' t. `; F
    Tail Recursion
    . q* z$ e! g4 a" A8 s; Z, {/ U- `' Z8 A
    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).
    4 K4 w2 M& q* z/ [' t0 Y
    + o7 c% `# W! H( l, R" kIn 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-27 14:16 , Processed in 0.034906 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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