& d: \/ w& w5 q0 A& g( D递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。 2 @/ @3 Q9 u2 G: e* O. G & p$ J |. R; \7 \! r. Q" y 关键要素# L7 w9 o4 G4 q
1. **基线条件(Base Case)** / e/ g! ~, R9 a4 K# u6 D - 递归终止的条件,防止无限循环( o* h" u, ?# P' x" Y( r. x1 ]
- 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 % f9 `0 n. m" `6 w& ~$ X4 B# D' _3 N- F# ^/ K% U; t: ~4 f( y/ R. V
2. **递归条件(Recursive Case)**2 K% |+ k f- V4 P- d
- 将原问题分解为更小的子问题$ {( F; d8 V% l1 M
- 例如:n! = n × (n-1)!5 V$ n0 [% B( ]8 m1 g1 w& y
% X$ w& [4 ]7 S- |
经典示例:计算阶乘$ m/ b: Q% H# \, P) ^' y
python9 T. e# ]4 D0 J/ m4 Y/ f
def factorial(n):7 D* @! v* J+ T$ U" r( s
if n == 0: # 基线条件 ; a( T+ y. @! f* c return 1 4 O4 U" Y3 X% i0 h9 e7 | else: # 递归条件' i- V5 r8 b( ^7 E$ a
return n * factorial(n-1)4 [+ x1 p1 m+ _6 E! w1 d9 _/ g# C
执行过程(以计算 3! 为例): 4 g0 X; j1 r1 M h" _/ B4 Sfactorial(3)' i4 i3 G. _0 X7 H' u
3 * factorial(2)2 R* J$ _0 X1 u4 z" C( C: F
3 * (2 * factorial(1))% D! M3 I& J1 y/ K1 x0 H' `
3 * (2 * (1 * factorial(0)))5 r. E2 M/ d1 |3 J
3 * (2 * (1 * 1)) = 6 1 X8 K4 i1 G: q. q1 }$ m& }( E( G- w& P; ~# ~ ^/ b7 w
递归思维要点. j' y! c I" k
1. **信任递归**:假设子问题已经解决,专注当前层逻辑 8 @3 c3 p' k' i% e( R2. **栈结构**:每次调用都会创建新的栈帧(内存空间) " U& h8 f, N' E# R% d3. **递推过程**:不断向下分解问题(递) : o* w" a/ ~# _" d4. **回溯过程**:组合子问题结果返回(归) & H; y2 I- [" u3 [: ]$ J0 ~ 9 z8 c0 V9 }, u% U/ e; ?. a) _ 注意事项3 G: @8 ?7 L. }8 y6 A {4 C
必须要有终止条件 . M4 `1 x- \! h# M) t( R, `/ f递归深度过大可能导致栈溢出(Python默认递归深度约1000层) 4 b1 @# a, n, w& L9 T! M某些问题用递归更直观(如树遍历),但效率可能不如迭代 $ s6 m; b( h- J d; j1 h1 G尾递归优化可以提升效率(但Python不支持) o3 S) [0 Z9 d, `: B- L8 y: e* K3 Y; f
递归 vs 迭代; \ L+ z/ C+ P+ C' x3 n% O! C# ~8 P2 }
| | 递归 | 迭代 |9 E2 o+ h0 z+ O% n' K: |
|----------|-----------------------------|------------------| 6 z! d/ D# K5 e$ h| 实现方式 | 函数自调用 | 循环结构 | 2 C/ {* p) {4 L' Y( _+ @* h| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | 0 O9 s' b+ k: j$ X, ]7 M| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |: [. a: W( U1 J0 ]' x! y. \
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | 4 X0 _0 `! T9 w; y3 l 5 U. V/ P6 `$ f, v 经典递归应用场景 2 B- A% t7 i. B- T0 n4 T1. 文件系统遍历(目录树结构) % W9 w9 z: Q, D( q5 S+ v4 y2 E2. 快速排序/归并排序算法# y4 |0 ?& l) V6 G+ Z( g5 m" q
3. 汉诺塔问题 * J, P' t% l! q+ c4. 二叉树遍历(前序/中序/后序)# K6 n t! \" z% k
5. 生成所有可能的组合(回溯算法) $ `- K* x3 f& f( d 9 d9 Q8 B4 q! v( q试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, ( q" K8 t6 _( @& d我推理机的核心算法应该是二叉树遍历的变种。. f; \& x* q7 [* j( F4 a
另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: 0 r5 f' V& N9 H( }/ e$ [Key Idea of Recursion / {/ V. Q+ q2 j4 J* W1 q8 J) _- o5 @ Z0 m3 \# L$ m; ^: D
A recursive function solves a problem by:, j/ X: S+ k0 ^7 o( b9 R2 d
3 b# b" |' u" T- [: v) Q6 ] Breaking the problem into smaller instances of the same problem.1 Y/ n3 T$ K3 _* p1 b8 }% f* s# D5 U
7 ~; r+ ?1 z7 g7 ]) h! h% q% y
Solving the smallest instance directly (base case). ; z$ N6 o/ h% Q- D$ e3 `! v7 H2 v, w9 C/ x/ P2 Y) Y, F% @, f; E
Combining the results of smaller instances to solve the larger problem. ) R! _& G- A0 N. _' d7 G& J6 ]# l5 H6 W7 I
Components of a Recursive Function $ d) T6 n( A# Z& M. c & _ u9 g- }/ L" u Base Case: 2 R; d, ?5 }5 Z& L/ K* }0 F% E& `1 d9 |" l' F4 S# L- ?, j
This is the simplest, smallest instance of the problem that can be solved directly without further recursion. 8 ~) {; e) q, {, e1 r7 F' l! [: K( n/ K' T1 J; g
It acts as the stopping condition to prevent infinite recursion.5 C3 `- Q: y& l+ o$ ]# p. P/ P
! ?7 W- p3 h: o% R
Example: In calculating the factorial of a number, the base case is factorial(0) = 1. , H7 U& l" k+ Y5 e9 \3 S- [5 J , N1 O* T- x! l9 j& X Recursive Case:! R' `% ]2 G: V# ^
! }. Q4 y" @$ I; l, C1 U1 u
This is where the function calls itself with a smaller or simpler version of the problem.9 o7 U) O$ a- _
' H3 A% c0 E5 w& [9 @* q9 U Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).: O6 p3 h2 w& Y7 W& L+ ]" x' |
( ]6 m( }$ Q$ \+ l) a8 ~. H
Example: Factorial Calculation) m; l v# I: g! B
) g; m3 Q* ^2 n, [
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:, P# X, D6 X/ Z U0 V9 V
* ^) i; E+ K8 a Base case: 0! = 1 7 T) { H- K X: W2 O( F7 Q! L+ [; N4 M
Recursive case: n! = n * (n-1)! 2 B1 i+ R, @) P' Y8 r & |1 a; M9 h) S& HHere’s how it looks in code (Python): 3 I8 N+ v+ R7 w. Y# Spython - @: r# P; ?( e5 R, Y7 r* ] 0 |2 r2 }: K% h. g6 u) y* \/ N% [; f; W a4 ?7 K+ B
def factorial(n): " y$ V9 X0 l) Z C$ B) h # Base case/ R3 q: Z7 Y% ^! J v6 _; e9 y" P
if n == 0: $ t% M* e2 m5 U/ d5 T0 \+ q" S return 1- t; B& }6 @: N3 A( ?; D
# Recursive case" ?! b7 q- M) A: {$ ]/ x
else: 6 ?; f! t7 d0 P; d: ?7 n: R4 t! P return n * factorial(n - 1): ~5 {: Z# H8 F; {2 P" V
3 z p* O( q4 y" w& X* y6 O, T# Example usage / j3 [8 x; T# l" `print(factorial(5)) # Output: 120( j/ m x& a- `5 C
, \! r F" x) K4 HHow Recursion Works) N8 N+ T: s4 J( M5 G1 Q
U8 K; L3 I, w
The function keeps calling itself with smaller inputs until it reaches the base case. ( d* Z7 |* Y: ^% I# ]5 |9 ^5 u0 Q3 c& O/ ^! |* Z
Once the base case is reached, the function starts returning values back up the call stack.$ h) {8 e* ^- X% K' o$ ?+ A
2 Y2 g2 ~8 x* r) F3 e
These returned values are combined to produce the final result. - t& c! u2 @: H$ g. c/ g6 A ' v, `" o4 O% f: G3 p, ^5 DFor factorial(5): + z( F/ N# p( b' z, e7 E+ r, K) _9 z( ~5 x3 B6 Z
! `* X( b+ Y" l A- J4 Gfactorial(5) = 5 * factorial(4) ! ^# [* ^) r" g/ afactorial(4) = 4 * factorial(3) & {. c4 c! t, k& w. l$ Qfactorial(3) = 3 * factorial(2)* C- s$ K) I v6 U2 S" f
factorial(2) = 2 * factorial(1) 4 M$ l- s8 T" q# c. d, c' Ffactorial(1) = 1 * factorial(0)( @( Z) E; X! i- ?1 L" ^
factorial(0) = 1 # Base case 9 H. j. C" |! M3 N6 K. M5 S$ q. O% a$ k d# n! @5 n
Then, the results are combined:# Y) d% U7 r4 {0 a4 g" J
: n9 u% Y8 u9 a. @! d4 d8 v$ p+ [% U. y1 J8 C- b" W
factorial(1) = 1 * 1 = 1 $ y) s7 z; Y& b" [factorial(2) = 2 * 1 = 2 9 A- |$ g# s8 [ xfactorial(3) = 3 * 2 = 6. A" ], t: f# J" y& ^7 l, K0 J9 D% M& M
factorial(4) = 4 * 6 = 24. t$ ?' t9 }) s {" H- ]
factorial(5) = 5 * 24 = 120 # ^, j" r) |/ d6 I8 p4 |* b8 a j5 j8 I% n& p
Advantages of Recursion 3 ~: y1 N8 ~& K! W, `& C' l0 \$ F , l, |* F6 M( `9 ?- c 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).( r. p( n1 ~$ S/ `) B5 o
( z7 E1 P6 e9 F& }. C& l+ g
Readability: Recursive code can be more readable and concise compared to iterative solutions. & T. M# V( [- I. G! c$ P : ~& P3 Y S b1 b% r yDisadvantages of Recursion8 p4 t2 R7 U% O6 ?# c
" I/ ^! U! a. d& n* D 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.8 ?" ^) \2 b* d/ D, j
* Y7 }( p# T) _9 D Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). ! S% D* `% t; k7 | V2 ^- r8 [+ q) @1 C5 p# }) p# X
When to Use Recursion + u- z; H1 }4 A$ k! Z9 U, Z; E# Q, u/ W/ O2 R
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). 9 c: g1 v$ O; z8 `5 P / |2 O2 X6 T/ z1 S8 E7 w Problems with a clear base case and recursive case. 7 v2 s3 x1 |1 Q( i( v7 ?; f& r! D8 ^ ) y' U3 k. ~3 T' [3 g0 g+ EExample: Fibonacci Sequence 1 A# F. h K2 Q; P6 q0 ?% b3 R6 J1 Z) T' \ B
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:9 o( b% w' Q# Q- \6 I
: [' q! [! ?5 `* ~
Base case: fib(0) = 0, fib(1) = 1/ H: Y- F$ M* A* S# f' U$ _
* n. G3 {8 }7 j% `5 }
Recursive case: fib(n) = fib(n-1) + fib(n-2)7 u7 {7 E4 n+ C& N
, A) }, l& g7 }9 s/ B( y8 O4 ~! Q
python & a6 K! E* T! @( m7 T1 d/ ~7 |; e9 W+ T! D) m- O, R0 E. G
7 {# K# A: m) y. O6 v+ s& C4 `
def fibonacci(n):+ T& o- M# J/ b" c/ r: S6 M% ~ m
# Base cases/ U/ q3 O c2 r+ H5 c+ L+ {
if n == 0: 1 n8 }6 ?# C' U9 u- q return 0 3 V& D- e: M5 P1 `, \ elif n == 1: ) x3 W. e/ x3 S. P! U6 \ return 1 $ B3 m/ w2 S' _) W # Recursive case8 y0 D6 q3 F# Z3 X/ n# u+ Z
else: * ?( R2 V3 {2 m; Q0 \0 ?6 ~' V return fibonacci(n - 1) + fibonacci(n - 2)7 L3 N( h9 S# t8 W& n) z
8 D6 c! a7 X4 ]" I/ t* D9 \
# Example usage , Z9 \0 ^- l$ jprint(fibonacci(6)) # Output: 8 ; ~# K, c$ h: q; G1 Q: n; J6 D; R9 q) G d
Tail Recursion! J; d7 x9 e. s1 D" j1 `; q
' n2 X% A. ^" \+ g7 w, @9 {: GTail 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 q+ C3 u3 a& x3 f7 J
! X8 g" ^9 t9 `+ V' @) }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 现在的开发流程,让一个老同志复习复习,快忘光了。