8 |. H0 I1 z+ ? 递归思维要点 # H0 a) b) l7 J1. **信任递归**:假设子问题已经解决,专注当前层逻辑 5 ?7 Z3 I' `& F7 P4 s3 o6 u5 q) n2. **栈结构**:每次调用都会创建新的栈帧(内存空间) " L$ {& T0 D! Q1 X: l( o3. **递推过程**:不断向下分解问题(递): e" w* o! p' p7 k* I1 b) x
4. **回溯过程**:组合子问题结果返回(归) 1 b3 w- u7 z( O! t- i8 l a5 o3 I
注意事项% A0 m6 E2 v' s+ M
必须要有终止条件 # i4 r' t% I) q6 V递归深度过大可能导致栈溢出(Python默认递归深度约1000层) # w2 Q, E) o3 v" w; M3 B2 @7 x- I某些问题用递归更直观(如树遍历),但效率可能不如迭代8 a. p( V5 q! y8 l) d9 o* \. T# u
尾递归优化可以提升效率(但Python不支持)- q4 U# E7 m$ `# u2 ]6 }
# W3 L5 T" T. Q0 t! [3 y 递归 vs 迭代 0 j9 W$ M: k7 D) S| | 递归 | 迭代 |9 P2 g+ g9 N; T& B
|----------|-----------------------------|------------------|& N& Y7 @2 o. p3 |' Y" T, W
| 实现方式 | 函数自调用 | 循环结构 |2 G0 M* i0 c# [$ H5 L# D
| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 |* f6 t9 _9 S5 y; z$ i1 w* T+ v
| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |% k2 B$ a% p5 t/ A- ?
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 |% y- o, `& X6 J" Z5 p: z5 l0 ~: k
5 k* n% q4 ]3 R
经典递归应用场景 ! k) C- Z) e V+ _: H$ K0 M1. 文件系统遍历(目录树结构) 4 s: c7 S# x( h5 D2. 快速排序/归并排序算法" H( V- n5 x5 q. @
3. 汉诺塔问题 V" J. M( U3 A( t1 R
4. 二叉树遍历(前序/中序/后序) 3 j; Q0 ?% ]* s( s6 Z% n; q5. 生成所有可能的组合(回溯算法) ( F! D, J* G4 ]8 Y2 e) b" ]8 ~ O. f/ x
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, % n% ?; d0 ?+ o6 x& X- S我推理机的核心算法应该是二叉树遍历的变种。 : y: ?- G! H& z G另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: # X" f" R% A9 O$ Q% b* n* h" ?! Z* i5 yKey Idea of Recursion . ^$ j, n3 G$ T( @6 k ) o+ d* ~( S8 Q; mA recursive function solves a problem by: $ i2 i. k# W" K. }" L0 o . p1 B0 I: s4 ?# [3 K% ` Breaking the problem into smaller instances of the same problem. & X$ |. T5 l! z& I 0 b+ E8 a2 v/ U1 s& | Solving the smallest instance directly (base case). , a" C, l3 d7 ~1 C4 {: k1 e; S3 J. K+ J: R
Combining the results of smaller instances to solve the larger problem.& E# E! L( B* y K* [$ q
9 y$ Q6 l/ Q& K& q
Components of a Recursive Function5 g' Z" J$ Q4 f
9 a' x* r2 w. A1 b. s" q
Base Case:6 D7 u8 g& W* X; ]. W9 T2 _
! }" P8 }) R q! N
This is the simplest, smallest instance of the problem that can be solved directly without further recursion. , U* P% i/ m9 R6 S' b4 @5 a* a& y! O$ I( F2 d: b
It acts as the stopping condition to prevent infinite recursion. ! k* O$ t4 X3 r% E; r; [% g" ?+ p' P( f, ?; f2 P) O* X* t
Example: In calculating the factorial of a number, the base case is factorial(0) = 1. ' V4 k0 k. P1 G, m, ^, e& ]% g% V& K; l& m5 ?- }, G
Recursive Case:3 {1 q+ R0 ], o) f' y
5 i/ Q" l1 m: v8 O7 Q
This is where the function calls itself with a smaller or simpler version of the problem. 1 o* X( u* S0 B: M1 d( ?" }" {: \
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). 5 S" u& [( f) [) ~& H( G' p" j# v. R% G: F4 z' u
Example: Factorial Calculation L% S }+ q. f! x1 b% g% D) e+ G3 N" e' E
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; V. ^+ |' ?" d0 ~& t
, Y- d1 q$ a! Y# j, d0 S
Base case: 0! = 1 ! D4 W+ l8 B+ ~) V 2 i' @: K5 ^: X1 h Recursive case: n! = n * (n-1)! 5 v% G {: @% R6 v: d( D {$ J1 a) |1 E$ u& o
Here’s how it looks in code (Python): - P( x% n: A# f; u0 `' `python p" W) F2 `3 j" \6 y6 f, [) B
( K( G: v- A5 Q: I5 C8 o$ w4 Q, u2 G8 ^
def factorial(n):1 ]8 m+ g; Y& |1 K' E. z
# Base case( b3 Y9 A4 Y! Y# s r
if n == 0: " u" r$ e( s& o+ `" X return 1 . v2 ~- ] B7 w, s' y! \: }; X # Recursive case* y, q0 `, l* `5 G2 n3 p' E% z+ d7 Y
else:7 k8 N; t0 d& g! K( i$ }, @% o: s
return n * factorial(n - 1) 4 s& G* e4 v, h9 A" I) D0 C% o) i+ E ~* }+ N6 T* T
# Example usage a: A3 i. r# Q6 D& O' @) a& e/ ^print(factorial(5)) # Output: 120 / e" a8 K' e {; Q- X' ]$ L* E6 k; T1 S4 H; N! k$ X7 y
How Recursion Works- C& h8 C5 ], {8 c1 T
1 M3 l, o9 e# ~2 [8 } The function keeps calling itself with smaller inputs until it reaches the base case. . @! R1 w1 o& @" C! e- z 1 q& j* q$ n7 n1 v" p Once the base case is reached, the function starts returning values back up the call stack.' W4 C+ H8 T( e) W( H
8 a+ [! y& C4 [2 S These returned values are combined to produce the final result. , l; c" L* `2 F. n, {" A' i7 q0 R1 C " e9 d# Y7 H9 ~% D6 b( r# B$ dFor factorial(5):7 ?; G# m6 w6 ?0 j( E }2 ^4 G# E
! l& h5 U5 K- B5 y8 x
+ j8 }8 ?8 X/ d' Gfactorial(5) = 5 * factorial(4)4 G7 ~0 u; L% T H' Z' T
factorial(4) = 4 * factorial(3); ^8 Q" M. c0 P: _4 j/ A- j
factorial(3) = 3 * factorial(2) : O, P$ T" n; J6 V: ^factorial(2) = 2 * factorial(1) ( h Z, p, F& @! S0 q/ rfactorial(1) = 1 * factorial(0) z1 y3 D) ]- M* W- `! T( R+ s
factorial(0) = 1 # Base case 8 `; F* w, B$ y9 _$ B: N9 Q; x6 x. b. _
Then, the results are combined:8 s. x; _; }3 J8 g/ I
# n& d$ O2 h$ @- [2 q* s # B& p$ S' o7 C Jfactorial(1) = 1 * 1 = 1 + k/ Z( `0 v5 p ]2 I5 ^* ifactorial(2) = 2 * 1 = 2$ {" X4 E9 M; y2 w' t
factorial(3) = 3 * 2 = 6 D+ h% _: n, \% S9 Lfactorial(4) = 4 * 6 = 24$ n; P w1 `0 p0 m" D8 ]0 r% m
factorial(5) = 5 * 24 = 120 # ]5 ~, g& @4 ^. h ) t3 H* l# J/ c& S+ F! hAdvantages of Recursion ' [" P# }& E( c + E, p3 O, p3 E' w. H' ? 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).7 ]7 a" {* p1 {% g3 {$ D0 W7 S
# S% V5 m# h# p! W5 t6 \
Readability: Recursive code can be more readable and concise compared to iterative solutions. 8 L n8 z0 @, T! G- g& y: c0 H" _8 A) x# i# U) ~- r c: m
Disadvantages of Recursion ; l# E4 B# u _5 V% P1 J, q1 a4 w- u3 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.( c1 T: j1 e. [0 n
5 p- ]# F9 b8 ]$ @8 {6 S7 X5 H
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).$ ?+ F% ^# M% @1 C
" s; ~- F8 Q( GWhen to Use Recursion- U% A8 |2 y+ k0 J; I) l7 s
4 T! a# o% V% d0 M
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). , ^7 q0 p5 |2 k) B$ J' k 7 H7 t9 V) S K0 K Problems with a clear base case and recursive case. " a: \8 m% B& M i0 Z! r# g! }2 m) Y
Example: Fibonacci Sequence& g3 b& o9 I9 X `
1 G' F# Y# v `$ w8 AThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: # i' x4 {$ x9 K$ N& f& M" U . |5 W) {. A/ B1 g5 ~ Base case: fib(0) = 0, fib(1) = 1 2 W) D9 |$ @, s& w5 D * Z% \. J3 `: n Recursive case: fib(n) = fib(n-1) + fib(n-2) ) E% D: e. s6 ^. a) N% M; V) u! h2 A. G8 ?+ s! X" k
python 1 w4 g0 T& K+ r9 ? + d5 G2 |% }9 a" I# d0 m0 h1 n* j 8 ]* X, Z+ {/ v- B1 z( B: wdef fibonacci(n): # W3 a; J& z( Q: Z; p* I! q$ z # Base cases- ]5 c# o+ k& O& }6 @6 ^
if n == 0:$ s/ z+ }- _9 u; K
return 0 ! {2 K: s, h; T6 q4 Y5 @/ [ elif n == 1: ) _# d" ?; P' w. t8 f return 1! s Y5 K T1 j
# Recursive case+ A( H. B4 t% v Y |
else: $ O3 J. `7 W) ^ return fibonacci(n - 1) + fibonacci(n - 2)4 Y) i( S4 ?: \9 u, m$ O$ C
% S9 Q2 q) g; b3 c/ w$ e- G
# Example usage 4 I+ S" J( V) ?. sprint(fibonacci(6)) # Output: 8 1 `3 z+ y" Z8 Y4 k: U4 \; E & g. ~( t% p: a5 H9 p( hTail Recursion ' N% }0 a% Q1 s. E5 ` 8 h/ @' E) j0 w: x3 c' Z" w0 ]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).9 }) H4 F2 r; z" h& e' e
/ h' f* C) J: V: e% |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 现在的开发流程,让一个老同志复习复习,快忘光了。