$ e# q7 M7 N2 V2 l5 E& H递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。 L. Y; j5 D: [. K! L# q 2 u5 a% h1 f$ F/ V 关键要素 |9 ~8 c0 J6 Q9 A- N8 I, p
1. **基线条件(Base Case)** : g: G/ l$ N8 U - 递归终止的条件,防止无限循环 ! v6 e, g& r8 i - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 4 ?+ ^2 N3 k( T& B: B) n ( m4 e. r5 T) o2 L/ V7 u2. **递归条件(Recursive Case)** # L$ @% ~& t2 W! M; c' l- K, L - 将原问题分解为更小的子问题 " O, U& q8 C& H! a" i1 D - 例如:n! = n × (n-1)! . {+ M F2 R+ |1 l6 d' W- \5 p( i# Q" E* K a1 M
经典示例:计算阶乘 1 ~' p) ]2 ~$ [! P' t& t" vpython 6 F0 Y. A6 p# X# `* Q: t2 X2 hdef factorial(n): * L8 H+ J; ^+ l! Q if n == 0: # 基线条件 f/ s e3 R) K, x/ x7 F return 1: L. a* v% h4 Q; R: H1 r [
else: # 递归条件8 _ E' i6 ]0 R
return n * factorial(n-1)2 h2 s3 _3 T, @' q7 f- N0 [2 K% D
执行过程(以计算 3! 为例): 5 S4 Z$ a I) g9 G) _factorial(3)! b$ V" n+ o" `, D# ^
3 * factorial(2), p! \ n ?7 [
3 * (2 * factorial(1))! m( [2 p; P8 O) n% C& S
3 * (2 * (1 * factorial(0))) J( y! F7 ~, H7 D
3 * (2 * (1 * 1)) = 6" ]8 }; p- T8 P. T4 r/ B6 h
$ x, q; M* |$ e2 \
递归思维要点 / V9 r, ^) ]; P. Y( h2 i1. **信任递归**:假设子问题已经解决,专注当前层逻辑( n. f3 o% W: E& ^& M# S2 J. n
2. **栈结构**:每次调用都会创建新的栈帧(内存空间) ; x: [& N' p1 x3. **递推过程**:不断向下分解问题(递) : U: Q) ]; G3 ~4. **回溯过程**:组合子问题结果返回(归) 2 s6 L2 l# u) I- ?. L. c 3 Y7 B" l D: P# W! B/ E f( G 注意事项7 G# K2 K4 L4 [, g# c
必须要有终止条件0 K- \# e( b3 [9 W7 E( W; N2 J4 R, [
递归深度过大可能导致栈溢出(Python默认递归深度约1000层)0 }( G$ q1 U m
某些问题用递归更直观(如树遍历),但效率可能不如迭代: n& G2 s! k, @/ N
尾递归优化可以提升效率(但Python不支持). j( q2 S( B5 A4 K2 e7 M
$ S; w/ o0 B; A" j( |" H: t0 q- s 递归 vs 迭代 2 p- x( h: N& J2 `, }% x2 N' T+ Z5 a" a) n| | 递归 | 迭代 | $ ^1 H- t# N8 X/ V3 n' T% N) z# ~: G) M' n|----------|-----------------------------|------------------|( L! Q) ~0 L5 C u4 W+ j _
| 实现方式 | 函数自调用 | 循环结构 | % R d# A) E$ l- }| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | " i0 I% G5 Z( H. C| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 | 8 [; O+ r: F% S- v8 y$ Q| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | / r% n+ |0 ^7 G N1 L0 t+ h ! D( A, F, o( t$ e/ h/ E 经典递归应用场景 ( k w2 ]# Y/ Z+ N' O1. 文件系统遍历(目录树结构)1 _" i L) P1 H! t
2. 快速排序/归并排序算法1 J0 h) L* W2 `# _
3. 汉诺塔问题0 U3 j5 `' o$ t. E7 K0 g
4. 二叉树遍历(前序/中序/后序)) w5 r& ]6 K9 j- Q* \1 g4 z) v
5. 生成所有可能的组合(回溯算法) + z) S9 q# t8 O/ P% ?+ G: p5 U. E9 z- u * g0 q# M3 z) ]+ P试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, ' ]7 P* d% p, }0 m) I2 f4 U我推理机的核心算法应该是二叉树遍历的变种。 5 t; c4 E% i2 `9 A9 p+ S" t# g+ r另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: r, w: A/ ?* q$ X* W
Key Idea of Recursion5 {0 }7 u) r1 R
9 G- H8 z: B7 Z* Q
A recursive function solves a problem by: & R/ L& o" q$ a8 q 7 F% f* ?& k% R9 ^5 x! k/ d Breaking the problem into smaller instances of the same problem.3 J' h; S+ ]1 D$ ~
/ k$ ~9 K; K4 ~0 S! y* J Solving the smallest instance directly (base case).# Q7 N0 X0 i- S
2 @2 y% [! D9 N
Combining the results of smaller instances to solve the larger problem. 7 y V Q P" N. N" H7 k( f5 X ' u' a8 b& q: r% a5 {8 D! ?4 IComponents of a Recursive Function# ~- W4 ?2 l2 H j |( Y _. l# O
/ \+ d9 V* m9 L Base Case: $ \( A6 R r H1 K2 W; k9 Q" D: n( o, o8 n
This is the simplest, smallest instance of the problem that can be solved directly without further recursion. P9 P& T/ |' v5 |
' j; g% u& t" J2 C4 U4 n It acts as the stopping condition to prevent infinite recursion. w0 n& l9 Q9 y2 g& _: a" r 5 m# D. j: L Q! Y1 Q Example: In calculating the factorial of a number, the base case is factorial(0) = 1. # {0 |4 E! x t8 N) R) r; h. b3 _, W$ y$ E5 e F7 V/ a" a# j" {
Recursive Case:8 K! B, r$ u& s5 E! n3 a
1 o' l4 C8 }- C4 ~2 h$ v5 f
This is where the function calls itself with a smaller or simpler version of the problem.) M' l- d* B+ o9 U# l
8 G8 s. X0 N$ q
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). 3 [2 V/ {3 Q' p E0 i5 g: O 3 K9 `& U8 Z1 ^: Y3 C- SExample: Factorial Calculation 2 U' Z# ^' n/ j6 z . J( o; P: V t8 i4 e7 xThe 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:4 z" D8 U! H4 V
1 H. |7 k/ E( ?1 Y" b: V Recursive case: n! = n * (n-1)! 6 Q- h5 t. T0 H& K+ U' S: D$ ]% K. @) p2 O
Here’s how it looks in code (Python): 7 H+ o8 U5 e+ J- B* ~python( N+ h, K! B. K9 M6 T3 X
, m& @* c. e) k5 m0 s
/ C v: Q: B- U( Z: u# xdef factorial(n): # M5 ~- Y+ L: u# E5 `( x # Base case! w! s2 E8 j7 [% t) _/ _: K& F
if n == 0: 7 @7 e0 Q' s( ^! d/ s7 T) V return 1 9 {: [# f) ~: t. G3 p$ I5 e # Recursive case 6 y( Y3 ~5 }' x s else: : D0 c2 {% [3 Q7 F& S* W return n * factorial(n - 1)4 L3 s% u3 k7 a4 Y
" H3 d+ d1 X. z; I* r5 ?; {( O# Example usage8 p7 k" R& y. g( U# G( T
print(factorial(5)) # Output: 1204 S J ~/ v' t
+ ]! U5 ^$ \% [9 u3 d
How Recursion Works5 O3 S3 W/ l% B R, t z
9 V6 S9 Y* @3 s" E3 f
The function keeps calling itself with smaller inputs until it reaches the base case.5 d4 o! W* t6 q( {8 s* k n# V
. w* B4 M* A, b/ o) N6 Z6 V2 U Once the base case is reached, the function starts returning values back up the call stack.0 ~6 G* ?9 v! f, P
9 f+ B2 [3 p/ B These returned values are combined to produce the final result.+ P* k2 _% r* D. ?7 ?
6 R! ^5 V* o( }
For factorial(5): / \2 r) p' D$ j& |4 E $ x, m' u* Z' R* m5 e " B' x# {4 d G% O" Vfactorial(5) = 5 * factorial(4) , j# X9 E3 Q0 {, afactorial(4) = 4 * factorial(3) 4 `( b3 `6 X0 V; F3 c* afactorial(3) = 3 * factorial(2) + h& a* m4 Q! K0 _# \1 o: @factorial(2) = 2 * factorial(1) , G# S7 H& n" ufactorial(1) = 1 * factorial(0)7 q) k. `$ Q# G/ O
factorial(0) = 1 # Base case ' M) u7 c( G _6 H / \- ]3 G+ u8 l& @2 Z' b1 R/ |Then, the results are combined:8 |$ l/ h- F5 \3 X. K3 a1 e/ U5 N
+ g7 w$ m5 B4 g) R2 Y
7 ?& I0 M1 A- ?7 H9 p
factorial(1) = 1 * 1 = 1 8 K$ w+ Y5 ~ M, D: |- Cfactorial(2) = 2 * 1 = 20 V# v9 S0 T+ T
factorial(3) = 3 * 2 = 6 * V3 C+ j# t, ^% m* D3 hfactorial(4) = 4 * 6 = 24; f2 O: ^, I, N% S& C3 o5 A$ J
factorial(5) = 5 * 24 = 120 % a2 ?/ t A3 E/ @% H * N- y0 x! V6 Y. V% X! p) \Advantages of Recursion D+ K( Y7 ^: S7 e9 s4 Z, n* W0 k, W& D1 _4 X; d) _+ I
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).# p4 R$ K, P) a
1 g9 r, A2 m7 a/ q
Readability: Recursive code can be more readable and concise compared to iterative solutions. f. h: H/ C1 |2 U( L) ?
3 Y+ ~4 c! D9 L2 p8 Z: mDisadvantages of Recursion $ e: b( v) d+ D0 y3 }* G. r* I q4 t# n, X* C+ c! `* P
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.! F8 O) o- M6 _3 C) U( A$ N
4 N6 ?. R ~2 U! b+ h& } Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). * v4 r0 ~* s& w4 l/ X8 F9 V ! V7 K3 W- |( @When to Use Recursion 3 \. d9 G# M Y$ V / c, T% e) \+ ]' d ]5 ?- M Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).6 j- \- {& Z: B( D3 a/ P" g3 p7 P
9 E& E- a# O5 y( |1 @ Problems with a clear base case and recursive case.; I& ]9 [ T3 l- V: ]
3 J: `2 N( w- i! mExample: Fibonacci Sequence 0 u- q9 [$ ]5 R 0 K! x5 z+ C3 j2 j1 V- x$ x. QThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:" U! P/ x3 Z5 E$ \ D7 K
" M8 ?3 ~+ v0 z Base case: fib(0) = 0, fib(1) = 1- G o% ? s# M9 I; P: @7 ^
* y- P% T( r! l' M Recursive case: fib(n) = fib(n-1) + fib(n-2) 9 |+ z' x6 J. p/ d- ?0 r & I, K) `! m) P. ~( u# p7 d' Jpython2 T( E9 G# x* g! g- b: I& l: O8 m6 \
3 g) [/ a# K O4 N+ ^1 v- X
& d* V$ C* e1 V1 G
def fibonacci(n):* l; S& s8 i( Q% U2 c
# Base cases. D- n9 p$ Q9 A" H/ y: D
if n == 0:3 T# l2 w# y) y: X; Q/ D u
return 0 - _ x+ f7 U4 ^5 m6 k7 D elif n == 1:& N( S- I# F# `% I
return 11 g9 r, r4 C" S! ]) O
# Recursive case 4 V0 t! A& t# P) g: n else:8 s# _# m7 D; K" \6 W. J" N8 @
return fibonacci(n - 1) + fibonacci(n - 2)7 y' X, k7 `; Y3 r4 h7 y$ \
" j; |- Z, B3 k* y$ q6 l& s
# Example usage3 C& W/ h# z0 N
print(fibonacci(6)) # Output: 8. Q9 s' T/ N0 G
4 l1 L' e, A7 q) |Tail Recursion & t1 L& h5 z" i. ^/ ?0 K8 M! f4 b$ C
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). 6 [! R% z! P2 ]3 f( Y1 L$ \; F1 F7 \. G
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.作者: nanimarcus 时间: 2025-2-2 00:47
我还让Deepseek 给我讲讲Linux Kernel Driver 现在的开发流程,让一个老同志复习复习,快忘光了。