4 I% k |% i. g" } 注意事项 : x' d- [1 @5 g! ~: A: g/ F必须要有终止条件 - z; l i0 L) T* \& I3 M递归深度过大可能导致栈溢出(Python默认递归深度约1000层) $ b1 |: [% o9 J某些问题用递归更直观(如树遍历),但效率可能不如迭代 : { B0 p, I( p, J% E尾递归优化可以提升效率(但Python不支持)! }0 }: z7 f' A$ J- D& ~5 |
# f) G' v* e- e
递归 vs 迭代 ( Y! A% B- g) d" C; _| | 递归 | 迭代 | 4 N* F8 b% ~5 t( d/ z( j, N|----------|-----------------------------|------------------| ! e2 a/ s) q/ W, i| 实现方式 | 函数自调用 | 循环结构 | % P( @/ O* k. E+ `7 k| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | ' P& M6 J9 h& z, g' ^" a| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |4 @4 a4 X! k3 @) h. @! [
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 |6 Q; v; i! z" A8 l% I: N: V
6 O+ [7 }* ]6 c" Y9 @+ Y
经典递归应用场景 ! B [0 ]- M1 r1. 文件系统遍历(目录树结构) $ ~* f; L' M( Z C! U( H9 J0 I2. 快速排序/归并排序算法 $ { J3 R9 Y4 p; h3. 汉诺塔问题. z4 ~1 ~- I/ B. u. V) _! l
4. 二叉树遍历(前序/中序/后序) v( Z, ^- a# ~3 f [* `3 X2 g7 v
5. 生成所有可能的组合(回溯算法) % o: v( j6 {' m9 ^! O/ c0 s % ~/ o. R2 r& @! Q7 P/ T试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, 7 U$ _! M1 H+ D4 _) H+ [我推理机的核心算法应该是二叉树遍历的变种。7 [# u6 H3 t$ x2 m/ [) J" y. n
另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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 A3 ^! P4 u" h% ?$ t! K
Key Idea of Recursion 7 J! K# {2 g# F& `7 A, N* w2 Q - F: k( O0 [# i! P4 W- d2 ?A recursive function solves a problem by:% Z' I" |- K; h7 j5 @7 q
6 x# ~* g0 \2 l5 b O9 y
Breaking the problem into smaller instances of the same problem." Y R+ L) [0 |) Z9 T4 x: z V" x
# w( [$ W, d# _( `& q
Solving the smallest instance directly (base case).; M( g+ G) I6 D/ E# W; @
; ^6 _9 D+ K; B% G3 F
Combining the results of smaller instances to solve the larger problem.6 l; F% G: P6 U
$ m3 y0 x& {. x7 [+ c; }
Components of a Recursive Function / G# A8 S% u) c d' Q7 n: k7 Y+ t , h3 s& V- ?" D7 q Base Case: 2 b" E5 N; [# S+ J 3 l k2 |2 d# [; |. [. E2 [) n9 T n This is the simplest, smallest instance of the problem that can be solved directly without further recursion. - a9 x" a- H0 }/ C3 H* w0 K; I5 B2 H3 K9 E% I* g, a
It acts as the stopping condition to prevent infinite recursion.$ k6 F/ Z9 Y" f! O& d
% M8 v u) U/ M; L
Example: In calculating the factorial of a number, the base case is factorial(0) = 1.0 K( U( A. {9 W6 o
- x' e! Z; D. A+ P' Z Recursive Case: 4 J% V( {% n# W& H! ?: k- ~5 ]6 {* s m
This is where the function calls itself with a smaller or simpler version of the problem. 9 f' `+ M/ Q% ]1 l ?4 I , y. U( f2 F1 ]5 d Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).: z. [8 y4 Q3 f2 A8 [# f; o4 W6 p
0 v% v" V4 n* X9 N9 l' z3 V4 c: i8 w
Example: Factorial Calculation5 J% W4 ^0 ?9 h: F) O7 e
; n7 Q( |' f" \; S3 q3 Z
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: / W p, n$ j2 b7 o) \1 f+ R8 s; B7 V( I2 R1 ]' {- f r- L
Base case: 0! = 1 8 B" {" W( b6 s8 q, [, Q9 i. j # m, C1 b& {, o: i9 b! h w/ o% {0 b Recursive case: n! = n * (n-1)! & r! y% a0 l! r# n: h/ N& t9 d) W* ]5 E8 U& T
Here’s how it looks in code (Python):3 T7 s" D& E0 R. o* J+ T4 U. m5 o7 c
python1 W2 p, P3 T6 I2 Y
, u! j; h# `1 P7 L' K! i
8 X5 i! Y8 C( B, ]
def factorial(n):8 A5 i: V- o! J- M$ d
# Base case # t, z, g# k+ j7 L" r" p if n == 0: # _2 I0 ?4 O2 G5 T return 1( h* _* A: o6 B2 B+ F% y
# Recursive case3 H1 d0 M3 W* V& @' a
else:" ]( T# A3 G R* K8 l) L1 p
return n * factorial(n - 1) , o0 x) f, P# k6 q0 u" U$ X" S! L) |6 p# `5 ?3 d
# Example usage $ e) E0 `) |2 iprint(factorial(5)) # Output: 120- u7 T8 Q* F6 @1 x1 U/ t" G
- {1 ?$ \. [( M2 T2 ^8 q1 eHow Recursion Works' X, D: @5 Y" U6 @! i
. `- J4 T9 m- n; i, I. W, K4 ]
The function keeps calling itself with smaller inputs until it reaches the base case. * |$ ~2 l a6 N+ t 7 X! r/ S9 @6 P+ q Once the base case is reached, the function starts returning values back up the call stack. ; z3 u: R! {" Q D- W |+ B' u: t' E& k# ^* W( a
These returned values are combined to produce the final result. 3 N3 ~' n& c' ]; |4 U0 u; F5 L" x- r r
For factorial(5): " W( p# z/ O) o: ` $ ~; u! a2 Z& G1 h$ a7 S: w5 ] 7 W4 X9 b s+ {9 E+ ?factorial(5) = 5 * factorial(4)+ {# h" a* x$ m, `
factorial(4) = 4 * factorial(3); X! Y* \" f5 [1 `+ c2 A2 P+ F
factorial(3) = 3 * factorial(2) 5 E: _: t3 y1 X+ y/ M( kfactorial(2) = 2 * factorial(1) 1 J# I# I5 W3 t) V$ X, Qfactorial(1) = 1 * factorial(0)9 ?4 v; A2 H! S8 n
factorial(0) = 1 # Base case 8 R/ t0 s5 b* [2 f$ W * K- D" @7 k8 r: x" mThen, the results are combined: 1 M$ h, T4 V* }3 n) J% q- A2 \2 l) o
. t, Q7 |) N; ^7 e
factorial(1) = 1 * 1 = 15 t7 s$ Y @3 u, n0 w5 s/ f6 e
factorial(2) = 2 * 1 = 2 R( I1 G2 I& y! v% L
factorial(3) = 3 * 2 = 6$ z5 t+ z! g i8 ?3 q7 R( ~6 {
factorial(4) = 4 * 6 = 24& _' \. M. U( a
factorial(5) = 5 * 24 = 120 # P& O) o# L* s7 T8 }4 b/ d3 ]; W2 Y/ ]5 S
Advantages of Recursion% A6 L( j. r- u% N
1 |. f$ ? d8 U3 U, Y 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).2 {& F3 M* s! Y# ]5 T$ X) }
9 ~8 C1 {5 y/ {+ X1 b* r6 ? Readability: Recursive code can be more readable and concise compared to iterative solutions. 3 }2 g: E! ^& q8 Z# ~ / S% X, L& b8 ~# iDisadvantages of Recursion/ p. Z, `- {) H. v$ [ |8 @3 a* p: U
# c: f. V& L' Z+ Q. B0 n5 I 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. 4 L# U7 X6 U* ]) Q) E* h; ^" U# h6 G' Q0 w
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization)./ m( _1 @) `; N/ b& E" T
4 P }/ F/ r7 \, ]$ R' Y+ m
When to Use Recursion , \5 g$ Y4 k- ^. @, c, k+ x6 u& b
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). ; s* h( v& J* ~. w+ r1 V& s. G4 h8 V9 D+ l" h5 A
Problems with a clear base case and recursive case. * A# A7 l! q! l$ a, l' {5 Y/ n7 ]+ T; |2 ^
Example: Fibonacci Sequence $ m; P) a7 _, O+ }7 o% ~ 5 b$ h: X. F5 B3 d/ ^6 o6 x+ V- w/ \- yThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: $ Y- x7 j) ^' M8 O. [( O- O# s. [2 m# s! B5 n9 x+ X
Base case: fib(0) = 0, fib(1) = 1 * j) P; i! ~- G% B( i' [' R8 R. ?0 g1 ~; x' U7 f
Recursive case: fib(n) = fib(n-1) + fib(n-2)9 h( n! B8 ~* ]! K$ d* o# x
; _0 Y$ K9 a& h7 x; K$ T6 Xpython6 ]# c) F4 B4 Y3 ]* R
6 y' k0 J+ @2 P% `& j & i4 c7 E9 n3 ~0 W) G8 Gdef fibonacci(n):6 K7 x& y. l& H8 w. ?; W
# Base cases $ z3 t( J. u0 d& x# G4 M) W) V if n == 0: ) O7 x, E$ `1 L- y2 s, O return 0 j, O1 R7 |# h6 r4 ]' [ elif n == 1: 6 j3 w8 h6 f9 g& S& q4 z% J return 1 ) J# v7 l5 r( {. ^ e # Recursive case+ x- R" w$ b) \" }- g8 ]9 N
else: 1 m4 J' K+ w: P* t return fibonacci(n - 1) + fibonacci(n - 2) " P! O4 |. I$ c2 C8 w! _6 M5 x3 O1 f+ o8 C ' E- n5 L; ~) n, `# Example usage, y6 `' U0 N4 ]
print(fibonacci(6)) # Output: 8$ _& u- P' x2 i
/ {8 t6 E7 d( V$ W) JTail 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 P" g4 I& I% S- W8 k: G) n. c. l& I( M/ p w: x
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 现在的开发流程,让一个老同志复习复习,快忘光了。