$ c% a+ V: f P' B/ F, Z 经典示例:计算阶乘9 n* o3 B1 z) p) G3 R- s
python n& G( A& H* |: z0 Q3 R5 }def factorial(n): / T5 V" M3 m; C q if n == 0: # 基线条件- C% k) A7 n2 Z$ v6 y9 ^
return 1( R% q& C7 b; G; s: `
else: # 递归条件 2 A9 w$ a8 E# ^4 I1 D# B/ j+ y3 S" R return n * factorial(n-1) 3 b0 T" ]5 r1 n执行过程(以计算 3! 为例): : l) \7 g/ [* b; M1 [& |+ xfactorial(3): i: D' J9 R5 e" `) m# l2 I" k
3 * factorial(2)$ H- O8 J0 O9 c
3 * (2 * factorial(1))! h# [* o; b7 }7 f; Q
3 * (2 * (1 * factorial(0)))+ l+ n" f1 z4 i' Q$ G4 U9 l3 G
3 * (2 * (1 * 1)) = 6' P. O. K, L* X0 P' R% V, P! Q
' D* D4 j' C; k+ A% i% g! O# H 递归思维要点, @1 ?( R' z }" u* {
1. **信任递归**:假设子问题已经解决,专注当前层逻辑 " A4 J: c( L% g5 Y* a2. **栈结构**:每次调用都会创建新的栈帧(内存空间) 4 F2 |1 {" s; H3. **递推过程**:不断向下分解问题(递) 6 m7 h6 D8 L' U5 S {+ a4. **回溯过程**:组合子问题结果返回(归) / X- L }( p2 y . s3 B& `( Z Z- X" x+ U 注意事项 : X& H! b! }" B) H必须要有终止条件1 m' t# H; h9 w/ E
递归深度过大可能导致栈溢出(Python默认递归深度约1000层), S z3 H1 a' I7 x' }. t. Q+ c2 I! {
某些问题用递归更直观(如树遍历),但效率可能不如迭代: u; K& v0 I; B- b' E2 |3 B5 B
尾递归优化可以提升效率(但Python不支持)2 q; ~, k2 v1 a8 n) V2 H& g
$ D- l$ S' |0 j# p6 D 递归 vs 迭代' C, m( T* j! e
| | 递归 | 迭代 |7 b# [$ ?) Y* c: E! W
|----------|-----------------------------|------------------|/ R" B7 I3 l% d6 z. ^, \/ H. k1 y
| 实现方式 | 函数自调用 | 循环结构 | 2 Q% T: W- N7 _$ }0 j/ w| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 |# f/ p" y- p) K7 f- Y$ `5 l
| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 | 8 t' M2 @" N2 r/ j| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | 3 O- e0 u! H3 N7 q1 ]. m9 r2 b- y
经典递归应用场景 # O1 x8 C9 U6 R/ B6 C" D1. 文件系统遍历(目录树结构)6 C! ]7 f) \ a! Z! |8 i
2. 快速排序/归并排序算法8 R; f' n. z: x& {3 F
3. 汉诺塔问题 3 t6 `0 F: b' P2 V1 X# O4. 二叉树遍历(前序/中序/后序)4 Q& X) p( P6 X* P8 O" d- L
5. 生成所有可能的组合(回溯算法) + U( y: {* W7 w. c- q" K 0 D% l1 l- X) p) `- b试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,4 _7 `1 p; @# a$ X6 C
我推理机的核心算法应该是二叉树遍历的变种。 . L% j9 \- o9 ]1 S另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: ; l0 S1 z# q5 y; u0 LKey Idea of Recursion 4 r Q7 S! }+ v# F2 v5 X* e: v& w- z6 [
A recursive function solves a problem by:" i' D+ w' J0 x; |* i: z( K1 F
3 }0 j2 {& n2 Y; T9 B9 ~. J
Breaking the problem into smaller instances of the same problem.) _( M$ X; S9 s" _( [$ x5 ]
& h2 H; T# V: ^ b: Y! h
Solving the smallest instance directly (base case). * q' r. \9 o5 D0 S9 B 3 W2 R6 s; g9 R9 ], l! C Combining the results of smaller instances to solve the larger problem. ' O( e2 ]8 m9 r8 C) K( _0 W& Q/ v( w+ K w- j9 l% F6 m
Components of a Recursive Function' q @( d; V- d7 N `0 p9 y
9 ^+ Q! ?3 j. f2 P, F
Base Case: 7 j" h* b: k6 ^+ F7 b" r: W$ j
This is the simplest, smallest instance of the problem that can be solved directly without further recursion. # ^" [, H. e- R4 L0 M) \7 J : k0 |0 U3 R# d8 r, O* Y It acts as the stopping condition to prevent infinite recursion.% L* V# O0 S6 k: J9 R: O8 I- D; T
( e9 W7 @9 q% z' X Example: In calculating the factorial of a number, the base case is factorial(0) = 1.+ R" U' A" E0 G. |/ j
4 x. s! i* x% ^+ g' R7 g
Recursive Case:- j4 J& @4 x" R
4 U/ ]% N x0 Z. T! |7 p+ Q This is where the function calls itself with a smaller or simpler version of the problem.% y( ~ Z6 Q1 p
0 T, E0 ~" }. z) s
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).( d! J9 T! E" Y
9 i/ L9 i* y# G/ {: [Example: Factorial Calculation9 o, S7 X& b( D" V: A7 O4 H
@* h: ?1 [$ {3 I CThe 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:: s7 s+ R2 ^: i" p& c) y6 }
) O% M6 l. T; r0 |, F6 b5 C' G5 E6 ~
Base case: 0! = 17 F" i4 N( Y/ w6 k0 ~7 Y
1 i& }" J- d! w4 ], } C Recursive case: n! = n * (n-1)!, y5 e# X/ c) I6 F
# x7 U3 S6 B! J( p; }; Q- N5 h
Here’s how it looks in code (Python):& R& y; `, t( ~
python ' B9 o( z* z( D6 `: h+ { ) C. p! b5 D8 @* l; n; h% z- J
def factorial(n): # E3 S( ~; v+ F- a2 X # Base case+ q7 T' v/ e- D; S8 B: Y
if n == 0:1 l- S- Z7 {6 I* Y5 [0 c* N$ W! U
return 1! X9 L# F% f/ v& X
# Recursive case" L/ a: ]) q0 q) z( ~' Z4 S1 r+ C# Q
else:7 P& x; @% [* @6 W$ v3 Y( J! { G
return n * factorial(n - 1)8 \, O# y! e" z5 Q' V8 T) T
. J$ M$ j' z2 J4 B# Example usage 3 ^" a, u: P' j; [5 Bprint(factorial(5)) # Output: 120* r! f; F$ Z% s" M( Y w q- H
4 z" k4 m& ^& f) D$ D
How Recursion Works' Y( Y* I t6 y
( {: D2 K& l0 ~1 i- R5 n" D- s; ]& A
The function keeps calling itself with smaller inputs until it reaches the base case. 2 s# A( @, S5 P9 R# Z/ |3 S% p% G6 m1 P% e& K8 z
Once the base case is reached, the function starts returning values back up the call stack. * Q' a* J0 `( u& C/ M 8 \! U3 t6 X, `+ d/ l These returned values are combined to produce the final result. 7 _: Z0 s; ?) w& Q& H3 x1 D1 h) Q5 A
For factorial(5):- y/ S9 a* ?5 y% h
3 G( n# F6 I+ c' |4 ]Advantages of Recursion 9 g, h0 Q3 C' k4 G . K9 d0 i" `) j9 W 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). $ c' E+ K4 r6 G3 u' x( U8 F % }% y! P& Q i) ~ Readability: Recursive code can be more readable and concise compared to iterative solutions.4 R) T9 r3 C5 K, L/ d# R
9 V" f6 b; c% E8 `
Disadvantages of Recursion$ ~; \1 K% \; I5 j9 i! L. g
. j! d6 k- d. M l- B% H
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.# r' \. G% Y. V2 d4 g4 a5 E
; s3 x" t5 S7 _# S( `
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).% p" H5 g6 j$ h! n. R3 e" K* R
1 y$ b2 G" k9 V5 M# x5 ^/ n; v! r, l. n
When to Use Recursion W( y9 a/ m# ^ q9 f" P8 m
# ^1 V. _; K, m Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). $ O1 W- v- K. c* H5 l! G* b* w+ z& W* D9 ]# ~ P3 p( z# F
Problems with a clear base case and recursive case. ( |0 ?/ i6 h$ b# Z0 L/ Y R1 n; u$ }+ v8 \: M9 X8 B
Example: Fibonacci Sequence4 A, v; U/ }- k! q8 D
1 t# w/ V" k# M: e$ B( j4 ^ d
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: - M1 b& e" L9 r6 s& [2 v$ p+ T& i# }; ~; g% V$ P- C) c5 @; g. C& f
Base case: fib(0) = 0, fib(1) = 1 / P) H( [+ `! n# S" r1 |$ v. A. p9 v
Recursive case: fib(n) = fib(n-1) + fib(n-2)% I, s) P8 o* |% d+ o, E
I) l6 v+ b8 J' F+ ^+ o6 ^- V
python) c/ O) j0 n% P; k
6 A* s$ e6 Z* {8 C* g5 [7 u
5 I a1 G0 h. P0 {
def fibonacci(n): 9 o& T1 I+ M! J! P$ ~3 h" I # Base cases' }7 b9 H2 x- K% K8 u
if n == 0:9 r4 K$ }$ t' y
return 0 # _0 C$ R, I! N* C m elif n == 1: " Y1 W7 b- F# E: Y5 | return 1 4 n' u4 Z0 N3 J: M # Recursive case . W/ ]9 y/ h) x# T else:; n" K9 B2 G& M# k5 g
return fibonacci(n - 1) + fibonacci(n - 2). f6 s1 K4 Z5 V+ h6 L7 W0 Z
2 N4 r; T0 E- i1 U" Q. m
# Example usage ! n* B3 f6 p9 w& J, k8 u! lprint(fibonacci(6)) # Output: 8 ) Z& e3 G p! x: V$ a4 ^- W * p. k- [7 ~8 o: FTail Recursion 0 ]: ]# H) a) f6 M2 S8 \! s( _' \9 i. { , o* Q4 B8 |( {! e- ?1 YTail 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).& m. Z6 k l* b6 _4 l6 A: q
9 f$ l, j" B0 N7 h6 b
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 现在的开发流程,让一个老同志复习复习,快忘光了。