7 R+ f$ R; J9 u' _/ Y! N+ {5 m# Z9 t/ Y" Z解释的不错0 W. ^1 f1 S2 i9 E
; `% {, A* T" ]4 u X5 Z0 p
递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。 % I# r! y7 N) |9 ?% K# I ( |! C+ A* p; O 关键要素 7 G1 B# p7 A4 y6 J1 j' {! C5 @- {8 ^1. **基线条件(Base Case)**# c, g3 F8 s7 p `' y* d
- 递归终止的条件,防止无限循环( c* j2 }8 h. q# n: d1 ^4 _
- 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 ( k; M% e$ a$ H1 {1 f' L h - `& O8 h7 }* P; h5 ~& l" a; p0 H- e2. **递归条件(Recursive Case)** . S( L. `- Z% |+ T - 将原问题分解为更小的子问题 8 |- R; ~8 ^# n - 例如:n! = n × (n-1)!* i/ d8 a. C1 {0 D: n' j8 `' ^% A
- q# G7 @; t. ?: g 经典示例:计算阶乘( M% f1 g+ z J4 S0 U A/ U
python ! e$ Z: \1 X" u Y9 l5 c5 ~: kdef factorial(n):( [) m0 S1 c: L% D, K f
if n == 0: # 基线条件 : s9 }5 M) H M4 w' R+ a return 1 % h/ ~$ O, ]( S: C, x( X i else: # 递归条件6 P5 b" G. A- K- t% U" [
return n * factorial(n-1)! F1 B4 t) z4 ?7 `4 @
执行过程(以计算 3! 为例):' u3 B2 E0 q4 q( f
factorial(3) + ?/ I+ [0 f& t/ Z; F3 * factorial(2)/ ?4 M8 k. [1 \& {1 z
3 * (2 * factorial(1))# t3 u: X- ~" H2 G. ]# B
3 * (2 * (1 * factorial(0)))7 F1 e# z! e! O
3 * (2 * (1 * 1)) = 6 0 \9 T$ Z+ k0 o! E. J" A Z % ?& C' h# {1 W% b3 @# }! }' _ 递归思维要点 2 a. x2 ^: _& b. E2 C1. **信任递归**:假设子问题已经解决,专注当前层逻辑0 L2 |5 w% H" y& m8 [
2. **栈结构**:每次调用都会创建新的栈帧(内存空间). R A% ^2 t/ d/ E/ x( p% F
3. **递推过程**:不断向下分解问题(递). X) C# Z: t: Y- q1 D+ L/ x
4. **回溯过程**:组合子问题结果返回(归)8 O; j g5 f* m" m* t! p3 t. ]
: S/ R5 U7 R9 J3 w 注意事项 2 A; ^& \, N) O- f$ H" x6 p" m必须要有终止条件 6 o Y8 N- b ]3 M$ f: M9 }$ j递归深度过大可能导致栈溢出(Python默认递归深度约1000层) - y3 \. o8 R5 T( ~, m某些问题用递归更直观(如树遍历),但效率可能不如迭代 8 h# K" J# G6 Q8 R, u尾递归优化可以提升效率(但Python不支持)! f7 D; S. d Y3 }/ {4 v
+ e8 n- [5 f$ r1 c4 t6 T8 v
递归 vs 迭代 , [9 n7 v) S$ ^5 f| | 递归 | 迭代 |" B/ W4 c( v, J; \" G7 ^
|----------|-----------------------------|------------------| 0 y8 {( p1 j. I H7 y| 实现方式 | 函数自调用 | 循环结构 |6 O5 U" ^; G& k8 q: k5 l
| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | 2 g! I! T2 S3 Z# L; @| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 | . f" C* M: K# a3 V# \" `. N| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | ; q. Q- o* Z- ^7 |; i" T+ U8 G/ g; P! ]; h+ ]* B! j0 H
经典递归应用场景 $ b/ `' Q) l; i7 G1. 文件系统遍历(目录树结构)" G; T! y0 w( F# J# h; L
2. 快速排序/归并排序算法: y, @0 d/ V3 V* z
3. 汉诺塔问题) S7 ]4 N: u1 [4 B4 C. e$ e
4. 二叉树遍历(前序/中序/后序)* p% o) U9 d# [* N
5. 生成所有可能的组合(回溯算法)9 W, |: H: u# y' K; A
( v0 I; L/ N$ S. g+ u" e
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,+ O _0 R9 p) W/ F
我推理机的核心算法应该是二叉树遍历的变种。 / S }, m) h) g, s! [, 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: 4 z1 d j& F; S" L: A/ PKey Idea of Recursion 9 ^! y4 u" _% d7 ^' }4 J' j& `- @" t' _/ R4 e- s
A recursive function solves a problem by:# \+ Q4 G& a( q7 \) v
0 s! c: k) i6 J, t3 ~; u, H. t! N
Breaking the problem into smaller instances of the same problem. 5 G, }. p5 l8 L/ I+ O5 q# |" ^* c" E' T# [) N" k/ Y; O/ [1 n
Solving the smallest instance directly (base case).7 U* \7 _" Q1 r3 v
4 b7 o" p" F( b; n$ a
Combining the results of smaller instances to solve the larger problem. ' a7 b8 L6 H3 z# m 3 d& L0 z) u5 XComponents of a Recursive Function + Y: r) w. p2 Z " Y8 ^! ~8 {4 S7 ]4 W Base Case: , t3 w. r2 n( C0 M, i" B7 g/ T6 _ a( g7 d% G4 k
This is the simplest, smallest instance of the problem that can be solved directly without further recursion. ' Q \# z* ~# ?, G6 C& e: ]* U6 R ( R* t: s/ C: C( {; q It acts as the stopping condition to prevent infinite recursion. . z! S7 o# B. G( @( _ , S7 u# w& R- A4 _ K0 E Example: In calculating the factorial of a number, the base case is factorial(0) = 1. & Q/ c$ o( r; U' N/ x3 u" c0 ^' V6 X) \* G# y, {# Q2 t
Recursive Case:. H7 F" M( ]' b( Y
9 ?) f: }/ Z0 R$ i G7 j
This is where the function calls itself with a smaller or simpler version of the problem. 4 \$ z$ b* z, j' ]! ?0 p7 G* h7 ?: E* L" Y! a% k2 v3 k& h
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).4 T4 l2 c* `: r
2 l5 G$ D6 X3 ?4 g1 L8 c/ V+ l- _
Example: Factorial Calculation 1 y2 Z6 t; u# o& K" i8 W0 @. b$ |, ~! m8 _
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:; ?5 k& w) C( W1 Q( f- O# m# @6 C9 d
/ _; J4 A: r i& p: C
Base case: 0! = 1 . c; Z, [6 H! Y 4 y, k- V5 b9 C3 k; t* n Recursive case: n! = n * (n-1)! . v/ i' F9 [. s3 `; c2 ~# Y9 s$ u8 F! t% P; e+ a
Here’s how it looks in code (Python):1 l. ]) N' N; N
python0 f8 c. ~# g5 u3 i& v
4 ?1 g% v0 Q5 z6 m1 Z) o C& P, N8 S; j0 x' I4 d
def factorial(n): % v1 V p. \6 k5 Q; p/ l* V # Base case1 Z2 l; i$ ]4 X& q, b5 v! j
if n == 0:2 K$ u% N* w; n9 t/ [$ p) d
return 1' H d+ ?2 m% g) g" p
# Recursive case 2 y/ ` U( l: Z- l( l) P) \5 D6 q" n else:# J. t' C3 F1 g1 W( I
return n * factorial(n - 1) $ y* G! p7 h. i* U, t$ Y: e! w& b, R0 t& p+ b4 }. u" A7 G& v
# Example usage M! x( f+ j+ ?% H; r
print(factorial(5)) # Output: 120# {+ K$ F/ {, ^/ u1 U: m6 b# f
& U; D2 O. H. h2 E& \; [4 x7 qHow Recursion Works2 `& }* P1 s& T% r; V- b
, t4 X+ y. ?4 l( ?) J# U, y" z! u The function keeps calling itself with smaller inputs until it reaches the base case. " \+ y- P0 ? e& x& @ # \% r. `- z# E$ q Once the base case is reached, the function starts returning values back up the call stack.% B j9 n7 |% W/ G3 F
1 d& m; o: q/ ]
These returned values are combined to produce the final result.* R$ k% T7 u, L( N2 s; n
6 z/ t1 G! I; ]; g. _: }
For factorial(5): : X8 y+ L2 h) }+ d : o5 p& Z. v/ B5 \+ w+ X' _ 2 n. U$ @' E' K! a e) o0 Yfactorial(5) = 5 * factorial(4) 9 |9 ~; C" x9 u! z R$ Q& g- yfactorial(4) = 4 * factorial(3)" S7 V8 K% x! F0 w
factorial(3) = 3 * factorial(2) - A1 k* W/ s3 W- p; i6 s$ |factorial(2) = 2 * factorial(1); X. n9 a3 Z- f. b, c/ P$ o
factorial(1) = 1 * factorial(0)3 [# X8 h2 d. z& C2 C! p
factorial(0) = 1 # Base case/ U- K% N2 M8 H& J/ M
" x" V2 ~% X9 _ t' d9 }
Then, the results are combined:) k% L' _8 d$ `& A# c
# j9 d. f1 P$ d h4 l2 ^9 a ; M5 z2 v* ]& V k' P0 V; n) ]factorial(1) = 1 * 1 = 18 ?7 d% T, g% o! z3 X$ w
factorial(2) = 2 * 1 = 2 3 S( P( D6 m1 F- o, ?* d& F3 h# Wfactorial(3) = 3 * 2 = 6 ' ]3 d) Q# T( F4 x4 lfactorial(4) = 4 * 6 = 24: p2 `$ T t9 [% Y! K
factorial(5) = 5 * 24 = 120 7 [! a4 W7 S& b& H* e* ~ . a9 y% b3 w+ Q3 e/ s1 O; ]$ Q* RAdvantages of Recursion ' S- O4 _( j, P$ X0 i7 H: [. f; w- p8 V; i/ n
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)., A7 z4 ]; c7 b( D% \
, \3 {: k# h$ @, V# z8 H
Readability: Recursive code can be more readable and concise compared to iterative solutions. . T* Q! ~- {1 _, y- h$ V; L6 Y& N* q5 a- v5 j
Disadvantages of Recursion, J; R' y" @% L( h+ W& o
/ r4 g- Y1 |. t5 h0 t# 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. % V/ b4 V1 p! C1 B! b 4 l" w6 w8 T' \, S* R Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).! U; V( }7 x) h
0 ]. W' c! T5 S) x2 E
When to Use Recursion * M4 A( _9 z& L) Z( e. I) p+ _5 U# d [7 O) o- {
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).6 @5 Y9 g' F" p. p- p; l7 k
( \3 Y( H' L$ ?( B0 h Problems with a clear base case and recursive case., P+ q: e& e1 e; i
7 k, L2 D. I; _4 H4 ~The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: ( q8 w2 U1 Z- N- _4 ?/ N0 B( Z! U0 E9 y! p1 y4 [* E! o7 [
Base case: fib(0) = 0, fib(1) = 12 z5 h; A3 |. T) O: y C& O7 k
( k0 {4 U: O6 k2 v: C
Recursive case: fib(n) = fib(n-1) + fib(n-2) # s, f5 v* @# L' ~" B) `0 o1 v " Y H3 h9 W. G) Bpython# G4 w5 i$ R) x
" U) ]+ y+ A. }8 I
& A" A: n1 @5 @def fibonacci(n):/ k. v0 a5 I9 [8 N/ o, B2 w
# Base cases 3 W9 I6 n7 f- u$ r' _) U( b3 `2 [ if n == 0: % M& E8 D0 s+ V" a6 _3 a return 0 - w% R; r0 w, u elif n == 1:+ t0 P( c: M/ X: |7 G% v
return 1$ j/ O& @/ D3 A- B) G7 X, K
# Recursive case; `; _. [* E9 {+ I$ x0 s
else: 7 |8 ^% L% {. u5 s+ e5 i return fibonacci(n - 1) + fibonacci(n - 2) - @8 P. u8 ~+ U( B0 S2 `5 \' E0 u# h) r: D9 x/ ]6 y2 A
# Example usage% x) {+ d1 p# p7 S5 ^
print(fibonacci(6)) # Output: 8 % p, f9 G( r- q: e8 p# r) K2 b+ [: L$ {$ @4 H. C
Tail Recursion 5 E' s! M; F; z3 Q. y- ? - x6 E; o( p) n: 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). ' D1 o8 T& p* z9 b4 h9 z 6 B b: \ J" i8 Y1 jIn 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 现在的开发流程,让一个老同志复习复习,快忘光了。