" s/ e l: A) E4 T# I _递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。 1 h, c0 O3 n6 A + v& W8 [3 _: o 关键要素3 |( Z! n7 _5 a+ ^* G& Y# N
1. **基线条件(Base Case)**. \( A$ p0 ]# d8 S7 x7 h7 z4 X
- 递归终止的条件,防止无限循环 ; `8 E& ?0 I& s- v% G - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 ( ^8 T, T, R2 J! F( U& k8 Q& E" o' \+ o4 E5 K
2. **递归条件(Recursive Case)**$ S! l: O( p: M( Q$ S
- 将原问题分解为更小的子问题( E: i0 g, |7 ]/ F' o9 d* X
- 例如:n! = n × (n-1)! & F+ e- @/ O( r4 l & C. S7 d; r. T 经典示例:计算阶乘: `+ _ I$ E ~: ?0 d1 j) c9 V
python" Z6 t$ ]. c8 ~
def factorial(n):& v) L9 J* i& M% m1 h1 M
if n == 0: # 基线条件 5 `& ~9 a6 z+ a return 1' P# l; V$ r8 I$ z' e
else: # 递归条件8 O, k$ w2 \) n, S; s
return n * factorial(n-1) B* k$ A9 z/ N执行过程(以计算 3! 为例):7 a* f, X5 c, b/ z2 b; [
factorial(3)7 a$ `+ C2 j. t% L- G2 G$ W& J
3 * factorial(2) - O' m8 P+ o* W9 Q9 a( _; t7 R3 * (2 * factorial(1))* Z) ?1 {8 c3 ?' i1 K" O
3 * (2 * (1 * factorial(0)))# }+ P. }0 i5 X
3 * (2 * (1 * 1)) = 6- ]1 K& S* @9 g/ Z2 d! j% } h1 F
% A# B; i% t$ H: j6 `2 O) I5 {% b
递归思维要点0 D4 [. J# b/ L7 i; N
1. **信任递归**:假设子问题已经解决,专注当前层逻辑 1 c I, S3 |* C4 Z6 C) ]# R2. **栈结构**:每次调用都会创建新的栈帧(内存空间) 7 a. ~6 W, X e! V- b0 C3. **递推过程**:不断向下分解问题(递)# _7 }6 b$ G* F0 j/ ]9 @
4. **回溯过程**:组合子问题结果返回(归) : F" a& F! L7 {, ]& j4 {' K" X# h! g; e
注意事项 : X2 T2 |; [0 z, _必须要有终止条件 . p% A2 y) Y( c F, T. _% ^递归深度过大可能导致栈溢出(Python默认递归深度约1000层)3 J& E5 J: s2 I& J$ U% r# t% i
某些问题用递归更直观(如树遍历),但效率可能不如迭代 1 v* D! ~& U& s' f) b尾递归优化可以提升效率(但Python不支持)- B* W5 W8 j' }5 n# d& ^0 v4 h
- K7 e0 r9 t g
递归 vs 迭代 : f; S, G2 g3 \8 p4 w3 L| | 递归 | 迭代 |- D T6 ?# m2 w
|----------|-----------------------------|------------------|$ o8 Z, z U. S& K/ j E& h
| 实现方式 | 函数自调用 | 循环结构 | 1 N- X- {; _$ Q( H/ p! ~% _8 M| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 |; J$ {+ ~9 n2 O4 i* \
| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |; l, v6 ~6 D, k7 \) U
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 |1 W+ c) ~. Q) K
1 i' S g6 s; B- w" ?. f) s 经典递归应用场景& j) l! R5 _4 I6 n; H( O: b
1. 文件系统遍历(目录树结构) 8 r. ?2 d/ n- S5 x2. 快速排序/归并排序算法 3 N, O& ]+ Z- J3. 汉诺塔问题/ D0 j6 D* L; I. F! ]( u* `
4. 二叉树遍历(前序/中序/后序) 6 l: H4 h* n$ L# ~) k7 r8 K5. 生成所有可能的组合(回溯算法) . |+ `- i- S: C3 k* s7 e3 _0 e1 ]& Q0 _$ `# z0 d9 H5 ?
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,& t8 l5 x T% p. z8 _. q8 [
我推理机的核心算法应该是二叉树遍历的变种。 $ z0 |6 f4 ]+ o0 J- e, @) s: x另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:6 s) `! g, C) }: ^- {% P; Y$ O
Key Idea of Recursion, I% j( l' Y" z% {" h% F2 ]
- l4 ^# ?! K3 u: Z
A recursive function solves a problem by: : I; B% x1 N9 g+ `9 E8 |" z 7 S- v4 e( P/ [: V: r Breaking the problem into smaller instances of the same problem. * i# n7 ^. D8 n# j5 _ 0 M% }8 A# j8 A3 m) m Solving the smallest instance directly (base case).& z5 c& U5 h& p
' r. S# q7 P, t6 _/ o Combining the results of smaller instances to solve the larger problem. " O% N1 g& q+ R+ w- i( ` @* f) j: B: E t
Components of a Recursive Function+ Q5 ~/ O1 y- M9 w% L
2 e: z9 R# |5 J- c+ A0 E; t
Base Case: 4 z. W4 x) Z1 N4 g4 h5 S7 N9 J# k# `$ `0 [0 N8 i C1 C4 Z6 n) T
This is the simplest, smallest instance of the problem that can be solved directly without further recursion.) S% R5 v) o; u) p% \0 ~% ^' k
' _& j }* K5 y9 E It acts as the stopping condition to prevent infinite recursion. 6 r# a" y2 r' ]# t/ h2 O4 P0 ?& ~; V; S3 G
Example: In calculating the factorial of a number, the base case is factorial(0) = 1. ) Q0 T& \2 _7 P3 }5 P2 ^" V# x) q1 G% i: p/ {5 ]6 R( [, z
Recursive Case:/ e+ Q& z1 b- z; s0 p8 h3 K# \
+ J G! u; e# H+ B4 D+ T- I
This is where the function calls itself with a smaller or simpler version of the problem. ) @, X8 o9 z; P/ c* {& g2 b' G ; @; l8 }0 U" e- d Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).; w* c- ?8 j8 E0 H2 b7 n
9 K' L- t' p; _9 hExample: Factorial Calculation" i5 o* G7 m& U1 ^* n `
% a# d9 v: Q0 ^4 I( C: _3 U0 F
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:( x( T) m" E" ?* N& S
: x" d! Y0 t; |0 X
Base case: 0! = 1 $ U- A: l7 l i$ s3 `9 N+ ~* z! _* G/ B1 W2 J, V/ ^. ^
Recursive case: n! = n * (n-1)!6 L, h8 ]" d! G! V5 O
. M6 d5 i5 g& e! O9 fHere’s how it looks in code (Python):0 _3 \5 m) W) ^* |" `8 o, K, U
python 5 H) t( G; d* [$ M& H& R6 B6 b9 Y2 E6 _, ~
' x n7 V' T; T9 s, l, pdef factorial(n):% A1 t3 O6 N" r q9 E ]
# Base case ! ^( U4 @. p3 r- R/ m if n == 0:, T9 ]" g8 l4 ?0 t) O+ `* [
return 1' F- r, I; I+ I" l. |
# Recursive case ; M1 Y6 S* R% u+ G! }, V6 J4 u else:8 W- Z% ?+ }4 _( T1 X
return n * factorial(n - 1) # M: K; b: ^$ r/ U% \ , Q( o" a) G; X2 U0 y2 [% w6 h# Example usage5 D. | K B4 {8 \
print(factorial(5)) # Output: 120 5 E+ `4 F8 J `* Y4 N# Q" @/ W; Q. I6 t3 ^
How Recursion Works3 T( i' S4 k% s/ U' d e8 g: L3 U" \
6 x9 _9 Z; N2 ]$ i( W9 }# ]
The function keeps calling itself with smaller inputs until it reaches the base case. 7 z9 W- [ l1 {# Y) S * ]2 x# G# |1 D7 Z Once the base case is reached, the function starts returning values back up the call stack. ; _% k7 p m& G% E I, L4 O, b. L& i: k/ F
These returned values are combined to produce the final result. * R$ N7 G/ T9 c& \. |8 Z6 R5 W0 M * L @' L. s( n) EFor factorial(5):7 h# j9 t; w8 m
* M( k; ?" A% a: u \, G% ] # k( }2 ]0 C% J4 tfactorial(5) = 5 * factorial(4) ( K* p7 O# j$ |; Zfactorial(4) = 4 * factorial(3) # O$ F7 V& z4 ifactorial(3) = 3 * factorial(2) / T3 ~ R8 E, a" X$ dfactorial(2) = 2 * factorial(1)2 @5 B! A5 g' t4 |3 H8 N% e. @" e
factorial(1) = 1 * factorial(0) + \8 h; ~8 _9 M9 o F ?. E6 O) Wfactorial(0) = 1 # Base case% @, n! \) G' U/ g% I% m
9 x2 e% M) g0 f- G% `5 z
Then, the results are combined: - ?( a: A( Y$ W8 J' ?/ ?4 S5 X) u5 v1 b3 J0 m5 h
) R' z9 f: }% q7 Z
factorial(1) = 1 * 1 = 1 ; i0 \% M) F- I, Ofactorial(2) = 2 * 1 = 2 * i9 b6 I; A" [" i1 Pfactorial(3) = 3 * 2 = 6" ^1 U+ m* j/ X6 t# |+ L2 r
factorial(4) = 4 * 6 = 24- I7 C* D" `9 h" i0 }
factorial(5) = 5 * 24 = 120 + t) O' j# A3 M, Y8 x# `8 b" a
Advantages of Recursion& q0 i$ A6 | z7 F0 {
; E& ^- O( f2 {/ b9 V. o# i 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).0 _5 u# X1 T. G2 L% {7 T: b
) `. G& \( H( u
Readability: Recursive code can be more readable and concise compared to iterative solutions. 9 i) a+ b" ?, ?3 U% N* q# e+ w C. Q. M B1 H& X$ f: \2 a6 A
Disadvantages of Recursion 2 _2 N1 {1 w3 ?; {0 H3 [6 r; e % z4 v' b: {9 I0 D8 j 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. ( R4 k# K' q: x- ? 5 n& ]4 g% L/ g Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). ( p$ G' [- ]! h# f8 t) L0 a4 i) C/ b( Z! u- C6 }
When to Use Recursion& Y! k' s* O2 U
& n6 b' ]$ s' ~2 `
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). # j& ~4 H7 l0 q% k3 f# |1 g0 R" D9 A5 _+ Y+ W6 f0 d
Problems with a clear base case and recursive case.3 [6 j5 }3 V1 ?; ^+ [
. q( f9 b" h& g- t' O
Example: Fibonacci Sequence" z8 } C" S' H/ A4 M
/ ^- P3 d5 u2 X/ \8 L
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: 6 A- B, X5 e" x! J5 e! j 6 n- l" K& ~/ [, e( H9 R' b% P; ^, U Base case: fib(0) = 0, fib(1) = 1* a+ I) l+ L! c6 Y2 {: ?
7 H$ J$ g' _1 a! Vpython ( p* X+ r1 {) M m 4 x, v- j* }% }& u ; G. G" w4 G) j! ?/ v+ c( u5 e7 ]: Wdef fibonacci(n):2 y6 y* x8 {6 B8 O, U& M' F
# Base cases7 F: m3 A/ h4 @3 J) a( g4 | P
if n == 0: 3 r7 ^' V9 w# |5 m return 0( t) m6 V8 J& w) }) L
elif n == 1: 5 a/ Q! _" @1 {- R return 1( K" y6 W) Y& g0 Z r
# Recursive case* x- u5 ~7 d0 ~) Q+ E# ?) ~
else:8 E0 ~6 `& }' z
return fibonacci(n - 1) + fibonacci(n - 2) ' C- W" C7 |. l) A. Q4 k) ]4 m7 ] ^: @: _
# Example usage, ~+ S4 s+ p L$ k, p3 U8 s
print(fibonacci(6)) # Output: 8 . P) b8 y0 s# b) b0 C . }( G) ?, e- F2 W# y! lTail Recursion; J: W8 F4 }4 b/ m
: R$ f5 f# e: o- V9 l: i% p! vTail 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 ] D6 P C [+ c : y* S& u- V1 F1 C8 s- {4 cIn 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 现在的开发流程,让一个老同志复习复习,快忘光了。