设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    5 A) S8 B/ A* T4 U; i8 k. R" ^. t. Y
    解释的不错8 ~* n" C6 y6 E. L* p
      M* R8 d1 H  ~+ b( P- h- i
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ' L2 R0 f: U* k/ S* J
    5 I  Y3 T$ k1 V% S" ^* G 关键要素
    3 t, M* j. n, R6 B1. **基线条件(Base Case)**
    ; S) H- f4 p9 ?3 F" v/ H   - 递归终止的条件,防止无限循环
    % M* @, A" m& P% J9 M   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 11 I& y8 Q; L" W" V$ e: ^# [: W/ e

    6 |0 A, z* o4 N2. **递归条件(Recursive Case)**
    4 a: T% x2 s; {8 E: C3 m   - 将原问题分解为更小的子问题
    % M/ \+ {& ?8 X1 F/ t7 ?   - 例如:n! = n × (n-1)!
    # T6 |" V5 a9 ]3 L$ _
    ) N! u5 l) k% \' ^1 _ 经典示例:计算阶乘' D/ H: F5 r! f  C  u
    python
    5 n+ \# K8 M4 N, Kdef factorial(n):
    : C2 v& M. j2 f( b    if n == 0:        # 基线条件
    + ~7 n& w8 F  N4 h# S" G# `        return 1
    2 |5 O/ ^- q  n, |    else:             # 递归条件+ z, H6 _7 e" s' E$ b9 l, d* s0 f
            return n * factorial(n-1)
    5 ?$ D) x0 F2 m1 Y& V; C  }执行过程(以计算 3! 为例):; L5 j8 o, b3 v3 ~8 A8 J
    factorial(3)
    # M# q1 x# c8 P+ q( J* A6 p4 _3 * factorial(2)
    7 c# X9 Z$ v' b5 w3 * (2 * factorial(1))
    ) b) w; O) k. Q1 q3 * (2 * (1 * factorial(0)))3 ~3 i; s0 F* |
    3 * (2 * (1 * 1)) = 6
    * M- b' p! a* C! d( S
    " T0 O& E& i8 r0 `+ |4 { 递归思维要点
    + g3 b. _. a6 x3 u4 y1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ( r& Y- R& @! T: a2. **栈结构**:每次调用都会创建新的栈帧(内存空间); l. O2 e0 L2 [2 P" f
    3. **递推过程**:不断向下分解问题(递)2 B1 G4 @: c" N& O* k% @
    4. **回溯过程**:组合子问题结果返回(归)
    ( R/ o* T6 W# b5 P* u6 c" R5 Q, R' P
    注意事项% c3 z# X8 q' q8 |
    必须要有终止条件2 e  C0 T* L0 }5 S% K2 X" d
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    ! l: [6 o# l6 u# x& R- i某些问题用递归更直观(如树遍历),但效率可能不如迭代1 X, i- j/ D7 A9 }' V/ J
    尾递归优化可以提升效率(但Python不支持)
    5 X! e) I& C* B3 n; j, g$ s$ S# |* \  ]! u) `; c2 p- U
    递归 vs 迭代* T& |& Y& [0 F7 H
    |          | 递归                          | 迭代               |
    % f* V, K  P3 m|----------|-----------------------------|------------------|% Y% T* E1 A0 Z- x( n
    | 实现方式    | 函数自调用                        | 循环结构            |0 W$ T& x9 N; l; F
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ) r  x  D; O3 f6 z| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |5 O9 U2 I3 B; c5 V5 I9 Z" U- c
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    / u8 d% X+ f0 T/ L+ ?! P' ~6 ^# u1 N5 p( `+ S
    经典递归应用场景
    2 f. \- h- r) {* L* L5 J1. 文件系统遍历(目录树结构)/ r. ~" m) S" @# N0 e
    2. 快速排序/归并排序算法% @) v: i) A& c8 s
    3. 汉诺塔问题, a% B0 m$ j$ W2 a! o  \4 b
    4. 二叉树遍历(前序/中序/后序)$ a6 [' N: K% E2 ?
    5. 生成所有可能的组合(回溯算法)
    9 l: i2 F' b' E. a" s
    , P( k" G1 O  M2 q9 z# `8 S3 z试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    昨天 22:40
  • 签到天数: 3176 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,+ D- L# \! l% x" R/ Q+ b. P
    我推理机的核心算法应该是二叉树遍历的变种。
    0 u; T& |. U/ ?" n1 R8 I& T另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:2 j3 G" L) d" z: @
    Key Idea of Recursion
    ! }0 J+ }: c9 F% L
    ' I7 z( b5 n% V0 u7 |5 n6 `A recursive function solves a problem by:6 I4 l" D$ O  d$ C0 R

    . A1 h" c+ R1 q7 ?2 {    Breaking the problem into smaller instances of the same problem.
    * S- g+ R# e2 o+ K3 E. D( x. \1 q5 A; M& |. k% B) t( m5 t
        Solving the smallest instance directly (base case).
    / e9 w$ f+ J. G2 p
    $ B/ f$ i- j3 U    Combining the results of smaller instances to solve the larger problem., d% z9 y2 o1 F" A, J* _0 L
    ) P: S. p- S) u9 O; h9 c0 u
    Components of a Recursive Function
    # I' j: y( Y# J5 q. k9 W: M5 G  E2 v: I$ Q* S7 s
        Base Case:" z0 g7 H6 M5 L, M  U+ [, m
    # T4 T, P9 }* G
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    + |; J3 ?% y- G; m5 t" T; [( ^4 T5 v6 Q4 Q6 ~. {6 a
            It acts as the stopping condition to prevent infinite recursion.  ^( I- d8 i0 V% k" Z( Y2 G6 x
    ! E4 c/ \' ]: @1 P. j5 t" e
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.2 j+ n2 w# w$ n1 C9 Z  f
    : ~! m- m  [) O; E5 W
        Recursive Case:0 q* @4 h- y1 m$ K: E
    " @2 Q) l7 j; |8 x' Q: P! M
            This is where the function calls itself with a smaller or simpler version of the problem.
    1 V+ G+ |/ _' V4 @# \8 b+ g; d
    " i4 E$ m# l& b9 \  z0 a7 J        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    ' ?+ z% m7 \2 a) [! \5 H$ ]' r/ H) p* p) i+ ?8 y
    Example: Factorial Calculation$ h4 h" `( y! k+ Z- @9 X

    5 l; q1 @8 o3 o2 O5 ~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:
    / v- u# }$ L- Y: R3 T+ G9 L3 J) {; C% j% w  W
        Base case: 0! = 1# {' C; I; v, l7 ]

    $ p( Y8 ^" H* a# T) D1 j    Recursive case: n! = n * (n-1)!( a) Z4 R% b; e: ?' N9 E# h
    0 ^) U0 z' ]1 f1 A5 W, J- ?7 w
    Here’s how it looks in code (Python):  G' p% K! Y: o( y9 Z
    python+ S0 [- p2 v  W+ M& o# o3 M
    0 z/ X: E. `3 }; G8 P' X

    ( P0 k- v2 @3 b) D- }- Idef factorial(n):
    ) S$ E+ R+ a: {# n3 K1 m0 ~, _    # Base case& h9 ~7 q- F. Q2 s* {4 U
        if n == 0:
    4 [2 Y6 K6 X; T- {5 J        return 1
    6 [- J; h; x0 @, |7 ~) N    # Recursive case
    6 N6 T8 c- A$ O2 [/ X/ U4 m- f    else:2 _- [3 O3 l5 v  P
            return n * factorial(n - 1)
    * ?, g% s4 {; l/ ~8 U8 z  {) r" d/ F: q2 p/ Q" `8 p3 L
    # Example usage
    4 f) R4 V6 @. n' ]4 Jprint(factorial(5))  # Output: 120+ y: o( A" ?: C8 n# z

    # Z- t- F+ I, k7 y6 ~0 o9 LHow Recursion Works
    . }. M0 H' ^6 q' I' `+ F0 B
    2 l& Z. f2 j$ u4 l" x    The function keeps calling itself with smaller inputs until it reaches the base case.+ l# B* \" r" A% x# d  \8 `

    + @3 R5 c: ?8 X- d: W    Once the base case is reached, the function starts returning values back up the call stack.
    3 F: e/ A+ V# V2 W1 a( O# `% M
    7 z& r* ^: S3 `& P5 y$ G    These returned values are combined to produce the final result.
    / v' r* h4 W( u! a5 v& a. P$ g" t: L) N9 u. `& n
    For factorial(5):3 Z, g7 {1 ~- o/ O% V. [( M

    3 B2 L* g# j! D8 b% c6 u2 y9 `; y$ R7 x  w7 [1 w. h( C/ H
    factorial(5) = 5 * factorial(4)
    9 C% |$ q$ E" D2 {% @9 ~. Zfactorial(4) = 4 * factorial(3)
    ) r6 Q8 Q5 |% k6 j# ]! I/ Kfactorial(3) = 3 * factorial(2)
    6 i/ x8 N1 ]. r" c! bfactorial(2) = 2 * factorial(1)4 g& x7 Q4 \3 g0 R: M3 v
    factorial(1) = 1 * factorial(0)
    7 k" z. V7 e' T6 o0 s" Xfactorial(0) = 1  # Base case
    * f9 j8 g2 U; b  l, ^" d, t+ x
    & j) e" A: ^9 }( L' F% o0 kThen, the results are combined:+ h' J8 J' R6 Q& q

    . I- o, V$ o9 \+ `; p: j% d
    9 A; y+ ?, d8 [% Y2 ?factorial(1) = 1 * 1 = 1' R" e8 s; G8 q  W
    factorial(2) = 2 * 1 = 2
    - c5 O2 [( J" h1 R- z& Q5 ]factorial(3) = 3 * 2 = 6
    / Z' I* l& w0 G1 V  D% k% cfactorial(4) = 4 * 6 = 24
    1 D" I/ U4 L, M2 `1 o2 I# afactorial(5) = 5 * 24 = 1204 {" M7 j3 r+ X( J) B0 _( {
    , F6 a* c5 T5 A( O! w% J
    Advantages of Recursion  X' [8 b( l' T( R3 ]
    ) {4 b* p' a: s( J9 `* |
        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 f5 P$ x& [* T
    ; G% k& F# }& P8 F4 F
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    6 D8 @/ a* @1 x0 {0 K$ [" |' A' {  s9 S$ I' H  _
    Disadvantages of Recursion! e5 p* [$ |, ^+ n7 e  S
    ) ^. X) L: t* y+ N! O, I
        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.* l& V5 M0 M) x
    " r: e9 N6 g0 A. \/ c
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).# v' S) e0 T/ }6 o: Q
    , `! u+ s3 T6 M8 A; ]
    When to Use Recursion
    " d& t1 [& `& Q& s: g) K1 u7 o+ V
    " s; E3 x0 j' U4 q    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).2 o1 A# W8 J4 u9 M  O+ F. d2 j
    4 ~2 G# d7 e% F8 ?2 k
        Problems with a clear base case and recursive case.
    9 z2 x; B+ C9 @, \4 r4 }5 o* S" b: f$ A
    Example: Fibonacci Sequence: g6 Z4 I3 u2 x; j- c- l9 K

    4 C, R% y8 }, u7 D7 h1 C7 DThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    ' `1 I, |; @9 M
    9 A2 f( v: g+ a0 ^9 Q" x    Base case: fib(0) = 0, fib(1) = 13 t$ S2 c( _- S% ^% I

    * d; B0 `. D) v8 N" J. \    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    1 D/ N6 X+ @- R- u5 z- H9 s* o/ J  T8 b
    0 @9 j9 @; i2 z6 X: ]0 Npython: d( w( l- x1 ]) A+ q

    $ o4 o# {7 {3 D3 o0 D% L" A! U, n
    ; ]# s, w3 t, a+ T2 s9 Vdef fibonacci(n):; r+ Y; A7 V1 r/ X0 N/ k
        # Base cases
    7 n/ j: `5 u1 j3 w/ H* Y: r* B5 k) O8 U    if n == 0:3 S5 b2 D( d# y4 x: z' @
            return 0. d1 o, x2 Z+ P2 ^; a1 Y) E
        elif n == 1:6 u. o/ h7 K( v) O$ l, I
            return 1! a3 q4 G+ E# F2 s
        # Recursive case% C) g* [  A( r! w# P' w5 v, ~
        else:/ }0 J& t& j2 }, O+ K
            return fibonacci(n - 1) + fibonacci(n - 2)
    " A+ a, d. f; ^1 h6 N- _2 F7 m, U# G5 T5 _) R- u' v
    # Example usage0 v; y( |7 C6 r
    print(fibonacci(6))  # Output: 8
    # z6 t' C' g& r& ]  H6 w5 z& i
    5 i5 S$ C9 w! j0 H9 ?& BTail Recursion
    6 V1 O) l( `  u7 T8 P7 q& C
    + ~1 k% b8 v1 {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).
    ) s  ]5 x8 b) Y/ c
    - K6 q6 `3 i( NIn 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-2-18 12:23 , Processed in 0.055552 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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