, s8 u* m) Z& q) v解释的不错 ) u( R+ T- S/ \ e" F) e; x/ ?0 `( P h8 j0 N& ~4 s
递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。 8 a( Q e5 o5 p- u" ] ^: k% g. n/ y5 z3 ~- f9 m
关键要素( H5 {( w% Y3 y t
1. **基线条件(Base Case)** / B* E9 ^2 q* f8 p - 递归终止的条件,防止无限循环$ s+ b, M4 L q G0 [) b
- 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 _" j |+ N7 P . H& Q. h0 b; l/ G3 `' s2 g2. **递归条件(Recursive Case)**! G2 W$ o }, E. V; B
- 将原问题分解为更小的子问题9 v- G2 ~# e+ C5 q4 r
- 例如:n! = n × (n-1)! % Z9 s( `! D3 {3 L, v) e0 `0 _* z3 ^, l9 ?
经典示例:计算阶乘 3 U1 h; [; N) }python9 b, _( F& w3 `6 o0 i2 O- M3 j
def factorial(n):6 ^% J/ s; w! X( W' m
if n == 0: # 基线条件 : X. a" S1 `5 O return 1 ( w8 ~, \/ ~/ [& c else: # 递归条件" k r% w$ k! M$ l: O7 p
return n * factorial(n-1) - a0 I/ p) `) ~, b( e( v2 `$ V: d$ a执行过程(以计算 3! 为例): . `! Q# o% o* Dfactorial(3) 9 w1 e! Z% t; c; O" |* M+ A3 * factorial(2) / `2 m& Z. L f# A1 }3 * (2 * factorial(1)) * r2 G# j! N1 q5 Z% y3 * (2 * (1 * factorial(0)))8 h0 f) J$ _5 ~
3 * (2 * (1 * 1)) = 6 " g- r2 U4 D" R: t& j , y* E- a" H. ~2 I. r- N 递归思维要点 4 ? L; D$ v+ v+ m1. **信任递归**:假设子问题已经解决,专注当前层逻辑 8 A1 F0 j# |8 t2. **栈结构**:每次调用都会创建新的栈帧(内存空间)1 N4 l; {& k; L; D0 B' [
3. **递推过程**:不断向下分解问题(递) 2 m E: }- }+ S7 ?* d5 j+ R4. **回溯过程**:组合子问题结果返回(归) ; ~. L# g" e2 l4 M: F' p$ K : c7 y2 T4 p5 e; |2 }2 O1 y 注意事项 3 _7 H( V6 U e" P4 P# h必须要有终止条件 4 ?* R5 @# W( p# M* f" F递归深度过大可能导致栈溢出(Python默认递归深度约1000层) 0 r( y, g0 U/ {# R9 {/ G% l某些问题用递归更直观(如树遍历),但效率可能不如迭代 C. m5 o7 W! C6 V
尾递归优化可以提升效率(但Python不支持)) Z0 G& A' F( R+ t& B, R5 X6 U
* b; o/ ^, ^8 S5 ], O- B. B 递归 vs 迭代. E- w% B; E3 }7 d6 @* N, t
| | 递归 | 迭代 | ; @- O. N l3 J: C" w|----------|-----------------------------|------------------|1 `- |5 \ D7 u8 ?4 E
| 实现方式 | 函数自调用 | 循环结构 |) T' x$ c* w# m1 U0 ^* P) h
| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | ; J, |/ t: d' V8 d1 e| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |: B7 H, Y8 s5 n$ C J U
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 |3 m0 D4 G$ J$ k4 I+ J9 V
. Z) H' _& C& ~) K 经典递归应用场景 3 U8 b4 k6 u, z( {- m: s* Q& V' F1. 文件系统遍历(目录树结构) 2 t& K1 D- J. ?1 E8 M( w; R2. 快速排序/归并排序算法: j) P6 C) [) ]4 J* g9 [
3. 汉诺塔问题" b8 t7 h4 ^+ M% [2 W' v" A
4. 二叉树遍历(前序/中序/后序) % E7 V0 Y2 X# n3 B0 i5. 生成所有可能的组合(回溯算法) : V7 T2 E! o$ o: E( w j- n* ^1 O j8 o% |: V! [5 Q6 E
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,- K" z8 F9 B5 j1 E8 M- ~7 c
我推理机的核心算法应该是二叉树遍历的变种。 8 S N9 \( S' b另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:' l) N; W6 T4 A8 }2 N- z+ m% r
Key Idea of Recursion % s2 i- K& l4 y, {/ Z2 B; ?) e5 n' `( |/ ^1 R' N3 ^1 L$ _! D
A recursive function solves a problem by: 2 k3 a% t8 s4 e+ g' Z* [0 c- `# g5 ]% F. @
Breaking the problem into smaller instances of the same problem. 6 M `( @! A0 B6 m4 I" [: ?8 O( _* S" q7 b( n: r' z' t
Solving the smallest instance directly (base case). * J6 m, Y8 x! ^+ S3 I; U5 }5 h; e6 V8 z |
Combining the results of smaller instances to solve the larger problem. 6 N: c, u) N% v2 J( d5 O . X, \; r$ m, Z% ~9 D& h) W |Components of a Recursive Function ' W' P6 j& I# m9 ~& D& e# Q6 j3 t N" _
Base Case:. o( b2 ~) ]/ F) }* ]
+ B$ c, ~7 X* x% o( O This is the simplest, smallest instance of the problem that can be solved directly without further recursion. _( c, @, r& @( G3 A. W/ C' R, [: x
# G( I3 `( a) G
It acts as the stopping condition to prevent infinite recursion. # c6 O: D5 Y5 w9 {9 l5 F % ^8 G% L3 ^& o' D( C Example: In calculating the factorial of a number, the base case is factorial(0) = 1.2 B3 f2 S, S& q+ H9 l3 M
: L8 b4 ?8 s+ p, N: L Recursive Case:/ Z$ p; H y; x, ?& F, \: P
& |( n1 s# h2 n: H9 D1 W This is where the function calls itself with a smaller or simpler version of the problem. 4 N6 y4 w% h9 f# ?2 o2 T- x8 y# i" F# v/ Z' R3 t
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). , S+ M( w1 F& K , m5 h9 u- @+ f) X4 \Example: Factorial Calculation" U% |0 ]8 W& M$ \* H% F
3 N3 E* J" s, h% B' Q# ZThe 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:, V6 r) s& r3 V! Z; o! Z2 _
d- M3 i" U! @6 O0 U
Base case: 0! = 11 I; n- D# g- s: k4 ]
! R/ x9 i1 U3 T, l2 e7 \1 f Recursive case: n! = n * (n-1)! + N. A9 J. ]& k& f3 Z: `' H# U2 X4 N' ?: d1 {
Here’s how it looks in code (Python): 6 |1 M2 Q! @ u# X1 Apython , V4 c {7 K* {6 G2 b, e4 u% K; Y& r. [9 b% z+ S! p4 {3 a& i
) g; G) y) R/ m) S5 g
def factorial(n): 7 J. T% Q' Q7 r) b3 ` # Base case 1 U* A3 _- ^, }9 p3 K2 V if n == 0:+ v: j# F+ g% @# W
return 1/ d2 R% N5 \0 ]
# Recursive case2 O* `! h5 w; q
else: 6 T" u4 s. o7 g" V( o return n * factorial(n - 1)8 ~: X1 I5 B/ Q
" d: B0 J" H- ^& {- D* V' Y+ a
# Example usage - K$ I3 n# Z" i0 Iprint(factorial(5)) # Output: 1206 s- k: M4 { i' \ G8 P
& Z1 X7 g6 s2 C$ R6 Q& W8 h4 |+ }+ xHow Recursion Works ! F9 z* e9 a" _" `5 Z& r + O' j2 D) w5 ^, j) c8 F The function keeps calling itself with smaller inputs until it reaches the base case.! v5 O' b7 `/ E$ v l; W4 F
1 N- e8 P/ y" A) \- x- g g Once the base case is reached, the function starts returning values back up the call stack. ( m% l% D/ j0 o1 g) u4 k* A1 r; @, a a( |' _/ s+ v6 }+ o
These returned values are combined to produce the final result.7 Y& W9 V8 N' R4 g% A0 f, L* |
6 R% v5 ^( u2 k% \9 J" ~0 k
For factorial(5):/ ~7 B" {$ j, Y- N1 \3 x/ h. p
1 p: p+ I P7 m/ a' z& O! L/ J0 V
- F: p* f7 @; `5 r
factorial(5) = 5 * factorial(4)# w; @9 y* V; A0 s4 x; v/ K
factorial(4) = 4 * factorial(3) $ ~: B- {% K# w0 d! K8 Ufactorial(3) = 3 * factorial(2) W: v: s( y: }7 V- h0 |# C4 }
factorial(2) = 2 * factorial(1)& W/ S8 _; y+ B% L5 @' s& q
factorial(1) = 1 * factorial(0)( p. _- t0 T5 x. Z5 [& I: @
factorial(0) = 1 # Base case! t% L) X, l8 Z6 B- M
2 l* j/ V! t5 y4 o% S/ G% Z; E9 N
Then, the results are combined: " A0 S) p7 M/ V! E& u) _1 H/ H* G, \/ n: _' a0 _! T. Y
i% x- p& \( v; ^: [ q
factorial(1) = 1 * 1 = 12 I7 A! c6 N1 `
factorial(2) = 2 * 1 = 2 , H" B9 K7 u) n$ k0 B) lfactorial(3) = 3 * 2 = 6 ) @ [6 S( J) J U8 B) Dfactorial(4) = 4 * 6 = 24* U8 Y A- s/ X8 ?$ E4 Z
factorial(5) = 5 * 24 = 120 + a1 @& v( Q; F( h* T2 B* U. x9 X2 X8 ^" h
Advantages of Recursion. D6 r5 r/ k+ a9 L6 f" S
% K$ s g2 u' O1 q 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).3 M! c. \8 |7 y$ x
' Y4 A: r) G# L1 G F2 @; A Readability: Recursive code can be more readable and concise compared to iterative solutions. ) P# R' S! F7 O, h. { M& w: |$ T" ?3 N: G
Disadvantages of Recursion( _' @1 V! o( w# m
% z2 W' j. ~& q0 V3 U* }- _6 }; `# r5 Y
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. 9 J7 E3 v5 q( l# T' I / Z( x0 L! D g Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). ; F' K K+ g7 ]* F 2 T! E5 X/ C3 K; J& TWhen to Use Recursion* k" A% {9 K. o$ m# m$ [' t( J% r) l+ A
5 q( l2 o- }" l ?- s. @ Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).9 U$ P* u7 ]" M9 i5 X8 J( ]% O0 `
+ @2 U0 b r M9 O
Problems with a clear base case and recursive case. ; x) B6 I* @8 L0 [, l D 9 E& g. R4 \8 M2 ZExample: Fibonacci Sequence4 f( ?' `+ B* G" r* b ^/ q
* z) }2 u& b" m: v) WThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: 7 @% A7 u; |8 v3 m Z$ ^ ( n5 r: A7 B; K8 J- D Base case: fib(0) = 0, fib(1) = 1- l# ^6 k/ H5 v
) X2 n: `# X) {4 A
Recursive case: fib(n) = fib(n-1) + fib(n-2)+ X& x. L5 |; k- r6 z b6 |% x
( V& w7 X# a4 T4 l2 g) E$ ?) B
python ) I3 u& r4 Q' e& Q7 m; m' z $ j* ?- U. ?9 j1 J, |% F/ T5 T, P; s/ j9 m% q
def fibonacci(n):# f# V# t0 t7 u5 E* T# C, D7 H
# Base cases 6 }# C( g+ s3 H2 U; \. }7 v0 c if n == 0: ! J. b0 N7 @/ D- x* S& v return 0 : S- h/ e6 o- i7 j# h elif n == 1:: c7 [' }+ T" \( {! B4 l
return 11 I: q, ?- i- f) X
# Recursive case / R3 x. b, g1 ~0 z else:8 C y& ]. e$ C" m( e
return fibonacci(n - 1) + fibonacci(n - 2) 8 n7 j/ S, X( T1 j3 r7 L0 q# `% {( h7 O6 D L0 b7 z( F. U; d
# Example usage( w+ ~. f' R2 C+ P4 w! F1 }7 {
print(fibonacci(6)) # Output: 86 P" q1 P* q) \0 X- ?8 G+ V; B; i& r$ J
" U6 ^( ?2 x; f; Z& uTail Recursion2 W6 Q4 M" t3 H' A
: @# f6 _' u6 i. _3 ^3 j
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).6 L. e7 @% \. R& e
$ ^" I& T6 i* b" r5 r
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 现在的开发流程,让一个老同志复习复习,快忘光了。