; D, k6 }4 a# l ?0 [' L/ o2 k递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。 " }4 N/ n: _! l) M 0 F* @+ m4 t3 W1 ~ 关键要素 M6 r0 @4 f4 C4 U& o1. **基线条件(Base Case)** 6 H% M% m9 |- p0 f: K8 o% C' Y - 递归终止的条件,防止无限循环# g8 h+ b# ~0 H; F3 P* w7 L" {# e- S
- 例如:计算阶乘时 n == 0 或 n == 1 时返回 16 D4 |1 U* K; Q1 v' N5 ~! t
( c1 V3 Q$ w9 }- [5 c) Z! j2. **递归条件(Recursive Case)**5 j9 z% _* L# G! y. a) s( T1 x
- 将原问题分解为更小的子问题4 K+ U% _+ R9 m1 ~& R% |2 d5 \+ S+ q
- 例如:n! = n × (n-1)!; b; o: G; |$ e& @
, }+ R+ t/ \* U% ~' ]: [$ o
经典示例:计算阶乘8 ~% l3 g) w5 s& M+ v" N
python8 X+ |6 k* L. @5 _
def factorial(n):6 ~ j0 l8 s3 P# ~1 |& ?6 ]4 c" l
if n == 0: # 基线条件1 l0 p. O i: b' x8 I) l+ h, c1 k
return 11 Z6 H8 g2 E' I$ {, i
else: # 递归条件( n2 N. q/ K( e# c8 @
return n * factorial(n-1) 9 t& @& Q# W& C& U) ]执行过程(以计算 3! 为例): + T L0 _. i) ^factorial(3) + w: v1 g. i: _3 * factorial(2) C* |1 q( i! t3 * (2 * factorial(1)) 2 i2 T% W4 O3 f" Z3 o. P$ k% B$ ~* ?3 * (2 * (1 * factorial(0)))2 K0 U' f- H7 S0 L5 p* o
3 * (2 * (1 * 1)) = 6 . C) `" \: g* G1 [4 ? ! e, h/ K: Z- x1 ]9 F4 j) m 递归思维要点 " _7 G* I5 E" [ Q: B1. **信任递归**:假设子问题已经解决,专注当前层逻辑; U2 x; Z! a! d+ o7 W# M
2. **栈结构**:每次调用都会创建新的栈帧(内存空间)3 s1 v6 d4 Z- }5 a0 }( R
3. **递推过程**:不断向下分解问题(递) ( i: L' B& X! r; Z4. **回溯过程**:组合子问题结果返回(归) 1 S4 s- ^& ]$ W( U0 n# Z4 Y9 ~4 l* V7 Z1 e8 L" D
注意事项, r7 ?* D3 t( }" U
必须要有终止条件 " i3 l, O4 Z. v递归深度过大可能导致栈溢出(Python默认递归深度约1000层)! t6 S |/ k+ ~$ ?4 {+ a
某些问题用递归更直观(如树遍历),但效率可能不如迭代 - I# I; A7 @9 N- Y/ E尾递归优化可以提升效率(但Python不支持) - p' V; m$ r- k0 I( G3 t" @ 5 Y s/ ?* s& _; Z' v u1 I' b7 p 递归 vs 迭代 $ a3 Q( g% q: ]4 e' d* [* x8 B| | 递归 | 迭代 | . x8 G+ R$ C7 r* y|----------|-----------------------------|------------------| 1 w! k4 K/ V" }" k) @8 _0 Y" o| 实现方式 | 函数自调用 | 循环结构 | 4 m7 H. Q2 ]( l9 U. s$ R9 W. @| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | $ t, e# z6 q9 Y& K$ G; C4 o* P; y. o| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |$ d9 e; W* ^) z
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 |" Y* N/ ?' @5 p* x* [) J `& c
7 e2 N( ^9 a" k1 t7 W1 N
经典递归应用场景 ( U" i+ S/ u2 P$ D3 R1. 文件系统遍历(目录树结构)+ i/ P4 B7 Q* f9 R) O
2. 快速排序/归并排序算法, w- q2 U/ M/ q5 g, k* c
3. 汉诺塔问题8 d/ _: W; u) d, P% D3 p* `/ [ H
4. 二叉树遍历(前序/中序/后序) ! y/ J/ b0 x% y v0 E. _: s( S' m5. 生成所有可能的组合(回溯算法): u- F. [1 e9 y( U
/ b. L% K7 S2 ^9 h( p# _试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, 3 P4 Q0 u" k% k; T我推理机的核心算法应该是二叉树遍历的变种。 / M8 }) ^5 I* K2 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: 5 ]& i- L' q) u: @Key Idea of Recursion # n" `* }+ R s+ [ n, ~! y/ z# R * p" e) h7 X9 _7 X& FA recursive function solves a problem by: 2 H3 A3 ?8 |, k4 y5 }% o6 [% N' a# W
Breaking the problem into smaller instances of the same problem. , ~/ p4 P3 R6 f9 d 7 ?/ I, ?, G8 g r. U, l Solving the smallest instance directly (base case)., |) C) T% y, o2 [' t" q& ]
5 p/ L7 O2 h& g* O' _
Combining the results of smaller instances to solve the larger problem.) q9 Y- _8 P2 e8 P* t
* V5 w: g ~6 A z4 l# ]Components of a Recursive Function5 ]3 ^; X: J# ]" K
0 m0 f% [2 }+ Y: i+ }, [ Base Case:: a+ O) s6 n1 a) a) \; \
( J. H" V8 I8 `1 B, z# C
This is the simplest, smallest instance of the problem that can be solved directly without further recursion. 8 W- Y# X5 H; ?( k! E2 i 9 `/ U, y7 R1 | It acts as the stopping condition to prevent infinite recursion. 3 F& e& |# E# j2 e7 }. Z ! T0 t4 k- y# n; t- i Example: In calculating the factorial of a number, the base case is factorial(0) = 1. - B" l7 ^* |8 ~' ~" e( V8 F9 `$ o/ S8 k3 y3 q
Recursive Case: 1 R* ~( ?* c0 z2 u' d* \ + |- _3 Q+ w* F4 W& k N This is where the function calls itself with a smaller or simpler version of the problem.; e J v9 ]3 w# Y# G: {$ h( e" @2 F
0 v, ~) k! l2 E5 U. G+ `" d8 l/ v. ^6 R# n Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1)., X5 C$ ^9 | ?; y# G) k$ A
1 b" F4 k/ E* p: q% cExample: Factorial Calculation6 L: G L5 Z' J9 P
! j$ i8 V! u, X6 ?# IThe 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:! |% d% j8 @9 h8 I* e
v3 s+ T ]0 s! T. R. x0 r5 A \ i" t
Base case: 0! = 1" k! [5 r: _+ o4 x8 o! G
( G2 H8 |9 r6 w% J9 o8 S/ u% p, ?
Recursive case: n! = n * (n-1)! 2 w* @6 e+ `) Z: m 1 b6 f* x9 V0 X2 m" eHere’s how it looks in code (Python):* b" @ ?( a/ `! M! W* ~
python( i. B9 j# \& f; \
# y; }5 Y- R# ]. Y8 l/ y9 S" P. `( }6 G# n! _3 W) @
def factorial(n): : Q* r- ?/ N4 ^ m; D6 J& ]* N$ E8 q0 _ # Base case. b! K2 z( r+ y# [& e5 M! P
if n == 0:! O+ k9 p3 P6 _/ s+ y. U) X
return 1 6 L& y5 X) ]& E# z) w* @6 L6 k # Recursive case% N3 b: S* S# M; V* `4 `
else:* N. ]4 } M. I D
return n * factorial(n - 1) / `8 @' E$ [8 q0 p2 E$ d- ?+ B' M2 h, l) p* f
# Example usage5 u" X$ l; ~4 y
print(factorial(5)) # Output: 1202 | ?1 f! ]6 I1 i, b2 ` \* f" e
# K4 _5 Q; X$ E; o# E" G
How Recursion Works 3 m4 |9 {1 ^1 y- i. U' z 9 V ]6 C8 B0 p- d; w r/ H% l6 r The function keeps calling itself with smaller inputs until it reaches the base case." N# S, e4 S) [# s+ U# P% n. [
: w8 R# u: v2 k3 p# T1 E$ e
Once the base case is reached, the function starts returning values back up the call stack.8 ^& D9 k1 Q( B. e
8 }: g, X' ] a4 E5 B) U' { These returned values are combined to produce the final result. 6 C( H3 i$ g( X9 d) ?. z* T) b, [
For factorial(5):8 j: D! ^0 f! D0 ^$ r$ F4 o+ n/ r
: y! e! w; P/ A8 _6 I, [ 6 l% q, r5 R) L1 i% l1 rfactorial(5) = 5 * factorial(4)! N- N9 {- L% x$ A' o
factorial(4) = 4 * factorial(3) . @6 g1 E# f( _9 I; f4 `9 P% Qfactorial(3) = 3 * factorial(2)) j7 p: Q* e* b" @3 m7 P
factorial(2) = 2 * factorial(1) + Y/ ^2 F) ]+ h$ I9 P& `7 B4 Vfactorial(1) = 1 * factorial(0) / a# @( s; Y8 T2 u, `factorial(0) = 1 # Base case6 P( h1 R9 ^% B% ?3 H
& m8 e2 l+ C- ~ c" @* T4 i7 E
Then, the results are combined: ) P9 \# [ S, M% y% c" J) M6 q% c) [4 E% b1 L& a' y1 L# V
% L' J2 ^3 k9 g4 h
factorial(1) = 1 * 1 = 1/ n& x2 u$ g* W2 D7 |8 Z
factorial(2) = 2 * 1 = 2 7 w8 X `" }; X% G4 G0 S8 Pfactorial(3) = 3 * 2 = 6 ( x+ Z' m8 S8 g+ ]& {factorial(4) = 4 * 6 = 24 5 z( s* X5 K8 S. u" ~factorial(5) = 5 * 24 = 120 4 c. x. b1 r, |) m, N9 |$ b. c/ n ^ A' I r1 m
Advantages of Recursion $ J4 J2 e2 a* F# w* } 3 Z$ f! f$ o1 p 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). ! g* q$ m: E( Y) i' P+ r N/ y& o5 v6 P: i. S6 ]+ t, V Readability: Recursive code can be more readable and concise compared to iterative solutions.1 v7 U0 E$ T1 C* o
" m( m) b+ G/ K6 D" [! ]3 S
Disadvantages of Recursion S' `/ A8 M2 n. X+ ^2 @, k' X1 @" s* P$ F$ X) d; p3 I$ s N" D$ }
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. # N3 n {, b) _% ~4 P+ Y4 X* g$ p1 g% K! G
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).: x" m% A- ?' X/ a- Z2 G
$ v0 M- x0 c/ y4 P4 u5 k# \, mWhen to Use Recursion 9 l2 r M! v0 P) r( b" l - e: S, h* L. D3 H Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).# ~) W; B3 F1 f; Q" d& y1 y' @# w3 t
# y% u0 s6 n8 n8 G) c
Problems with a clear base case and recursive case. 3 `: w; B! e% V \, B% }$ ?' u7 @: ^) @5 Y2 W! X+ ^
Example: Fibonacci Sequence# K0 {) ?; L- c/ X$ x- I! T
7 ~7 ]! P) o" r" q) y/ LThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: 1 B$ }2 ? v$ m- e; Z. k3 d : N3 u( D0 {- `) ^9 ~ Base case: fib(0) = 0, fib(1) = 1( N. I0 H4 {* u* l5 H& \8 x s' P
6 h! D4 w) u P H
Recursive case: fib(n) = fib(n-1) + fib(n-2)8 l5 ]5 t; K7 K& x
0 n, n1 c6 s/ B* B
python , ^* [6 f4 I$ l5 Q" v. E# V; f" @; D) C7 N4 Q) v
) ^" N5 {: Y8 ~
def fibonacci(n): ]% m& b* h7 y. @
# Base cases8 y+ @) j) X& F; z) N) O
if n == 0:( H2 R6 [; v+ D6 E( N
return 0 : E( r/ l0 r3 t; U% J) y# `* R elif n == 1:) S- m# \' _5 x# }/ B
return 1 M' i4 Q6 F! n0 ]
# Recursive case5 F" x# m( u! e/ C
else: 3 ]8 g- n( n1 H1 d9 M$ O4 u. T return fibonacci(n - 1) + fibonacci(n - 2)- X" \4 ~# i5 s5 m# B, |! a
: k, C! U9 s: z7 D# K9 r5 F
# Example usage 9 M8 h+ W. q. L7 Z: g8 Xprint(fibonacci(6)) # Output: 88 Y& y2 F4 a! Q# _
- M+ A) o8 ]* C6 g% ?! F+ n- y4 b
Tail Recursion& \! e% S8 }8 C1 s- e/ r
- K% r1 y/ l* L5 x
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).6 f: [+ L$ _% n6 i7 _) }4 ]
/ ^6 c1 n* g4 F. V' P; B2 v4 z
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 现在的开发流程,让一个老同志复习复习,快忘光了。