4 w$ [. Y( R$ J" D4 D" \6 d 关键要素, z; L% g" N6 H: e* F( g' p
1. **基线条件(Base Case)**5 a0 ^, J; x1 R z
- 递归终止的条件,防止无限循环 2 B) y2 Y; c e5 y - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 r) Q& |0 J9 E) S+ ~
& ~ q4 N* p8 L4 b: _- g' l9 {8 F9 p
2. **递归条件(Recursive Case)** % A1 _' @0 n) g" t - 将原问题分解为更小的子问题 1 e# h8 i" c/ N! C - 例如:n! = n × (n-1)!' P8 H+ F4 [* A
7 M7 o/ c1 N3 ?2 h1 \: T6 T( M
经典示例:计算阶乘6 u( q6 |1 L, G
python # }, U5 V# {' o6 tdef factorial(n):% g! N1 B1 A) G E
if n == 0: # 基线条件3 B4 n$ T( T$ t! ^7 V0 }5 x
return 1 9 x0 D; _) O; U else: # 递归条件 ; K9 s4 x* v+ H" h$ a' K return n * factorial(n-1)& x% j: z5 x- M7 k
执行过程(以计算 3! 为例):: F. B) C5 {2 p9 ^$ R
factorial(3) 1 Y6 Q. z; \, R ^8 I9 J) x6 g" S3 * factorial(2)! d3 l& C+ C- l
3 * (2 * factorial(1))! ?) w& I% S; @% t
3 * (2 * (1 * factorial(0))) # B" I i6 X7 q1 H' L+ D3 * (2 * (1 * 1)) = 6 8 [, q O0 i: w% C* \8 x; W! H* J9 H
递归思维要点7 J2 E4 V3 O+ ]& J) R$ z
1. **信任递归**:假设子问题已经解决,专注当前层逻辑 / J: t+ d2 e1 y+ V% P( }6 v2. **栈结构**:每次调用都会创建新的栈帧(内存空间) $ _% I7 O1 ]0 K6 V3. **递推过程**:不断向下分解问题(递)( b" ]2 m; K- c2 ^* Y. B
4. **回溯过程**:组合子问题结果返回(归) $ z3 `& n/ J2 a/ W$ A. m + I5 S N$ z) T- p5 x& l* p. c 注意事项 % p$ j8 f8 t' U3 z% H, K/ k9 b必须要有终止条件 2 u; O ~# Z. M0 e# k0 ?& s3 o$ m递归深度过大可能导致栈溢出(Python默认递归深度约1000层) / h: U3 K/ m& F% z某些问题用递归更直观(如树遍历),但效率可能不如迭代% X0 p4 ^# v( z# Q% T( L
尾递归优化可以提升效率(但Python不支持) 5 K6 x) m, f) ^5 I5 Y" N ( }" P$ s& J+ `' J8 z B* h 递归 vs 迭代 5 H2 Q2 A p- v3 s8 B# b| | 递归 | 迭代 |* f! j a2 k/ L8 c2 T
|----------|-----------------------------|------------------| 8 q7 N F& |# ^" I& p* l# H! u| 实现方式 | 函数自调用 | 循环结构 |0 T8 a1 q9 c8 [ ^' `# Q- W
| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | ) q5 V5 L: b/ b7 P) ?' Q| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |0 t. U5 Z: M- C! w3 z, F
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 |( E. j) @5 t/ U9 O
0 b# g9 }7 g1 u" q% o
经典递归应用场景' n+ ?& z0 F% z# d: y/ Z
1. 文件系统遍历(目录树结构)5 a; ?. ?, U5 Q! E& t% O
2. 快速排序/归并排序算法 ' c. G7 E' G: n. _7 H3. 汉诺塔问题 , `+ q4 z; U9 D4. 二叉树遍历(前序/中序/后序) # R# x; O5 U0 `5. 生成所有可能的组合(回溯算法)0 p0 \ g* L: S& B/ M/ M
7 C6 Q% y- ]) U( Y2 p' r试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,7 t6 w1 j2 l' c/ r/ X/ ^
我推理机的核心算法应该是二叉树遍历的变种。 , l" q8 c4 p% P: Q* E D$ o! @另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:% ~9 ~% c, {/ u5 Q$ D
Key Idea of Recursion2 V' P3 R% l/ X8 `/ V# _
. {& c- }0 p( q- _: V; XA recursive function solves a problem by: ~) T. @- K T5 M9 `6 T
% V# a6 }# m0 Q* q0 f
Breaking the problem into smaller instances of the same problem.: k7 n2 Q# y# r+ F' J
8 _* M! n# K3 I3 |
Solving the smallest instance directly (base case). , f: e: ~5 C# Z2 f - Z& ]0 u0 G7 w9 s$ W5 v; w3 H& g Combining the results of smaller instances to solve the larger problem. ! ^& H% u( U2 X( h 7 y* D$ { ^+ K9 |3 y* RComponents of a Recursive Function 0 c2 r$ W z5 d8 B* w$ i! y/ v3 l: A) t% Q
Base Case:2 B# E9 B% s) M% S0 n- }0 z3 P% |
$ D5 ^- j7 i( x) K9 S This is the simplest, smallest instance of the problem that can be solved directly without further recursion.5 A" h. l- }0 }& S* ]
9 z6 H4 j( q( V& [ It acts as the stopping condition to prevent infinite recursion.: A8 H7 D8 L, W' E4 v
8 T0 [6 {3 J: ]( a. s' b/ ~$ O6 L Example: In calculating the factorial of a number, the base case is factorial(0) = 1. , q* p- t$ F3 p( I. b2 s H& p - E, G; ^+ o- }) }' S. u S W$ h Recursive Case:4 i6 W' Y' A1 v: W {9 |, i
: a& z/ \+ }" U# N* w# U This is where the function calls itself with a smaller or simpler version of the problem. 6 `7 I. p) j7 B( p# r$ m. X2 v# n Z7 ]1 G
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). # w6 i: |- c8 J7 x- k; o4 U% U6 S. I6 ?8 Z7 D. W
Example: Factorial Calculation + L5 i3 t8 s7 F : X1 Q# a" q6 @9 ~0 FThe 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:# I$ T- g6 z: p, `1 s. C$ J
2 ^' ^7 [+ }, Z t# z6 b Base case: 0! = 1) e6 r; m, T2 m# w* T4 Y
, e3 b$ \6 j6 Y5 g) H6 f. U! E- ]2 b
Recursive case: n! = n * (n-1)! 2 }$ f' X2 @7 b3 W( D! w) J ' g# n, T! k- y; i h( jHere’s how it looks in code (Python):. G' j- n2 U5 ?+ U, A8 l
python ! J# f; L! D2 X8 @ 6 I) J9 l# J E' x! U3 k+ ]1 G: }1 q2 i( F' z% d
def factorial(n): . ?% H) H+ e! W) N6 }: m # Base case/ w' N; m) p0 b5 c9 Y5 U) s! |
if n == 0: * A2 P; b7 L* q% l return 14 }& `; ? T8 v. J5 m) d
# Recursive case; p5 f: a3 {* N1 o9 v
else: ^& X# |$ }4 _: J7 \' B, M
return n * factorial(n - 1)/ w6 D' A* p8 s$ q, S
2 h$ {; N r6 L0 g4 _# Example usage& E2 }" g4 h6 e2 a3 w# U
print(factorial(5)) # Output: 120 ) u$ l9 p3 W& S1 \0 K% ?8 a' V" r1 q2 o, n Q7 e4 X3 P7 ?
How Recursion Works+ ~* C8 C' N j' p6 @
2 ^5 ~: p- C" [3 T, o1 T$ b3 |! L
The function keeps calling itself with smaller inputs until it reaches the base case.8 L# z* Y5 w! M7 a
+ x( S8 e5 T8 G( r, b
Once the base case is reached, the function starts returning values back up the call stack. + b, b1 K9 ?) a# f s 7 A2 M% K/ t. X: E These returned values are combined to produce the final result.8 D; A; o& u; E/ `8 j# U
# R7 W" d2 }4 S% m3 T c7 K$ f8 NFor factorial(5): " C% ^9 k6 X. z* F! X$ Q* V1 L, n, {7 F8 X5 t
4 H* V1 ]- |) |9 Sfactorial(5) = 5 * factorial(4)4 r8 h/ T- k U
factorial(4) = 4 * factorial(3) % x! E) E: d9 H4 bfactorial(3) = 3 * factorial(2)- I1 S+ [# `. B4 ?$ t; u4 U/ i
factorial(2) = 2 * factorial(1) ) H# v1 }+ {5 Gfactorial(1) = 1 * factorial(0)3 J( p0 L4 Z8 K4 D1 f
factorial(0) = 1 # Base case 0 D5 j- F2 L; } 2 i) c, V: ?3 F ]' yThen, the results are combined:! I m+ V& ]" ?# F; Z5 U3 I2 A3 r
- n$ a% {/ H0 b* X+ S* u6 j, r) ~& M1 h; Y( d, y/ K
factorial(1) = 1 * 1 = 1 9 R' D' [/ P2 h1 n5 [2 n* v8 \factorial(2) = 2 * 1 = 2 8 K" h3 S" U7 N) Ifactorial(3) = 3 * 2 = 6( e1 |; L! c! W* Q2 M& j* y! Y
factorial(4) = 4 * 6 = 24: z5 R* N3 u; B" W( {4 g0 s# C+ X
factorial(5) = 5 * 24 = 120 8 R7 P0 ^ v8 Y" x$ m$ Y. w4 O) }" A2 W
Advantages of Recursion 8 f& h4 [5 P$ a, `. G 9 k+ F5 x( |9 g. 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).; x. {( g7 {8 K% F2 q! I
9 A- `' }0 z$ T; Y' { s3 R Readability: Recursive code can be more readable and concise compared to iterative solutions. " A6 A+ s1 ^* f6 c9 r6 T6 l7 W7 o1 i
Disadvantages of Recursion 2 ]7 D. j/ J. F, U/ T- o/ \4 E 0 v. V. d" } Z: m Z9 } 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.. P0 j3 c2 x& D/ T3 b# O6 N9 l
/ a, J; T7 Q7 i6 H- e0 ^/ o Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).7 t5 @) O' o5 |4 _/ D5 o U
9 t" _4 O+ e7 |$ u! z# a9 jWhen to Use Recursion + j8 D, \* V* h& y8 l- Q* \# m8 L" P. W: X- A& ]
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). 7 a7 \% I6 @" Z6 Y/ t/ J5 ?9 I" {9 J2 e" y; h4 h* Q( i; H
Problems with a clear base case and recursive case.1 N2 ?5 V1 g4 S# g% b2 q) s2 M0 z/ g
, H K5 O( B% i8 w* q7 A
Example: Fibonacci Sequence 0 B8 f. G; @+ `. ?! o) o : I. Z( W5 l/ `' p+ x$ oThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:- e3 p: w* w3 y9 C; u
( { v) J/ z9 F( [& c Base case: fib(0) = 0, fib(1) = 1' {, [- A/ V# A/ g: L9 s4 u, ~
% h3 E5 T _/ G( g Recursive case: fib(n) = fib(n-1) + fib(n-2) : Z9 {- N# B: z/ R2 Q3 z6 v% G9 _7 l1 j, v% I% m
python # C o P, }* G T% S. ^6 t; i; E, c: d7 P& w0 ?" |' X: n& Y; A
1 D5 P+ n" z/ p: F$ e
def fibonacci(n):( d) K! l: |8 i0 e
# Base cases% h: Q% d) k) Y8 B8 j' f
if n == 0: ; k- z7 \) Q- {9 h1 M8 f P. Y9 o return 0 ; R) ?' x- K, l6 [! }3 ~- i- p' Q( o9 q elif n == 1: # T0 v3 A5 B% n# _% G H return 1 4 A( S. K0 P6 d4 W* M # Recursive case ; N: z. z1 @$ z( _) ^ else:. g! O+ k" ]7 y8 i
return fibonacci(n - 1) + fibonacci(n - 2) 4 a0 }6 q9 r( k7 ^2 @# Z" r& v" b f) I& x8 W0 h
# Example usage/ t; J' V' A* C
print(fibonacci(6)) # Output: 8 , T( Q6 K Z. L6 M `8 g. U3 t" |1 A * t- K6 e. Z5 Q* [0 D1 XTail Recursion : Z( D+ q; B: a* | 9 p: m+ e( p* B6 A1 @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).+ w2 \; M# O: ` U
* v5 `9 j7 q: H. S u3 n
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 现在的开发流程,让一个老同志复习复习,快忘光了。