设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 5 ~! \! M6 v+ l" K7 [
    4 C" E4 x  S% H, x
    解释的不错
    . h. C" u8 A! ~+ `8 i$ \/ ]; K; S8 ?/ x
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    & _" v9 \8 ]  q; Y% V2 X, O2 `
    ; Y$ q7 M& y8 I" O2 Y 关键要素+ ~- o5 G5 l) X
    1. **基线条件(Base Case)**
    0 r& n8 s  V3 V2 }  F0 X' z4 n/ ?' |   - 递归终止的条件,防止无限循环
    , P" m- Q6 F- `# y- [$ Z' `6 @   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    - L  N$ b- B  ^; t9 a+ c' j/ M) R2 s0 n& }7 C
    2. **递归条件(Recursive Case)**  O. J" P  r% n* g" [( A# o
       - 将原问题分解为更小的子问题; e! u5 _% c# h3 r
       - 例如:n! = n × (n-1)!
    ( Z9 U; n! H/ s! @6 P, {# |' E- X9 O( Q) D; ~
    经典示例:计算阶乘
    2 t5 D3 E, x) Z" Gpython
    7 M7 q' }/ ~) c) A; i# ?: g- gdef factorial(n):4 d2 e2 `5 _2 N: P! ~) A) F1 L
        if n == 0:        # 基线条件
    1 J& O; p: Y" A! @        return 1* Z! w( h+ a# G9 b/ m& ^% r
        else:             # 递归条件, X& K# h# p& ]6 a* B( P# [
            return n * factorial(n-1)
    ' s( w$ k$ L7 r( |' k执行过程(以计算 3! 为例):
    9 A* K5 \7 d, I1 y  h" G4 Ffactorial(3)
    ! B) E% Y2 |5 D8 N# O% ~. l1 G- r3 * factorial(2)9 x+ j, m: Y! @+ r5 s
    3 * (2 * factorial(1))* ?" R& I+ J# V1 C% `6 h
    3 * (2 * (1 * factorial(0)))
    + q* l9 w$ R+ b4 f! v3 * (2 * (1 * 1)) = 6
    + {% t9 t- a, F' H+ j+ ^* H, U- k( b
    递归思维要点6 C, w% P5 O% i- i* B
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑3 N1 ?' R  v+ t# |0 m- _' d
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)2 [' u6 G  Z  N& T" ~; z
    3. **递推过程**:不断向下分解问题(递)" r2 q$ W2 ~7 N3 P
    4. **回溯过程**:组合子问题结果返回(归). C; E: I" [9 r/ b1 O9 M6 @

      u0 d; K% C  I0 A* l# W% }) w 注意事项. ]! _8 g1 V* W/ ~0 h5 T5 E6 e
    必须要有终止条件
    % {7 _& E+ t) x5 I; X$ P9 f+ v* S递归深度过大可能导致栈溢出(Python默认递归深度约1000层)0 ?, `& K/ F) S+ M3 h* A* y5 K) p- I
    某些问题用递归更直观(如树遍历),但效率可能不如迭代# c* ~: Q! }$ l5 h# ]/ ?
    尾递归优化可以提升效率(但Python不支持)
    + N# D: N: `, h- ]" M
    3 e( _& y3 X8 ` 递归 vs 迭代# E' ?8 m; d: @$ T5 j- L8 a
    |          | 递归                          | 迭代               |
    - c9 I# z$ H) ]2 |1 o! @# h0 U8 C' h) f|----------|-----------------------------|------------------|2 I: F9 `* C. r" C* K- w; q" q
    | 实现方式    | 函数自调用                        | 循环结构            |
    5 L6 T" U: r; d3 \+ t| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |  |! K6 G2 |  x
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |: d" v1 x- x, `3 u8 j! i
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |. ^( j+ `8 X3 b  R) ]& \: y" P
    / ]: C  \4 J# K; {: N
    经典递归应用场景; f$ @. k+ A( `: o7 t3 `5 B* j. o' ?1 w
    1. 文件系统遍历(目录树结构)
      ^0 G) _7 Q7 c. @; y2. 快速排序/归并排序算法
    : u7 H: ?* d$ i: W# Y+ L1 Y3. 汉诺塔问题
    , O9 [1 o* _" ~4. 二叉树遍历(前序/中序/后序)
    5 W+ g3 b, U" S* z# T" H, P4 z5 V5. 生成所有可能的组合(回溯算法)5 Y) t. M, c3 P! y9 P; j
    ' b6 J7 h4 H( Y! d* M; ^
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,6 \/ f( @, U5 T% H* M$ v* u
    我推理机的核心算法应该是二叉树遍历的变种。
    % W0 R1 m5 l1 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:
    , I% L& u+ G0 Q# r- ^Key Idea of Recursion! _4 y) n8 ]& r- J- b: U/ B/ C8 m

    . j* s0 H" S2 q# n, F/ iA recursive function solves a problem by:
    . Z& ]7 q$ u* S2 x
    ; `8 ]# s1 T5 L" R2 h    Breaking the problem into smaller instances of the same problem.7 z/ u# z& ^- K5 k, @
    % y2 N% S: X2 ~9 I
        Solving the smallest instance directly (base case).% H5 z* g3 v  A; W5 X
    4 r6 @$ @8 W4 C5 D
        Combining the results of smaller instances to solve the larger problem.
    : V  I# A/ T& ^2 D7 T
    9 p# R8 i; q  x& C, G" J0 PComponents of a Recursive Function+ A) m. h/ ~& U' O, {( q- Y  F2 X7 B

    ! E! J: z, j4 y2 C6 O* X. \    Base Case:
    . D1 y+ m& ]" g0 P  n% A/ z" A* X* g4 p
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.; M8 }" G6 w7 ~: `2 h$ ]

    8 L" p2 {& G7 W0 [        It acts as the stopping condition to prevent infinite recursion.
    4 H& b" a7 e7 G" L; d; G0 ]- [+ Y' E0 e
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.# a5 R* e- U: L. T9 R& T1 o

    ( g% S4 E% d' L# t3 B, K    Recursive Case:/ ~. }8 X& [: g

    1 A) H0 d$ s" |& E1 Q3 \4 k5 l0 u        This is where the function calls itself with a smaller or simpler version of the problem.% b7 _, O' D+ q* O2 j/ P# t

    & F/ H( S+ O1 J8 A9 _' p8 |        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).) x1 b0 `( E: c2 s0 ]1 S
    & _$ ^8 d2 b# I3 Y4 w
    Example: Factorial Calculation" ~# T/ k7 Q0 [' ~, @# B  R

    3 ]$ l7 R, x# N: x4 JThe 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:& W5 S8 |1 E" {7 S8 ^
    3 D! P6 l: S  m" G
        Base case: 0! = 1( C/ G) J( |- D% O2 ]3 y8 t

    5 t5 F+ c0 O0 }9 C( [. k* \" F    Recursive case: n! = n * (n-1)!9 M' i) d; x' O9 i5 X
    7 B, J: q# R! k# X
    Here’s how it looks in code (Python):( Y% `% g, H/ n9 Q4 e4 q
    python
    1 E+ C& O; N( z$ Z
    : R: h8 n' p& k( o6 D, P. Z* m3 p- C. _4 @. B; r% z4 v
    def factorial(n):
    # B; ~, R2 p( F- _% u  G    # Base case
    4 N$ S! _8 B. O) J# N' ^3 L( |    if n == 0:- s) T8 n: h4 F* Z2 x$ M
            return 1" z2 h& K7 d* Q, y8 f- Y
        # Recursive case
    ! @8 t  S" c4 h' j8 `    else:# n6 v" I* N# ]: P2 p6 q0 `
            return n * factorial(n - 1); J4 h0 R  @# n% U. H8 n
    , o* l; q. e2 c5 y
    # Example usage
    2 l" i. K: W1 ?print(factorial(5))  # Output: 120' W4 s1 D8 k# X2 E. v/ |# h4 ~; l

    " s% t, N7 z, ]5 [How Recursion Works6 S! l1 l/ }, {  a7 u- F2 a9 ]  s
    3 x6 O7 D% i: D+ L
        The function keeps calling itself with smaller inputs until it reaches the base case.
    2 r& E* S! j/ N) q, N' Q: L. r, E; r5 f  w% I8 q- a' t
        Once the base case is reached, the function starts returning values back up the call stack.. N$ K+ P/ |9 ?5 F: m
    - }2 [3 |  \- ~& H5 Z% O
        These returned values are combined to produce the final result." P/ I2 b* }4 y1 f1 p: H4 L( j3 w

      l' E/ o( q5 D( o# |; kFor factorial(5):, @% S- G$ T2 F

    * z- ^* R4 Q) Z: G+ S" J4 h+ W5 |( v, {9 L8 n1 t: A) g
    factorial(5) = 5 * factorial(4)
    ) t. L3 Z2 @$ q- X0 F" k; p% Ifactorial(4) = 4 * factorial(3)6 T8 Q! E- G7 A, Y. g
    factorial(3) = 3 * factorial(2)
    2 t* d+ R  }: @, W) N9 Pfactorial(2) = 2 * factorial(1)' b+ |% H+ K4 v5 b
    factorial(1) = 1 * factorial(0)
    , m+ T- ?4 t  J. Q( Dfactorial(0) = 1  # Base case
    . J3 a' W1 h5 O9 M& D' H
    , ^+ b0 o/ \# P1 @4 G4 XThen, the results are combined:+ ]0 W: G" z- T. Q( d9 @

    , w  C6 m5 V" {' }0 V, Y# c5 Z+ k7 M4 I
    factorial(1) = 1 * 1 = 15 Y' n# T- W( `6 j. @
    factorial(2) = 2 * 1 = 26 b- L6 Q5 W; g& S! u5 l6 G
    factorial(3) = 3 * 2 = 6" v2 q$ Y$ E: ]. x0 L: i) ?
    factorial(4) = 4 * 6 = 24* _5 V% m% {6 C+ V- N
    factorial(5) = 5 * 24 = 120; N! ]8 \9 _5 b4 u3 t
    & E/ ]8 E8 Y/ T! o4 @
    Advantages of Recursion: m- \  \& h6 ]) v: [6 s+ F- b
    ) m* n0 _% N0 W) j; \8 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).3 a: G0 d! A* @! Y
    5 Z4 R2 p0 V+ l3 w
        Readability: Recursive code can be more readable and concise compared to iterative solutions., d2 O% ^( P# q6 H
    & D' Q$ l( P2 c' \2 Q
    Disadvantages of Recursion
    & o2 q2 F1 q- c1 c; z& m/ Y' X) ^5 K; D/ ]/ }( n* C4 e9 n
        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.
    6 ^  `! @0 U- C7 m
    3 }0 s" i$ s" m0 b2 d2 Z2 L    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).1 k! y8 A4 a6 G6 a1 g4 ]

    ; \  ]5 P8 u5 EWhen to Use Recursion
      |) J& E4 l! ~  z6 a6 n6 W$ R+ H, @# P+ r
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    / u0 }7 J% e9 T% e" `, Z* S5 I2 J% x% _; t
        Problems with a clear base case and recursive case.
    ; ]6 I/ S; o7 w! }+ g
    % L; j% q6 T: j$ f! }5 iExample: Fibonacci Sequence) w1 y" l2 O2 ?/ `0 v1 q

    $ ?7 b+ F8 l$ P' l. XThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    + _. k* q# c" f3 o% I7 ?% @, W% ]" E2 |* f3 X' @4 f* M
        Base case: fib(0) = 0, fib(1) = 15 z/ i+ T' |6 |$ [) c& N8 `
    & E1 e1 ?3 s5 R8 G% M. N6 y
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    * Z7 |8 M2 k4 N* n4 B, m
    7 `! _  N: K) U, Z" T" o" R: Apython
    . ~4 }' H: t0 c' ~
    ) W# _1 V  q6 t$ r8 c! i) V
    7 P: s7 V" |5 f4 w$ U, N& s% Z$ p" Pdef fibonacci(n):2 o% }8 ]) m/ d
        # Base cases
    8 e( q" l% a" x% d4 g! ?: c0 b    if n == 0:* l. u% R1 M" J/ ^  S4 G
            return 0
    * q. R. A  Z/ |* q3 U' E1 ~    elif n == 1:3 V. g5 U6 W& r- i
            return 1
    6 i, o" H' B1 ]7 {/ ]    # Recursive case
    1 |1 v# n& p" H( y, [    else:
    ! ~8 _3 [& u! P* W! a1 b        return fibonacci(n - 1) + fibonacci(n - 2)1 o; K# s1 g: i  B5 f

    " d5 V) @. E2 @# Example usage
    ) E6 w2 Q6 D% x0 t- U) \print(fibonacci(6))  # Output: 8
    * s) z' @! I# ~0 M5 x
    , i: J! K) d  p+ W! R; O! w/ JTail Recursion# g' h' P# H/ u5 ^

    3 t5 w' ]2 u. g) \" N5 [( QTail 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)., r  P2 l" l3 A- M% X
    0 x7 s' S: f: g9 f, j5 h9 V
    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-7-13 14:38 , Processed in 0.064083 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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