0 e. _6 K+ T) L7 g9 \3 B递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。' _+ _3 ^; ~- C: N9 l( _) c5 A. e
# D6 Q4 k( a! Q6 i2 n; `8 J# T
关键要素 . n9 _9 |/ g+ W5 {+ _2 j- s1. **基线条件(Base Case)** & H) A7 q, P" |6 O! }/ } - 递归终止的条件,防止无限循环9 `0 X/ G* @" c9 g' s+ W4 F
- 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 & i9 l$ p% }6 M$ ] b4 B, {4 `! @: M! K! L' z+ u# X2. **递归条件(Recursive Case)** , G) V8 @- ~" G - 将原问题分解为更小的子问题 |" g& P+ [8 }* j% f/ k4 K - 例如:n! = n × (n-1)!& ]0 R- r8 a* F, ~" u
# o z, Z; l: d* S- y0 j8 _! k 经典示例:计算阶乘, d+ f' U' i$ u9 T
python " E& D+ v1 {( g. R" f) }( U' Ydef factorial(n):5 W0 \6 g3 o! u" A P
if n == 0: # 基线条件/ o& W9 L8 f+ n
return 1' O. i, d! S t" @
else: # 递归条件 4 d% V" G/ J' ^& V. R2 g0 J( A return n * factorial(n-1)0 z9 l2 k2 M% O* @ [5 j- b: p
执行过程(以计算 3! 为例): 7 j! X0 l: y" p2 g2 u# |7 L, nfactorial(3) , h+ E$ Z# F$ a3 R: Z2 A7 o3 * factorial(2) 4 W( T7 k' M# w# S8 a- M8 \ C3 * (2 * factorial(1)), I K; B) [& O6 J* m3 t
3 * (2 * (1 * factorial(0))) # ]; {! U, |1 i( t- l7 s1 F3 * (2 * (1 * 1)) = 67 q' b4 R7 f' B# A/ b: |
* b, z+ z% _1 P+ S4 `$ u/ T. }
递归思维要点 - l2 D6 @4 i1 N! L! Q( B1. **信任递归**:假设子问题已经解决,专注当前层逻辑 0 m N k s/ h" v2 Q2. **栈结构**:每次调用都会创建新的栈帧(内存空间) " z: m7 }' T5 U- g1 U; d% Z% A, ^" J3. **递推过程**:不断向下分解问题(递)1 W$ W n/ d* c9 I4 _9 W1 S* f b0 w
4. **回溯过程**:组合子问题结果返回(归)( r6 [) P, M5 a! j8 D1 |
0 G h+ }. x2 o0 V8 B
注意事项& f `! N8 O$ J$ c3 m2 j
必须要有终止条件4 y$ ~$ `* R% z9 \& Y8 N
递归深度过大可能导致栈溢出(Python默认递归深度约1000层)3 k1 J( {$ A7 _/ ^/ R, N: J0 @
某些问题用递归更直观(如树遍历),但效率可能不如迭代 ; R9 {: T* }. T; S* `" @尾递归优化可以提升效率(但Python不支持) & y x& ?3 ?6 ^3 p( n- ]% ~# d( H ! q9 M5 l* ]; U) V2 ]) s 递归 vs 迭代 4 l$ C! x2 m, |# `, G| | 递归 | 迭代 | $ |2 j6 G+ t: x|----------|-----------------------------|------------------|1 \7 I" A, A% w, R) E
| 实现方式 | 函数自调用 | 循环结构 |( t' C1 a# B" T2 t h1 `
| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | + g* G. Z E2 u X3 W- v) H8 ?| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 | & t- |7 Z3 b6 V3 Z( \$ U' C# R| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | ! L' P; E& u. q2 Y! s' t# d" @" w! o* a, f0 g
经典递归应用场景 & Q4 E1 k7 L" ?" n# D6 T& P; k1. 文件系统遍历(目录树结构). ^. R- k8 Q1 l; h2 H+ L) _* j
2. 快速排序/归并排序算法. O' d3 O; S/ @- d
3. 汉诺塔问题2 R* u+ }" d& \6 B3 ]/ R6 a* W
4. 二叉树遍历(前序/中序/后序) / i3 q& k4 ?8 d. R* n! ~5. 生成所有可能的组合(回溯算法)# U! [8 _5 y" M2 z# Q% e
- _5 e0 c4 k9 [7 O+ a! v试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, : H: j" Q; f' s2 v! ^3 ^我推理机的核心算法应该是二叉树遍历的变种。 4 T8 b$ V! W4 P6 c/ |9 S另外知识系统的推理机搜索深度(递归深度)并不长,没有超过10层的,如果输入变量多的话,搜索宽度很大,但对那时的286-386DOS系统,计算压力也不算大。作者: nanimarcus 时间: 2025-2-2 00:45
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:, g: { S! x$ K
Key Idea of Recursion # b/ c) q3 ?3 o$ z- ^' ^' |* |, Z+ o$ M9 Q. Q$ A! B
A recursive function solves a problem by:% v6 C6 b" ]) w. f' c" y5 x" f
2 t3 ~' P* P% n0 T
Breaking the problem into smaller instances of the same problem.; @" l1 T, e" l# \6 \' l1 |
# d1 h: ^4 j, J* }2 u6 {' s
Solving the smallest instance directly (base case). 4 _8 a6 C# J& J$ {0 U! v0 T$ i/ l5 P7 u }) X+ @6 A) G6 p
Combining the results of smaller instances to solve the larger problem.# r0 [' m3 `0 s5 A( D6 R
- Q9 h* N( A T2 G) f
Components of a Recursive Function * q$ f% A5 d G! U/ A% [! N7 r; ^ 3 V% e; x9 w/ v& n6 @+ j- n Base Case: 1 u, R& X- V1 |; U% z / O- N. o) _: x" Z! k1 D1 [ This is the simplest, smallest instance of the problem that can be solved directly without further recursion. / o) J8 g% x+ u2 I9 @1 @9 P# F: p( d: o- c
It acts as the stopping condition to prevent infinite recursion. / q$ y7 d1 L: g" A3 X1 T1 B& u1 n7 u' i0 |8 o
Example: In calculating the factorial of a number, the base case is factorial(0) = 1. 1 u- \0 N) n$ w% B: A8 z7 z3 E- P" Z( A" Y6 M- s/ j
Recursive Case:" @9 Y1 l3 j1 j
% g- X6 h2 V/ e/ D1 ^4 Y
This is where the function calls itself with a smaller or simpler version of the problem. 7 `# W. t7 V R" s* @2 R, I8 x1 f# b( j Q V% V( l
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).$ r$ k' O4 L# }2 L# r' O- a
" p* ~7 z" k+ {0 C% AExample: Factorial Calculation ( B+ g$ c3 m$ C7 e2 }: D% X# J5 }. I2 {0 }
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:( t( n. t% ~0 G# B9 z1 Z3 M
" m) i* i. N4 `2 [ Base case: 0! = 18 ~0 O/ A# n5 I8 T* o! `1 T0 P
0 W+ z* c% d! r9 z
Recursive case: n! = n * (n-1)!1 |6 y) v" ]" [$ ]" a6 a+ ~ U8 L
3 b4 Q3 Y* _( o x3 r5 oHere’s how it looks in code (Python):1 \" W6 b4 a I. e$ |
python) _2 p& K# m* v
$ S2 ?" f0 G1 a6 P: `5 f
3 d) v: O1 H% J- L/ udef factorial(n):9 G) f, x* B! y5 J
# Base case ; f' P1 W$ F- d if n == 0:" ~! p5 J* Y7 S
return 1! K+ k) R% f% g. Y1 X% k8 T3 ]- d
# Recursive case5 m l- h4 [0 \5 J7 X' ~
else: 1 A8 U8 m% e; j" w( W return n * factorial(n - 1) - d4 b; D3 T0 Y0 d * }: j( z* L4 R% a o# Example usage 9 O% Q4 ~" t6 E! L; I- rprint(factorial(5)) # Output: 120 7 Q9 s6 b0 Z4 S x4 D- x0 L' V b' Z& C V9 B P/ K; ]; c: MHow Recursion Works" }7 [) M' X! J
* Q. [# i- P* @6 R" L The function keeps calling itself with smaller inputs until it reaches the base case. ( p' w2 ^& L; k8 S1 A% [" K1 I n6 V8 K+ ~3 N7 i; A# A, Q
Once the base case is reached, the function starts returning values back up the call stack.) o% f: M* M$ N' @" h/ w
, L! E- H6 m7 C
These returned values are combined to produce the final result. ' Y' m' ]) O7 G9 @" U- \$ M4 v! Q( a( B; H
For factorial(5): ! K4 g) z2 M! g4 r5 R, v4 Z; ~- L ?- ], A4 z2 `6 f
! O9 y! N" @) s4 B7 `1 ^/ bfactorial(5) = 5 * factorial(4) * ^/ A% E. m0 l) W3 P; }. R' gfactorial(4) = 4 * factorial(3) 0 K* A, G$ u( Vfactorial(3) = 3 * factorial(2)5 u. P6 n9 W* m0 }) b9 Z
factorial(2) = 2 * factorial(1) 7 L/ U2 K# C, m$ w u% X& I- pfactorial(1) = 1 * factorial(0)- j& c& E B5 W" Q: V" V
factorial(0) = 1 # Base case" f" l0 u1 r( H
& y( `* u( K6 X/ c5 i/ h2 Q
Then, the results are combined: - C* S' h2 \' J1 x$ n: ]8 L1 i. l) t" v; w/ `: U' P3 [ {
6 C% b9 s, E- PAdvantages of Recursion . I. ?8 w8 b$ A" [5 F' F: s& Q* r3 e7 i/ r d- e- q" h6 T/ `3 _8 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). & O, g. B: i p- \& w; D, m7 y $ s* {9 r# j- c0 M, A* L! u% ] Readability: Recursive code can be more readable and concise compared to iterative solutions.* V) ?% _( h: Y9 u) S; V
$ w- {9 X" a+ t5 p% gDisadvantages of Recursion3 I: V" H) X# ~; ^ _3 C1 F2 H
3 L6 y; ]7 }% s 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. * [1 U$ y" N \9 F5 ]* q" I2 M Y$ R" A, v( I0 m% q# k1 i" x4 W1 _
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization)./ l; X- f& W9 W' b
# O, g3 x: z0 d$ ~+ P8 D6 v! t
When to Use Recursion7 x) Q, M7 y# v1 C% V
% k1 N) s0 h9 u
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). , p5 Z) D/ f' _9 q4 [4 T2 R2 P% M; P/ m I0 b
Problems with a clear base case and recursive case. : m0 y* U- _% w8 d; G. ^) J5 u& x/ N4 n& G$ p# a6 k5 l
Example: Fibonacci Sequence( |1 Y. O* r2 D2 e( Q8 S
: `$ o7 N$ [9 |
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: 4 C. {! R; z. e+ C' x3 Q" r7 ]1 e' p9 I
Base case: fib(0) = 0, fib(1) = 1 3 I v; z( O/ l2 Z; M Q% s* m! e4 E: k" v
Recursive case: fib(n) = fib(n-1) + fib(n-2) 8 w# T, W- f$ m, b$ v 3 S3 @) n0 I3 ?3 u; V' x7 u, Ypython # i3 J5 [) m6 [ T7 ~; y9 J5 Y$ U* k. Y+ V
# p' D1 b4 Q: S: V. Udef fibonacci(n):5 C d4 Z( @: `. K3 ]3 G
# Base cases4 U, r) n( C& f) S2 E- U& W
if n == 0: 6 \2 v5 P. e1 ?( m2 [: s return 0/ y6 o5 F/ N! o& O- v" P
elif n == 1:# k V+ F% s& V5 s
return 1 6 u5 R e9 ?6 \/ L4 y: e) S3 C # Recursive case& j4 S0 ~9 {. S% W# S) F
else: ' i- l& U" Q$ y/ L r$ t return fibonacci(n - 1) + fibonacci(n - 2) 4 O3 v) N" Y0 Y- K0 ] H- ~$ X- l; o9 S9 F
# Example usage, ^- Z( }" B% v( o- S6 ]8 i
print(fibonacci(6)) # Output: 8/ i/ V9 E* `0 A0 E, s
- o( `2 X. x ^
Tail Recursion* G& l9 M: ?0 R v* z/ X
5 n, E) D4 x# ^. u
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). # L$ y2 G, ]' n3 Y3 j. P0 F $ {8 ~7 G, \& f# K ~+ vIn 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.作者: nanimarcus 时间: 2025-2-2 00:47
我还让Deepseek 给我讲讲Linux Kernel Driver 现在的开发流程,让一个老同志复习复习,快忘光了。