) {$ V" O8 i. k8 z 关键要素6 T3 }& {8 K5 u3 A8 v; H
1. **基线条件(Base Case)**0 [: v0 U, Y& @" \4 Y0 i* ]6 d
- 递归终止的条件,防止无限循环; g) D" d/ a# V' ?$ S: D' |( n5 N7 {
- 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 4 G Q* O; m6 `: U. G! c9 N. Z5 ] / |' J5 R9 x$ h" z2. **递归条件(Recursive Case)**; J, S; `4 ]+ a0 y* p Z
- 将原问题分解为更小的子问题. r8 n% z5 s4 J( \
- 例如:n! = n × (n-1)!, l( f' Q9 c; ], ~( u, t9 K" J
4 |% Z9 S. W" T, i( w2 F
经典示例:计算阶乘; m a0 w/ F8 C" Z) s
python y. T9 O9 F: i9 {4 J( ~
def factorial(n):) Z5 |& m$ n. U% B o: b
if n == 0: # 基线条件8 i' C( y' L4 \( Q
return 1 \. z/ y4 y- `% L7 p else: # 递归条件 0 ]0 Q% D; e1 S9 q8 m& F2 e0 [ return n * factorial(n-1) ) h, s( Z- j" x2 k执行过程(以计算 3! 为例):- L6 A) S' [: r
factorial(3) 5 H+ s/ U* v$ N2 B3 h4 ~3 O! l3 * factorial(2) H% W$ ?0 J" G3 N( e3 * (2 * factorial(1))4 z5 x8 A" A8 g6 C$ Y" o
3 * (2 * (1 * factorial(0))) 5 n: g3 h! H3 V) e( L3 * (2 * (1 * 1)) = 6 9 c" N# {4 i1 u2 o/ b' h6 s7 I. I% J, q# y
递归思维要点 6 Z3 N" t3 [' D6 l0 z, z- S( k1. **信任递归**:假设子问题已经解决,专注当前层逻辑 % |: Z: s& L5 D/ ^2. **栈结构**:每次调用都会创建新的栈帧(内存空间)9 A, p0 w, n: M8 W
3. **递推过程**:不断向下分解问题(递)* f8 d; t; N! E# @; Y# l1 @
4. **回溯过程**:组合子问题结果返回(归), E/ c, J1 ?8 z! E
, h" z2 O4 ]4 j 注意事项. `3 Y! g" H- W
必须要有终止条件7 {2 j6 s* c* l B) c
递归深度过大可能导致栈溢出(Python默认递归深度约1000层) ( c% V2 j# F! T0 D某些问题用递归更直观(如树遍历),但效率可能不如迭代 1 e/ I: M- G( _. @7 G尾递归优化可以提升效率(但Python不支持) . W: @3 `/ M0 r& Z+ n # G1 S6 P& ^1 g0 M, Y& P 递归 vs 迭代 2 S* Z$ s o+ i* E4 o| | 递归 | 迭代 | / u- T; H' U# Z5 [: x" X" E/ M4 {|----------|-----------------------------|------------------| 7 g* |1 S; _" U( J7 p( }| 实现方式 | 函数自调用 | 循环结构 |% L; X" n" e% p& K h( Y( S, h9 u
| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | $ e; L) r: p) T2 T/ h R5 }! A| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 | $ c8 K; \! [, x- [) u' P| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 |5 v8 E8 L& B- f5 H4 v L' ?. h
8 H, ^8 y0 T H \ r8 ]
经典递归应用场景1 s2 v- z0 p s7 `) z9 p; N: I* g
1. 文件系统遍历(目录树结构)* n3 d7 {8 `! v( ^
2. 快速排序/归并排序算法 : E. D! q" S. P& {* Q1 y2 y/ m3. 汉诺塔问题: f) T6 w. d6 h. `" W$ r
4. 二叉树遍历(前序/中序/后序) 2 u+ r, m, D; J" @5. 生成所有可能的组合(回溯算法) $ V- y& y$ q! ? [' w9 e' B! f1 ^* X- W- K2 F& P! J
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, 4 m, ~8 p6 T3 {% j& ?6 e) N我推理机的核心算法应该是二叉树遍历的变种。8 B5 K) }6 `$ M7 O1 x/ Q
另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: # Y: h. r& f3 v/ |% _8 x8 M# Y* fKey Idea of Recursion * r) a1 z* B) Q) o& w/ N ) J L# N$ }7 l* {- Z8 UA recursive function solves a problem by:: J4 `: j4 \7 B& ^! A
2 O2 |* A# t `! \9 h; I$ b
Breaking the problem into smaller instances of the same problem. ; S) C% |) ?( P 7 ?" d A2 l: z6 }4 `8 F3 u. e Solving the smallest instance directly (base case).3 B$ i# v9 f* c8 n, t
% k7 L2 ?# b* I6 z) x" [ Combining the results of smaller instances to solve the larger problem. 6 j: M! y e" \2 J2 Y" d* @- w c, X0 ~3 F' o
Components of a Recursive Function, x5 |% R$ `- l0 s, b# _
* {9 U# Y+ ~( C; n& `- B- U6 F
Base Case:' q1 @7 t1 f4 Q7 h; h0 T
+ U0 n; B" k2 T This is the simplest, smallest instance of the problem that can be solved directly without further recursion. 1 z( m; d* J6 C8 m! ?: d ( ^/ [; o4 C2 q( P3 u5 k It acts as the stopping condition to prevent infinite recursion. 8 P* j9 ?$ C4 D% u' p7 ?' v) h* T( G. P$ U' B0 y- @
Example: In calculating the factorial of a number, the base case is factorial(0) = 1.- A7 q6 J O9 X$ ~- E7 i& B
( a* i7 J# e. V1 P6 Z3 [# z; Y Recursive Case:, [, X7 z& ^1 M/ k' ]8 K
2 G& Q/ s" s: r
This is where the function calls itself with a smaller or simpler version of the problem. 4 q9 ~) V1 t; |* ~& N4 ?; W6 W. u/ m( [- B9 f
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). . i V! b- w3 H! h& r0 K/ s# t( b1 N/ R6 Y0 Q/ B
Example: Factorial Calculation% ?# p- ~7 d+ K
. o2 w5 {# |9 A" k3 o5 J3 I- K
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: 1 G# c+ j8 M0 A* q& K! [: B' q' h % ]9 R: v; g, q; N! \3 a3 I Base case: 0! = 1 ; k' n' I& d( [8 D! K3 i, r/ x+ J5 @* T0 r( M
Recursive case: n! = n * (n-1)! # o$ b* T) i# g" l+ M* l n; _6 C2 k7 I7 T i$ }Here’s how it looks in code (Python): . Y) B2 H& m- m# X, Zpython8 @; r6 ~& Y& D6 X
' g0 d1 ?' G# _7 C& I
0 l3 o n: U; jdef factorial(n): , `/ R/ ]; A5 Z) _. Y( o9 D # Base case # {# n4 Y! g. v if n == 0: ; d- z" [ ~+ o E return 1' @0 R; K' `- D3 u7 V2 |/ t
# Recursive case$ G, R; L: ~! i
else:: a. F, F1 `: ?* N2 O
return n * factorial(n - 1)5 _ S( v4 T) V& B8 L
) {3 {# O- y" `8 O& |# Example usage & `% r5 W: V: L: qprint(factorial(5)) # Output: 120 2 @+ |, K/ w4 x" C+ z2 o& B - _' N; q$ n& E1 S4 V9 {How Recursion Works 2 D( w" J, D) p8 l6 l4 Z! `" K: a. a$ W
The function keeps calling itself with smaller inputs until it reaches the base case., B3 V: d! W( b* Q# P
) q( T8 ]/ a4 \# t Once the base case is reached, the function starts returning values back up the call stack. & i G7 P4 ?# |' s " `- k) C6 F' X5 C/ Z8 P These returned values are combined to produce the final result. % a% q4 Q1 c* ]; ] + F. G' o. j, c& h8 { Z K. gFor factorial(5): # k, y$ B. T8 D. I' T c1 A 3 D! }; ]- `/ t+ I2 O( t" b/ R6 F$ Q& ~& ~" v% W4 }, W q, B
factorial(5) = 5 * factorial(4). h9 {4 P% \, k
factorial(4) = 4 * factorial(3) . y4 i8 n% p& N3 J) ]1 L( mfactorial(3) = 3 * factorial(2) & G6 W* X9 S9 a- z% afactorial(2) = 2 * factorial(1) / n& l6 o2 }/ s2 z. ]* ^2 Y; Nfactorial(1) = 1 * factorial(0)# V. C+ D0 x8 y* X
factorial(0) = 1 # Base case8 V6 P2 H# ?6 x
" s6 [& b) ~! l( h4 n! l4 Z
Then, the results are combined:1 o8 Q2 R$ G: E2 v6 o3 E+ G
/ r! Y, G9 r/ J- ^ 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). - u; R2 L" e+ c+ h5 j! g: V! |7 c7 v( @
Readability: Recursive code can be more readable and concise compared to iterative solutions. & [' t( `- _5 M9 {" u$ k* B& e( Q, x * P6 X- X7 `) g" L4 ODisadvantages of Recursion2 D" ]) W' J) ?) u* |2 R8 ^# E
m8 ], M3 K' i- S( \ H8 } 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.4 U, k% h( Q, D( g* V* a6 G
! i& P5 Q( C1 ]: U
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).+ I% ?3 E4 ]- N) i7 w2 N
6 h! `3 i' g# K# u5 Q: A2 Q D/ h1 y- ~When to Use Recursion / S! n- H; _$ e * ]3 M& \, q( X4 C6 t Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). % T8 R0 h; z, J& e( z5 ]6 s" K: G, `% V- L) B# ~7 T
Problems with a clear base case and recursive case. + y& g# O6 h: Z" S5 |* s $ U% J5 }8 t/ _Example: Fibonacci Sequence 9 B' A: ]+ z( _ t. k' m: h1 X8 e ^( F1 l' G& k _The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:2 ]( u) Z/ Z% }# M9 @- n
0 y3 B3 Y4 U& ]& _7 P* K* P9 w) f0 s Base case: fib(0) = 0, fib(1) = 1) \5 X. l. c+ t9 z+ v; \
* d2 r, {" B6 ^# l' a' |7 Opython* a7 _5 t# Y. n! p
7 g8 \) z- I% P j) \$ O" }: P; P5 _$ V; `8 B9 A5 ^
def fibonacci(n): 4 ?$ {7 _# e Y- ^2 e# F; p3 b ` # Base cases * W1 j0 R h) D6 g) H9 H! ? if n == 0:1 Y0 b2 y) l$ W
return 0 ; D+ g; B9 u& N" I3 \% T1 u) H% f elif n == 1: $ k& L/ J) r4 U/ S- h& K return 1& P- c7 e" a" u8 b
# Recursive case, d' R e" a# M, ?
else: ( L2 N& {% R7 J! |4 x( y: [ return fibonacci(n - 1) + fibonacci(n - 2) 7 i2 h7 \/ X7 m6 j9 c: @ O1 |' `& |# N* V# Example usage 4 i5 E; [- R7 |print(fibonacci(6)) # Output: 84 H3 ^) J! j; T% ~- Q' `
1 T: N9 j6 i: eTail Recursion " ^8 Y$ R8 O3 [. c: z " ]& W/ M; F. w& T- [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). ) j8 G# l2 X3 e0 o& @9 M9 ~& x" h- L8 W5 B, X! Z
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 现在的开发流程,让一个老同志复习复习,快忘光了。