) Q8 l* M( V) |5 D: F 递归 vs 迭代3 v2 H9 \( A3 A6 J. R% p9 h1 K# H
| | 递归 | 迭代 | # P2 e0 [* O' J% G) T|----------|-----------------------------|------------------|5 N) }; v+ s+ [4 r7 a+ ?3 }. N1 p
| 实现方式 | 函数自调用 | 循环结构 | 7 a' I1 L* M# y! t9 K| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 |" e/ Z: L% s" O( ~( r
| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 | + c: f, a5 I. u% o @3 ^* p$ m| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | ( t1 Y+ H% Y0 r1 Z6 l' } 9 z, M) |. m) u4 Q& {2 S3 A* i: B 经典递归应用场景3 w: F% a; X2 @7 A4 N
1. 文件系统遍历(目录树结构)6 r0 ^/ o6 ~/ {/ Z# U
2. 快速排序/归并排序算法 s w# l) ]7 v
3. 汉诺塔问题 # H a( g D, _. x% ]& G _4. 二叉树遍历(前序/中序/后序)+ s' X U, C# ^9 ?% _ [% f
5. 生成所有可能的组合(回溯算法)* j0 B8 k1 Y+ _( D1 c
; N. b. I, O4 l9 Y |
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, 3 p! E8 o V- j我推理机的核心算法应该是二叉树遍历的变种。0 _( c8 W8 R& H* u+ C/ 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: 9 D% S% V9 k: g4 i; H# f1 nKey Idea of Recursion9 m8 Q/ B- Y9 R( T/ ^5 s5 Y
7 E5 L# \# c1 `0 N
A recursive function solves a problem by: 8 w s1 _, w8 u2 {) y! e5 K9 N 9 @2 U1 E3 m9 p( R Breaking the problem into smaller instances of the same problem. _& W4 @4 {/ H' P# _/ _6 e
b- {+ f* e6 F3 c
Solving the smallest instance directly (base case). p( w `! x$ Q$ O' @; M! l& H! g5 d& ~5 H6 x# @
Combining the results of smaller instances to solve the larger problem." X3 {, @5 N& m& r
* f. S# I& E V6 {% t8 xComponents of a Recursive Function 6 `& p% }% ]* q" y/ a 8 K8 ]! M, L* B8 J Base Case: 9 t0 u: R! \8 S1 b1 c8 f: V' W& _ ?6 ]8 O
This is the simplest, smallest instance of the problem that can be solved directly without further recursion. + K6 }% \# A$ [$ J! I5 ~# h0 q+ P* V2 {
It acts as the stopping condition to prevent infinite recursion.; h4 b% }& b% O; }: |# \- x, A( u" p
- f0 F+ l8 L: A5 D Z5 }' U Example: In calculating the factorial of a number, the base case is factorial(0) = 1., w4 E+ K* G: S9 x2 j& q
1 P" F! Z4 D+ w9 t0 w' _! ?9 C" s
Recursive Case:9 F5 ~$ m8 G% Q
+ L. L9 k% @% {8 Z$ x- ~; h7 e. u9 y
This is where the function calls itself with a smaller or simpler version of the problem. 0 b3 J7 e9 N- ]6 P1 u1 r; b5 o6 S& e, @8 g
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). 9 Q/ |+ { f% f6 x# s% S2 b, o" ^) M D) s# ]6 E" Y) R, \, K+ p
Example: Factorial Calculation% P- z9 l; i7 Q2 ~/ i
- q E6 f4 J4 o; `: }: S/ r0 d0 f7 {7 wThe 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:6 f/ N# `0 ~* I5 T8 l
6 T" j- i9 c3 G
Base case: 0! = 1+ i d! B0 a8 [; L4 |$ }5 n# j
$ t8 S+ Y2 b( p- l% o
Recursive case: n! = n * (n-1)!& v3 O" v9 n$ [6 }, g) V. a8 _" f9 {0 L$ V
1 U; H6 }9 L, y2 t( F8 ]/ A' N, J2 x
Here’s how it looks in code (Python): 3 L7 [: s7 Q7 j0 Lpython 1 ^- v# w" V2 N2 I/ x: [6 G5 V F5 v- n0 V/ o+ y+ R
+ K4 u( i* p3 @$ i; Y ~; f. F
def factorial(n): 1 k. M6 T& e& A) r. b* e' u # Base case) p( [' O2 q% X2 Z: T
if n == 0: ( Q; g, f6 x! d* u% ~ return 1 I; f4 M; C, |* F- `( v
# Recursive case ! v0 G! T, L% M# b& T$ l else: 7 J' r3 h8 X* L0 i4 E0 }, { return n * factorial(n - 1)$ @7 w. O+ ^) ]5 b9 s
$ l8 a8 K* M$ w) a7 L: E# Example usage" ]! V3 c4 r1 b- k) I
print(factorial(5)) # Output: 120 # N% i& P6 L. Z# d) `' W 2 l @ y4 [) C0 ~! k9 THow Recursion Works7 A4 T; |% a7 W. k, T
6 Y, Q4 |/ I" R8 d3 s% \2 _ The function keeps calling itself with smaller inputs until it reaches the base case.0 t. e8 c4 K5 D1 e U
. c/ \8 X! Z- ?5 E/ U; ~ Once the base case is reached, the function starts returning values back up the call stack. % f1 Q& c, A. q. j6 F: y; s8 [9 b W( b$ W, L S* z2 v
These returned values are combined to produce the final result.# {5 T' M% w5 Q! r+ C) e+ S, \% A
! z o& ~1 P3 O& f9 o2 s& m
For factorial(5):9 {3 h2 _9 ~8 [6 v" Q
0 `4 q0 q& ^- s0 k4 j* P7 t* W0 N+ v
factorial(5) = 5 * factorial(4)+ A( D# k0 _$ Q+ \
factorial(4) = 4 * factorial(3)8 |. M# x/ `! t/ `0 T: t/ o# |0 R
factorial(3) = 3 * factorial(2)# k. y' M/ Q, ~0 g) ]/ G6 |
factorial(2) = 2 * factorial(1)1 D- X- Z3 m3 y' l6 Y2 A
factorial(1) = 1 * factorial(0) ! S* n1 w2 \# j0 N* sfactorial(0) = 1 # Base case 3 F1 A& k/ T$ R5 T G ' o, I& }' r) b4 B% pThen, the results are combined: 8 q0 d }% v0 \8 ?% m$ Z 4 G$ k" _ h8 v) t9 X7 h6 A- f3 f5 Z9 T
factorial(1) = 1 * 1 = 1 1 M; q8 v5 m- \1 ^1 J( K# vfactorial(2) = 2 * 1 = 2 1 p# } B L+ j6 t2 N6 @6 lfactorial(3) = 3 * 2 = 6 8 U& ^& F0 f& z5 Tfactorial(4) = 4 * 6 = 24 . ^: U2 _' x/ c3 `factorial(5) = 5 * 24 = 120 0 K8 n. r+ h1 v' G0 `8 U1 p# }/ d ~ B
Advantages of Recursion! c1 M1 c2 Q' {7 T* ^
8 w ?, \ t% l5 l# t- M, |
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).6 E" L7 B: j! Q
5 x% ~5 @9 \ s8 b# p( c7 j% p
Readability: Recursive code can be more readable and concise compared to iterative solutions. 0 B+ q% T& e: x; \3 ^ " n) o1 A4 |! |7 T: RDisadvantages of Recursion 5 d3 Z! g& t, K; E6 t3 i( ]9 p; t/ Q& o
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. 7 b2 ~: o D/ t5 q, o! s4 W) v ) u9 K# f% q$ n Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).% Q, L7 G( X9 C, }
: A5 m( D( d; ^. R% B& ?; {& f" Y
When to Use Recursion8 a _& [, g2 _. i7 x+ G+ V
$ e. a+ H7 G/ I' |, _ G
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort)./ H) s1 z% H4 z
7 q0 o* ?$ K3 B% H Problems with a clear base case and recursive case. 2 K* p! V9 B' T1 E4 @: [' u0 Q0 Z) u, l$ r
Example: Fibonacci Sequence3 D% Y' a% j: F0 f/ O
% ] Z5 I y* M( o* D
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: 3 r& V. b8 w/ `) b, e ! E9 M, a) {/ Y Base case: fib(0) = 0, fib(1) = 1 4 m$ n7 Q( ?3 }7 s* e0 p# S + N. ?9 h- F5 B2 M |$ z/ J Recursive case: fib(n) = fib(n-1) + fib(n-2) : w. U+ T7 ?4 ?# U' m 9 N- v( G) p! p% t% d# @python3 J6 R1 f9 g& z3 \% a
5 _4 l6 V; {, H 6 B" K- `6 Z2 }1 V5 i4 ?def fibonacci(n): 5 f" p% [! l& m' B' u/ A' G! Z # Base cases5 `1 Z& b2 e" }" \, B \5 v
if n == 0: ' ~9 v3 `4 A3 B6 ^ t% \- I return 0* Q5 g. H1 z2 Z+ L% m* g4 _
elif n == 1: $ B$ }1 n$ |& t0 f return 1$ [6 Y E7 e: |+ U
# Recursive case b" P6 v6 m- }4 l* N
else: & r' |3 c7 s1 f$ ]: A% ]2 _, x4 P return fibonacci(n - 1) + fibonacci(n - 2) 1 J1 M! F* n( V) T' s4 S$ g1 o; v k- J1 ~. ^1 G8 r# D
# Example usage A- x0 @. P, o0 D9 Z; a
print(fibonacci(6)) # Output: 8 9 y$ m* f) q+ T$ ^8 R; H9 [( `4 {1 { $ D0 y; m3 ?+ d& c) F& d. NTail Recursion, r- p2 ?, Z* B7 N/ n) `, z
) H0 r w6 I. X+ ^3 P
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). 0 x7 q3 z2 D/ x; G; [1 R3 w% r* w0 y# b! k2 A+ o/ R
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 现在的开发流程,让一个老同志复习复习,快忘光了。