$ G8 `! h, o0 o7 R3 M/ J解释的不错) _8 W s* E0 E/ \8 E; u
& v/ O8 }2 a0 ]2 h0 ]
递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。 0 K: y3 z5 C: W* v, d 6 D5 N4 @; ^; b! ^3 i0 _$ ?2 [- y, h 关键要素 & A6 t* ~' L' f" C7 o! P6 R4 c1. **基线条件(Base Case)** 9 N' Y, T9 y. X5 G - 递归终止的条件,防止无限循环+ B- G, N0 M0 P. B4 J% A2 o$ _
- 例如:计算阶乘时 n == 0 或 n == 1 时返回 1. |4 J4 \$ s' a, v
7 Z1 J2 Q: m; \8 W1 h2. **递归条件(Recursive Case)**+ r5 h* F7 D& q
- 将原问题分解为更小的子问题+ l( \: X }* I3 C9 ~7 u
- 例如:n! = n × (n-1)!7 a a# b m6 j4 o; B* q d' w& j: R8 b
+ B ^. d; K5 I9 a2 u% K+ O2 Q 经典示例:计算阶乘! q6 B0 g' z4 I7 _4 {
python z& a2 i& J: J2 b1 f
def factorial(n): / t4 {# b" e8 @/ H2 j9 o/ A if n == 0: # 基线条件 . I# u6 A5 ~# m1 Y# v2 ] return 1 ' Q. M5 r- O+ \( q0 C# l else: # 递归条件 ) q h! w5 u0 H( j; d return n * factorial(n-1)- ]9 x7 Z2 B5 N- ^7 g; L) v
执行过程(以计算 3! 为例): . n6 g/ z9 H) x5 v* n3 i4 e) Zfactorial(3): t8 r( B0 u& ~' K& b* O
3 * factorial(2) ' B) J7 W/ }3 ^0 K1 p6 s) o6 \3 * (2 * factorial(1))- o0 i$ f; e# N* H
3 * (2 * (1 * factorial(0))) 3 g( U4 w& D9 C' W: [8 n3 * (2 * (1 * 1)) = 6 0 o0 \/ r/ C8 n, P! ~! R+ ^7 ~5 t4 c' g& j* D8 {. W
递归思维要点+ Y8 D% V+ Y! O0 l" O
1. **信任递归**:假设子问题已经解决,专注当前层逻辑6 _; L6 W* p6 @ u/ f2 R
2. **栈结构**:每次调用都会创建新的栈帧(内存空间)+ ~& f# o/ F* v" q8 Y
3. **递推过程**:不断向下分解问题(递) - _( h; E7 Y+ {- k2 q# X' Q4. **回溯过程**:组合子问题结果返回(归) ' t: [7 q0 C0 C) h( n- m. D2 x) h6 q0 J% j% V" A
注意事项3 C6 Y4 i, O" k: _* B2 F7 W- [8 K
必须要有终止条件. k$ x. B1 W' X1 @" C7 V5 L
递归深度过大可能导致栈溢出(Python默认递归深度约1000层): F5 N. [* m9 A& K
某些问题用递归更直观(如树遍历),但效率可能不如迭代8 x9 a3 f' U$ e( T0 i; x$ o
尾递归优化可以提升效率(但Python不支持) $ w) _: Z. T9 c# l7 o, Q1 z) d+ f" e S1 F) E6 |
递归 vs 迭代 6 S) e" x1 x! m7 I6 @) \| | 递归 | 迭代 |, Q3 s' S) }' d/ B
|----------|-----------------------------|------------------| + [0 n7 N- o) f, ?% p8 a| 实现方式 | 函数自调用 | 循环结构 |+ Z$ B8 b- @. G0 g Q8 O5 W
| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 |# z0 r9 u$ Q1 j
| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 | : x D# k2 u, I% \. ~4 s+ u, k| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 |3 U2 O4 q; n+ b
+ M- V2 T$ C$ P4 }7 _0 Z+ L
经典递归应用场景 3 Q/ x2 |" D9 n1. 文件系统遍历(目录树结构)) S2 G; Q2 V( ]9 X$ a+ d G7 c
2. 快速排序/归并排序算法* c# X6 j2 Q: j& J9 h8 {& A; t
3. 汉诺塔问题 ) d2 q2 o7 P0 k+ D4. 二叉树遍历(前序/中序/后序) + m8 x X* B& C2 }4 D) W7 P1 M5. 生成所有可能的组合(回溯算法)2 P8 o6 K& `/ o* Y+ {, m
* O. K, B% `: s4 u" y0 F
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,9 V7 c# V; i, U N5 P) |( [$ \8 u/ G
我推理机的核心算法应该是二叉树遍历的变种。3 l6 A; N+ H8 V$ w4 q
另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:( M/ w3 _0 [% B9 p
Key Idea of Recursion 0 b) Q6 p4 P6 a* c4 K3 u6 D( {' w V" g) ~$ c2 sA recursive function solves a problem by: " `1 i( c3 D; p) K7 x: @( L3 I ~, N: a% h, {
Breaking the problem into smaller instances of the same problem.) w& R: V% l0 f
1 i+ j- W t; }; s, p Solving the smallest instance directly (base case). 7 `: i2 F* s1 W # F3 g; F. [ c J Combining the results of smaller instances to solve the larger problem.: y+ A4 S$ o2 a: Y
9 g6 V: b1 m' `3 S( H8 g! b
Components of a Recursive Function Q" p. @. E) b! [1 a4 `8 [) s
1 X& m- w# l' h; L! x% M Base Case:) P! t8 T% S; {" F2 M. i m0 W
8 l2 |* Q* z$ n" |+ ]0 m This is the simplest, smallest instance of the problem that can be solved directly without further recursion. * K5 c5 j7 `+ S" }$ p7 p1 {$ K6 B/ L+ Z$ i
It acts as the stopping condition to prevent infinite recursion.8 }! P6 O1 P6 B; h4 Z9 ^: f
% g/ q, ?5 x l3 R! j4 ? Example: In calculating the factorial of a number, the base case is factorial(0) = 1. 2 S: w8 D2 [1 B e6 t' {! V7 m9 `) s4 l1 M5 x+ f0 c
Recursive Case:$ @6 m5 e! n; u8 f/ R6 g
: |3 A3 r4 R: p# b( K
This is where the function calls itself with a smaller or simpler version of the problem./ _1 V$ `- k, R: H
3 q& h7 O0 N9 b4 j# v# [3 G
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). : W( m$ z: ]( N/ L+ L2 u( ^. c/ }: G! k7 Y
Example: Factorial Calculation & L5 O, N# I6 e: |* b ' p7 u4 m* G' p: 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:1 R* i! A! ~6 k. A. ?1 A
2 N: ?1 A6 {9 y Base case: 0! = 1 7 O8 V6 `- Y; P+ ^) M- a9 `& A' r3 D) e' F# G ^7 S
Recursive case: n! = n * (n-1)! 2 V8 f4 E5 D. @! q+ q7 r / @. k$ R/ d# W3 z/ Q2 }( J/ ^# }5 oHere’s how it looks in code (Python):* [! n7 j2 W* N( X1 X) R1 N
python7 @8 H2 T' t9 R$ w/ d. G
. i3 A7 v1 |, J& o$ c+ @$ _! N8 i- a; N' @; K
def factorial(n):2 ?) r4 @" j% C; S/ j$ I
# Base case ' [/ w/ z+ U* G+ N( D7 b; x if n == 0:1 \$ N$ p' Y; i: X# g! Q
return 1% b! q3 _$ [- ?$ {: w# U
# Recursive case ' B6 m% O4 r8 B7 W; P0 h& V else: ; `* }7 ^4 I$ g return n * factorial(n - 1) 4 ~6 S8 w3 y) |& S m : g* r8 N _# j U" _& o7 W# Example usage, \, W. ^, N" @# D/ I: y) O
print(factorial(5)) # Output: 120( p, ~) Y7 e9 l, E6 q
3 u: V" L0 q4 E0 f, Y
How Recursion Works1 Q9 S3 ~2 t$ B' F
4 {/ N6 Z* v7 L- j6 c( P The function keeps calling itself with smaller inputs until it reaches the base case. # j x. }! j4 @& A " a9 Q0 }& i; r- X) p& |/ S Once the base case is reached, the function starts returning values back up the call stack. & }" F+ L; C( F; @3 f5 ]+ r% A* G$ {5 }
These returned values are combined to produce the final result.) C3 O+ M: ~2 d% U% K# i$ a M# w
1 d) i. e; e, k5 U! w3 A8 v' B+ {For factorial(5): 2 R+ W) p/ A: { 9 d' d' C( N8 X( N; Y! ]. s0 g7 d$ x8 w* X6 A. o9 ^1 _
factorial(5) = 5 * factorial(4)9 S! P+ }, h0 D. w: y
factorial(4) = 4 * factorial(3) 1 M0 O* r# N& w: \factorial(3) = 3 * factorial(2) % t- ?& a7 q7 P# ^. |factorial(2) = 2 * factorial(1) - m E! V5 o) I2 z8 ~# ufactorial(1) = 1 * factorial(0)/ `5 {* z. y9 w, j! i. H6 _
factorial(0) = 1 # Base case & I1 ]5 v0 K. d9 ^4 p% w" v# }6 R: c3 s$ s$ z
Then, the results are combined: . r; J/ X+ t* V9 C- E 4 y% V. D& G7 ~, z8 h8 G! K % s1 l$ k1 `& {$ l& c% R. v9 w9 }0 afactorial(1) = 1 * 1 = 1& k5 W6 {5 C* E$ X
factorial(2) = 2 * 1 = 2( e1 p+ A' ]1 x
factorial(3) = 3 * 2 = 6 & }3 ^9 l( X* [5 j3 t8 Mfactorial(4) = 4 * 6 = 24 # c$ G! l! i# A( o& _ `factorial(5) = 5 * 24 = 120/ o/ `6 l+ {5 J3 W& ^7 X9 c
3 Y4 x) l5 G q5 J7 t _ H
Advantages of Recursion. `( _2 {: J' H
) N: V7 l1 w6 }" d& 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). . w# @6 A3 S6 D7 @) x 2 _4 q7 s6 O* ^) \8 r; k+ l( R Readability: Recursive code can be more readable and concise compared to iterative solutions. ; U# b4 }1 ~% e% ~8 o . N' f. H7 c7 H# R2 l' HDisadvantages of Recursion 0 \9 Q1 v6 L7 X6 _; W G 3 F$ m* E/ a# w" l* G, 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. J* O8 x6 g5 j3 f6 ^6 q9 d8 i/ T! ~7 e- V# P& Y8 P
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).4 F! {6 r7 e/ V2 j' w
, I; Y% i# e7 K2 S% F/ m* B
When to Use Recursion ) V! F, g4 ~) J) n3 L3 @ X% A* n# a+ N" c1 v Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). 9 I) |+ A5 u' x8 a% P, a" h% a; Y3 s7 A: h; I9 c( B. G
Problems with a clear base case and recursive case. - ?/ S- G, a9 T) ?, d2 l: S) f. F6 Z9 C3 S5 w1 b& d, \4 p
Example: Fibonacci Sequence . j0 ?; K6 F, ?5 Q) y0 v- W( o! n% G6 W7 T
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:' B* E) K6 d+ S4 Y1 ?! o
& ^9 D& {6 ]& g; {8 C6 E! d Base case: fib(0) = 0, fib(1) = 1 2 Q {: V0 B$ b9 f+ p( U5 i% h' x! e( G6 t: p6 C
Recursive case: fib(n) = fib(n-1) + fib(n-2) + Z! ~- J0 H n; I# \1 |- c7 d7 @9 Z4 o9 t& o8 ]
python 7 F! E& R6 J5 w% O$ t3 H3 u$ \; {) |' K1 i
1 w# B' v' U4 q1 Z# |" K V5 l
def fibonacci(n): ' i( _( j8 f% u$ r$ Z! i9 v4 | # Base cases 5 |( P5 {7 @7 T9 Y+ @: ^ if n == 0:3 y" F/ C6 y8 s
return 0- U) r- E( \- o) Z6 d8 U
elif n == 1:. c' B! ^* Y; h9 _
return 1; m( U% a- G) `
# Recursive case) e! b( H' }0 B3 ~+ ?/ Q
else: # s- e$ Z8 R& q1 D- G0 k return fibonacci(n - 1) + fibonacci(n - 2)& z3 [( Z. W T. @
5 _5 P; N* T+ nTail Recursion# x% W, A/ X" l$ k% o
7 F+ G* X E+ F n5 @
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). 3 I Z) @* P2 K+ G: a1 k; M5 L9 p4 k, w# l/ x3 u5 v0 ]. L& v' 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 现在的开发流程,让一个老同志复习复习,快忘光了。