/ v, w8 z5 _) |4 N 递归 vs 迭代 ; _+ a' {, r; z5 H+ z. e% v* T| | 递归 | 迭代 | $ b6 Z* k/ R) k! T|----------|-----------------------------|------------------| 7 J& C& U9 z( m+ i. }9 }| 实现方式 | 函数自调用 | 循环结构 | U0 I0 \9 Q A: m| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | * y r9 H- f! }8 j' m: |+ l| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 | - T- B5 c# f( x: U, [" [5 A6 U| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 |. x' I0 s( S) _% T) i
2 R! f% j/ `# M' W& ^$ b3 L
经典递归应用场景/ r6 n. T* o/ u8 B% `7 z
1. 文件系统遍历(目录树结构) # O& y4 l0 O0 P# y" v. p2. 快速排序/归并排序算法 0 B2 }, F0 o5 Y3. 汉诺塔问题 2 H; T6 J5 X& S# }& H$ a; P4. 二叉树遍历(前序/中序/后序) : C# r" O- h, H$ ?% x" U5. 生成所有可能的组合(回溯算法)8 N9 {" E, f- z' I& @. y9 @
) p4 W- E3 r6 r' I% {
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, 2 k ~! |( x3 o* B6 ?. i* s我推理机的核心算法应该是二叉树遍历的变种。8 ^6 G' n, l. ]- e
另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:$ k8 ~5 ?4 d& W+ L, U; X: U$ N
Key Idea of Recursion8 n' m. S: M; `& ^- f9 ~" P
, {; x: M) v/ E+ ? dA recursive function solves a problem by:- _! _8 }$ [8 x3 a
; H& @" a" y8 x% [% G; O2 C% y Breaking the problem into smaller instances of the same problem. ) E3 \1 K% I* x) X: y* [! Z l9 L7 P, O* @
Solving the smallest instance directly (base case). % V6 `7 {- W! v+ \ 7 Y; r! C3 W$ H/ t+ L) y( Q Combining the results of smaller instances to solve the larger problem. 6 J% v* m2 l$ v9 V$ Z( f' J- ~6 a& ] " ]$ ~' J0 Q; {0 QComponents of a Recursive Function 7 | F# D: r6 e" M- q2 J/ C9 f/ n) I: Z! Y3 Y; |. ?
Base Case: % X1 b, h( N' o1 g" @1 y9 G9 m% o; [: g: `4 N9 W P
This is the simplest, smallest instance of the problem that can be solved directly without further recursion. m J( q( J+ a+ m+ ^
5 [& B# i" ?# C It acts as the stopping condition to prevent infinite recursion. 8 z' \# j$ \9 r- a* n9 q : O' f L- ?9 i8 c3 |! T$ K Example: In calculating the factorial of a number, the base case is factorial(0) = 1.% \( }- _- A$ U$ w/ k; j, T/ k
$ R1 d& S& P2 \0 V Recursive Case: 9 F1 i, S E$ o* v/ t 7 i3 s. T( ~$ g This is where the function calls itself with a smaller or simpler version of the problem. 5 ~: ~5 M$ p2 U- y* h, @3 a. u0 `1 e6 E. T! q c
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).% g4 D6 o5 i. e1 m) H2 I8 }
' V' S; ~( N8 D' H' V+ g' u2 D7 M) }Example: Factorial Calculation- f7 G+ b+ {' J: G- D+ O2 Z# ]& O8 A
6 z) |- u0 i+ x* R* y) ~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: 5 R& f9 Y7 j/ M5 f1 t9 X3 z7 @" m3 Q8 ], y# H4 E- A& Z7 b8 ~+ A# B
Base case: 0! = 1: S; q4 F5 y* Y- X( N3 S" f
9 p# N1 L; k6 a2 N' p
Recursive case: n! = n * (n-1)! # X8 T r% C7 y3 F$ |% u$ `! O s* B Y3 a) R% l
Here’s how it looks in code (Python):+ L) s1 s. e3 [) f
python 7 @6 z2 h5 ^4 E7 B% A; `0 W) p7 m1 I
9 N& p3 }1 f4 {7 Odef factorial(n): % c. w# @3 N% Q; G # Base case7 n# g7 ?/ `# Z. c1 c2 Z3 M
if n == 0:+ W N8 l& M U9 X$ n& l
return 1 4 H* r) G) X) o3 j% H# m- D& c7 t; | # Recursive case / b& n* }+ R+ g9 c else:, t' H$ u8 k$ m+ B- t, M: b
return n * factorial(n - 1)8 L" c5 b0 s/ {6 V/ P- \: O
( M1 z3 t8 ]& @; d1 j/ r/ M
# Example usage 4 } ~" |2 r' Nprint(factorial(5)) # Output: 120 2 t6 g1 ]9 E5 c* o' L. D2 ?1 ^( b1 N* T0 E4 T7 ~+ }3 o
How Recursion Works+ C. E- S5 \9 V$ r
( D6 |& B" }9 l* I3 ]1 I& _: _1 y The function keeps calling itself with smaller inputs until it reaches the base case. ! a6 q {' j5 m6 U# l1 P5 B0 n" Z' Z; s3 o( P& C$ r- j
Once the base case is reached, the function starts returning values back up the call stack./ {; a7 \6 D) O6 t; N0 {
/ n! S; o% ?& ?+ o5 ^- x p1 ` These returned values are combined to produce the final result. : C% l' p( x4 _/ C ) T6 h$ I6 N' KFor factorial(5): 0 O1 f6 H' y5 u4 t1 c, ^- d* Z ; J9 Y5 H4 F) A) c/ H" c( a# { 9 Q T( K9 z1 gfactorial(5) = 5 * factorial(4) - l; F- a" m# |( v9 Zfactorial(4) = 4 * factorial(3)) M, b, _6 G# M$ t6 @ c2 I& v7 p; o
factorial(3) = 3 * factorial(2)( s% V- o" h% {3 H, l0 G
factorial(2) = 2 * factorial(1) 0 w F$ g, Y5 Ufactorial(1) = 1 * factorial(0)5 X* `! { L& Q; j
factorial(0) = 1 # Base case / P0 }/ C' [- [+ R# e( i/ U3 O1 W/ [9 L0 r# S7 o% b
Then, the results are combined: \/ d+ m/ X! h' ?
4 M w8 `! Z0 z 3 z5 M [+ E* hfactorial(1) = 1 * 1 = 1 ( J, Q3 |0 M) t" h3 d* Y6 \factorial(2) = 2 * 1 = 2 - ^* V: B8 D- n1 O e7 }factorial(3) = 3 * 2 = 64 ]# m; c" X# [, D9 f/ T
factorial(4) = 4 * 6 = 243 [% F. V& [4 }8 U8 Z# q
factorial(5) = 5 * 24 = 120 - i2 c% r% x- M3 g; u$ C 4 K) o/ w/ @7 f4 R- Y& oAdvantages of Recursion \( d8 z3 v- d5 k" p( T
2 A6 k, n# v. B. d8 S
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). # M; c1 A. @+ U- F0 ] / t2 l6 b; L% G! Q Readability: Recursive code can be more readable and concise compared to iterative solutions. $ g2 m% c8 @3 M $ C& ~" }- q" t9 v3 H8 ~: F% Y* ?. @Disadvantages of Recursion + M( s2 X- u6 D3 V1 ]; X+ p. T6 k' e k0 K/ r8 s7 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 s; j+ B: x0 Y8 Q& I* Z& ^$ s; _0 P" F: H5 w- R" w* j
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). . d0 q5 A" m6 V3 \! E" U" \) i$ y2 l$ s! N! x: s
When to Use Recursion $ s' E# S1 y6 V8 w8 K" y, S1 b7 H, G6 @
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).- Z4 R" C3 _, _( O
5 f/ ]$ L5 R: b7 }8 [9 h
Problems with a clear base case and recursive case." R% l N* L6 R0 D3 Z
: b5 z% [( O0 o/ v
Example: Fibonacci Sequence ; N& f6 ]. P. ]* j) @0 Q8 a - G/ Q' b8 ~9 ]4 q8 DThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: @* e$ [( L) x# k6 L
& D/ T, ~8 w6 Y+ {! i Base case: fib(0) = 0, fib(1) = 1+ W/ X! _( ?$ O/ D. `
- o8 e* M0 i7 I" V2 f1 [ Recursive case: fib(n) = fib(n-1) + fib(n-2). W* E- @1 ?& { R9 {( n
0 [% `4 o& U/ L" d
python 4 C' n, o( }; J0 s: p: M0 t: n( d/ @! I
& g e x% e3 _6 h3 o
def fibonacci(n): e% b: R) P, T7 i+ r2 L5 T # Base cases& p8 P4 N0 n8 |& U3 h2 u
if n == 0:' z! @6 H/ |: Y$ L: X) W
return 0 3 i. f! d' C+ D) O elif n == 1: 9 y- n" [7 H4 N' R0 B9 ^ return 1 ) z* N" W. P8 y # Recursive case- D4 p; \' x2 V, T; ~$ c
else: + l, K/ |! X( y/ n3 T1 b return fibonacci(n - 1) + fibonacci(n - 2) ( q3 d; k0 |! I F6 v/ K( U" I0 `9 E+ s% {' p& @: V# ]
# Example usage9 e) B7 l3 b3 H( Q R; C! b2 P& R
print(fibonacci(6)) # Output: 8 , y" o' G; L" {9 Y! ]. @ q) s0 \7 X2 ~' `
Tail Recursion8 r; @8 x( U. t, T- @- u
, Y. c8 t8 Q6 ]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). " n$ d2 S! N- Z% m) j5 j8 u+ B! I1 i# s: 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 现在的开发流程,让一个老同志复习复习,快忘光了。