设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 ) z3 k( u: v# I) G7 \" J5 \- }

    . f/ R6 h+ f5 |; X7 s解释的不错- z* c/ h  i6 a# b" J

      ?1 r+ j! b3 Y, ?) k. l3 f& T递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    ) Z2 o- \8 a9 G0 D) ]
    ( m" @2 s7 r# N- V/ t2 k. l 关键要素
    5 {& P$ F( l+ `4 t, T' ^1. **基线条件(Base Case)**1 H5 Y' i3 [) N; R, r# M3 ]
       - 递归终止的条件,防止无限循环) X- D1 m2 w( _
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1! H3 O# M* u: F" u  M2 C( G* _
    ' @8 r# x% }6 Z" f' J4 E
    2. **递归条件(Recursive Case)**
    7 |4 ?8 ~: F& B& y   - 将原问题分解为更小的子问题
    ! P% _6 i+ h8 b4 k! g   - 例如:n! = n × (n-1)!
    7 [# w* ]) [: R0 y9 q( g1 V9 o4 j. E$ k9 l* C; S6 I6 o
    经典示例:计算阶乘% k- F/ @6 h# A( l4 @5 e
    python! g, s1 r4 Q; S; E) ]' P* ^
    def factorial(n):
    8 u; v) n( ?$ Q6 ^8 P    if n == 0:        # 基线条件: h8 P1 a* L* j) s3 \5 ^8 W. W
            return 13 t. R0 Z- A$ b8 S
        else:             # 递归条件" F* P6 A  f& B# L3 b
            return n * factorial(n-1)
    2 c6 u! C; o# b4 ~执行过程(以计算 3! 为例):
    0 N" m9 M! E% y- V* A7 Tfactorial(3)4 o; m6 b8 w1 P( k
    3 * factorial(2)0 ~+ {, [' P$ a
    3 * (2 * factorial(1))
    8 M5 I& h8 l2 Q6 n" n9 Y3 * (2 * (1 * factorial(0)))$ |! k2 H& O- i. u: V8 }" P! Z
    3 * (2 * (1 * 1)) = 6
    0 {/ o6 s: ~/ [( Y/ X6 X! T! r, A) F  u9 C
    递归思维要点
    $ T! |8 R' M; @2 V7 c, X" e1. **信任递归**:假设子问题已经解决,专注当前层逻辑7 f" T  F1 v- n0 |
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    " b# F- ^9 M$ r2 c& a( t3. **递推过程**:不断向下分解问题(递)+ f; ]% a; n' Z/ H
    4. **回溯过程**:组合子问题结果返回(归)1 A9 E' m: y& _% h) C' j

    ' r& u" [% V& O0 J 注意事项
    6 f$ T  t* D! e6 |) M必须要有终止条件
    " A* L3 d1 i, T3 `: `' b+ z递归深度过大可能导致栈溢出(Python默认递归深度约1000层)3 P; i) i: S, q& c  u
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    . _0 u2 ~, N. _/ m0 H尾递归优化可以提升效率(但Python不支持)0 {( H( Q- `3 h& g% V

    " c" H2 K9 }$ ^8 U# g3 R5 v- R( h 递归 vs 迭代# W. P: o' x) J+ Z
    |          | 递归                          | 迭代               |
    $ X/ @0 W( a; n9 s|----------|-----------------------------|------------------|: ?" _2 V9 T2 g8 G6 g
    | 实现方式    | 函数自调用                        | 循环结构            |
    + x; O# J: a! D5 R| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |/ |  }' D+ l6 S) O& U
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |3 p6 n& E/ c( @) {6 U
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    - W, K# r+ a$ V) A
    # F/ R5 @4 W: i$ O2 ]6 l7 O5 q 经典递归应用场景
    / |1 l9 ?7 a2 y' z1. 文件系统遍历(目录树结构)+ A$ _8 o: K5 e% R
    2. 快速排序/归并排序算法
    ( }3 |  E; ~  |# ^. N4 F6 z' J3. 汉诺塔问题3 R# E, J5 t0 }, F0 a" |, ?7 L
    4. 二叉树遍历(前序/中序/后序)
    ' }, H" v( o4 m) `6 N5. 生成所有可能的组合(回溯算法)
    * V7 h+ i. f' f: B6 r1 `& p- N: i( V6 U* q  s! Z
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    昨天 07:10
  • 签到天数: 3153 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    5 N- P7 ]) D4 c我推理机的核心算法应该是二叉树遍历的变种。
    7 |  l" ~( c7 M" t# K7 D" @另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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! c# M# J/ Z- }: \6 n% ZKey Idea of Recursion
    4 v/ I+ {; `2 M1 h/ C6 p/ c. p$ v5 w3 r* _% ^+ h
    A recursive function solves a problem by:2 M/ e8 t2 V0 y0 i2 |* w
    ; k! e3 T) H) i+ k  @7 v2 K
        Breaking the problem into smaller instances of the same problem.
    % b. W3 `0 O5 l7 K7 H
    ) m0 z0 H8 i& h3 @# L5 t    Solving the smallest instance directly (base case).
    ) O1 F* X  ^  S6 J4 t5 P. H# q' R9 s6 E
        Combining the results of smaller instances to solve the larger problem.
    ( ]! a3 ^+ M- ~& j  l5 q! J+ x* n) v, o" C
    Components of a Recursive Function
    . E- a( m4 ?5 O; D# a  y- i7 T0 y
        Base Case:5 F) K* |7 ?5 h/ k) c" \, ^; j+ D

    6 E* n8 e$ u( h3 h0 k# f: S        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    6 ~- ?8 C- J6 L/ d: }4 I  U$ M) l% B& b' ~, Q
            It acts as the stopping condition to prevent infinite recursion.
    " G8 o  n9 h4 d1 p2 ]- G& H, ~9 A9 q. X
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    * N+ ?4 w$ F+ Z! [1 {( d' n/ \3 f0 A, I* o/ \
        Recursive Case:
    ; a% T$ {$ ]" X5 d9 N! ~' v* F2 q: M& l- R4 S9 k
            This is where the function calls itself with a smaller or simpler version of the problem.
    * ~4 o3 b" r# \0 U. i- ], s0 A. p( s5 M, u8 F0 c
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).8 P  I  A7 X& D; g6 M

      ^, Z* u) k# T9 c" C3 k8 k& [Example: Factorial Calculation
    $ o# d% P; B% ^$ x3 k# s3 J& h  j- v+ y+ ]
    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:9 u- c- t$ D2 @5 Z2 }) |0 s! c

    ' [' V1 X3 s& R( h; b* R    Base case: 0! = 1/ k( ?. s3 p9 d4 R
    9 c! D$ t* O8 Z% g
        Recursive case: n! = n * (n-1)!
    ; H& ]- F1 i0 B& t6 A9 p$ j
    3 a& @8 @* V( p& O: mHere’s how it looks in code (Python):
    4 @+ s: v  e3 S8 p; Rpython0 c( P- N. ]9 L9 v7 s8 t
    , g$ M; F4 n' [) Q5 g; L: E& ?; }
    ! s# u& y. s- g( Z" r% P
    def factorial(n):
    3 l! v0 `2 t( W+ z! i" A    # Base case" m  V9 b- j) X& m# |) O
        if n == 0:
    8 |; Q3 Y4 G1 ], H) U/ w8 w        return 1) ^& t) S  {  C% O+ u
        # Recursive case6 Y6 [- X' \) j+ |
        else:! K4 Y, _! F4 d8 L; q, ?/ o
            return n * factorial(n - 1)( q  ~$ L8 U2 r. j& k# j7 X( u
    5 l( N/ D6 W/ {/ ^
    # Example usage- I+ m5 _5 C( Z, [8 Z
    print(factorial(5))  # Output: 120" Q* j  ~' ?" K3 H% w
    8 x' B. D4 m0 p
    How Recursion Works- H) g: ~) [) p% j8 D* l; f& V

    . B* b- R- B* d# Y, s) r    The function keeps calling itself with smaller inputs until it reaches the base case.5 B. ]: m* {: V: U9 k% `# y! i

    3 U9 @1 F0 }7 ~( d; y    Once the base case is reached, the function starts returning values back up the call stack.! b1 J* z% }9 b

    # P, ^: J, y# `8 V+ r5 S    These returned values are combined to produce the final result.
    - @* k% a& X  J) A$ b( g+ R* T# X1 d& N; r# ]: D7 P: [5 q
    For factorial(5):+ E! n7 t' \8 [# o- a, f

    8 w5 M8 Z/ s! C- W' P# X6 H4 m  x2 v- Z3 j
    factorial(5) = 5 * factorial(4)
    : Z1 z4 Q& H/ c, a0 ~. Kfactorial(4) = 4 * factorial(3)" ~5 d# Q( j0 {1 |
    factorial(3) = 3 * factorial(2)
    # H* R! J, X' K8 ^factorial(2) = 2 * factorial(1)2 t5 j' _* q8 T& z! j
    factorial(1) = 1 * factorial(0)# P; O2 I9 p, m  H  F
    factorial(0) = 1  # Base case1 i! |* h& l! v0 ?3 R7 k! ]

    / Y2 G0 Q9 H. x8 p3 X, {Then, the results are combined:
    $ `7 [. T, C# U# Z% C  k  ]. k) _' s$ d- q1 |, a

    2 @4 l+ S, ]$ D8 {& Bfactorial(1) = 1 * 1 = 1
    $ j2 C# {, t$ x+ ^factorial(2) = 2 * 1 = 20 S! N! K# S  Y& y. h2 E* m2 m
    factorial(3) = 3 * 2 = 65 j+ c+ _  X8 q" R- [4 p
    factorial(4) = 4 * 6 = 24
    & B. V( D' h& |* p6 h: S) u/ Sfactorial(5) = 5 * 24 = 120  z+ G4 R+ F* V# {

    , ~; h# Z) R; @3 {  W; h# }Advantages of Recursion; D" X  S9 b  l5 e

    3 A0 t) E/ f2 B$ W, u    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).0 y) c5 c5 V% t% k% n

    - ?. I+ [$ R- u+ h    Readability: Recursive code can be more readable and concise compared to iterative solutions.7 V2 ]: \1 s+ U. ?7 M: s  y

    1 l( Z: C* ^( C0 Z- u3 D0 PDisadvantages of Recursion% i/ G9 |5 l! {  L# F
    & i' n) e( _: H, J
        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.: Q4 ~# ^; b: E3 Y' ]
    ; e* X, D" L1 h, K/ h( {/ [0 y) z& V
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).# b2 A) O  y  S) i5 x
    ! f3 `; ^5 V6 K8 z. E8 D! X
    When to Use Recursion/ O4 D. @( m, A: O0 Z
    ! c$ O1 j- V: b8 R& v! d. L
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    9 d9 _. V& x, m1 a+ }- p* X: Z& G) `% s9 L9 Q
        Problems with a clear base case and recursive case.' e0 z5 h- i" Q0 |3 F

    * ]7 _9 ~3 t" U; C& z  U) I( i0 aExample: Fibonacci Sequence8 y' }( G  @) i7 n& u7 m" [; k7 Y

    ; I1 ?" D. h: Z) PThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:) ?& J5 T  T* o2 {% w
    1 J) w6 h& u" U& p5 U/ C- y
        Base case: fib(0) = 0, fib(1) = 1
    , X5 c' O- t1 ?$ B& z9 F
      J4 ]& ]4 F5 @& A    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    & o& b8 i9 k' d, `2 j
    ' c9 a4 R  @( u4 B3 e" gpython
    0 o' C2 l6 J3 d" P! N) X, Y2 }- `9 C7 G4 p! p" X. z/ P

    % Y5 a3 B6 p5 j$ O- Zdef fibonacci(n):
    ; L* A7 o+ G' O% [, H# |  S" j    # Base cases
    ! `4 W& g0 a5 o  @6 b6 w    if n == 0:
    + {$ r: n7 N. l+ c7 t        return 0
    0 u% A" {2 \- {; T3 W    elif n == 1:
    ( y6 ]* ~6 v$ R! x" s4 w. B1 p        return 1
    ! y1 `  |2 p. d! H5 I( g. u    # Recursive case9 u& K( d) J6 U8 b$ u
        else:
    3 `! S7 E- ?1 S        return fibonacci(n - 1) + fibonacci(n - 2); y9 }1 s% q& J- o+ J
    3 o- c% z" x& i: q) j
    # Example usage9 i  q( [* U- @8 r( m- C
    print(fibonacci(6))  # Output: 8
    1 E5 _0 E. s! l4 T$ l2 N( v8 }
    # H" O3 s# O2 r% _+ m- ?) s! K* Z( ETail Recursion
    % o$ F8 H" L$ w( k& f. r
    " ]' J; j* m; B( D- ^. ^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).
    $ P; H  n& {2 y! ]  \
    8 i% Y. P( f3 h; ~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-1-25 01:41 , Processed in 0.058421 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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