% c- j3 Z C: d. v 递归 vs 迭代 ( R2 c# y% a0 D$ a, C1 u6 S/ l| | 递归 | 迭代 | * {* H: e( \1 Z# {9 T|----------|-----------------------------|------------------| / |' ]& l* y$ q7 T| 实现方式 | 函数自调用 | 循环结构 | 0 t) O5 f7 t3 n& t| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 |* c/ C; |! g. X( E& M5 A
| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 | ) x, ]7 n$ n/ ^9 L; G| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | J) C' v% _8 C( S/ s$ F! C# L
, u. V+ ?4 \1 C) w
经典递归应用场景 ) v; r) x: |7 p1. 文件系统遍历(目录树结构)( W2 e x, B0 _1 s+ z
2. 快速排序/归并排序算法2 J( {: V. p: _1 C2 Z
3. 汉诺塔问题 * `1 [- g* S! O4. 二叉树遍历(前序/中序/后序) p! ^8 g# X1 F. Q7 Z$ `3 z$ G0 F
5. 生成所有可能的组合(回溯算法) - z7 }8 A1 ~: A/ i( Y0 v, [( H 6 W, e3 y9 N3 y1 {试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, * F1 F7 Q. p& R( c1 R我推理机的核心算法应该是二叉树遍历的变种。 * Z/ l1 `" C4 }; A4 m4 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:' e/ m; T" a7 R& v9 h+ a4 S$ _
Key Idea of Recursion1 b7 v. D1 M" I
/ M" f# k9 D" }: N ~& S r, y# v0 iA recursive function solves a problem by:- o. Z3 r" } H8 H' o! V
9 e' l2 w$ X& u, q( R Breaking the problem into smaller instances of the same problem. 3 o- E6 V+ e8 |! X1 c& C2 I$ l6 R. h/ U* {
Solving the smallest instance directly (base case). 3 P# c8 v0 v- ?* u ( ^, R: r5 T* C- D Combining the results of smaller instances to solve the larger problem. N7 _, F( j1 Y0 M: N ( g! G# L5 `9 s$ {6 S. ~7 NComponents of a Recursive Function1 E. Q3 q' r, X3 x
* `+ R& Q0 M$ E5 C2 s3 ^
Base Case:8 K7 {& U" ]3 I. p9 |. Q
& t8 b/ U1 E& n& O# X7 T2 e* Z This is the simplest, smallest instance of the problem that can be solved directly without further recursion. 9 R! Z* T" N: g" ^7 s( y4 `/ ]5 A& ]' N% w+ V2 J
It acts as the stopping condition to prevent infinite recursion.. f; |( X O( q% P, ^5 @' u( C
& E* P" U/ ]3 |# z
Example: In calculating the factorial of a number, the base case is factorial(0) = 1.$ ?9 N8 r1 L3 F8 M
m4 U) c" R. a, H! h- e
Recursive Case: 1 q7 t. ^' e3 i( M8 d- A / W% U+ L; f1 T; |$ B# j This is where the function calls itself with a smaller or simpler version of the problem. ; T+ ?2 r2 r' l3 K+ r3 W2 b0 S+ ]# w( s2 o, h) b j7 C. b
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). ; m7 ?! q) P* r" L( o7 B( `0 X% ?. o7 ~0 |/ q3 a' H
Example: Factorial Calculation7 Y# R" f8 v7 N ]* w. @8 J' p
, `" D5 L0 w- \ [6 f
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:, j' Z. I1 N ]8 h. l
3 q Q; ^. s. X0 I1 W. G' T Base case: 0! = 1 3 f, u5 ^* Y, d. U# T/ p2 @ $ I, L- g, s3 t! n' a! @, y Recursive case: n! = n * (n-1)!7 B$ \- w y! j7 L! H7 X$ K
( A" i" ~3 ?3 a* ^) SHere’s how it looks in code (Python):% B y* {- l, `0 n
python+ E+ y% P6 Z% b: U7 G
; b" o) m) c) f5 e4 j* e; y
8 f/ J3 z- }5 t, C) Z! o. W
def factorial(n): 2 }( t# K: w) d8 X/ S, p2 T4 _1 D$ M # Base case 2 [. D5 h6 ]1 i2 T' M! U if n == 0: + I* p; N; M5 r return 1, _4 @ J, w I: R
# Recursive case3 R# l0 O7 t9 w3 \0 p) {
else: % m, p$ T6 H0 t8 G6 x+ A7 M return n * factorial(n - 1) r% k! v% M! j; K" m( N6 z- b' g+ h+ t) e8 x. o: C; S6 c0 f) t- O
# Example usage. H5 }$ U3 T( Y" I" Q
print(factorial(5)) # Output: 120 y/ p- v# S- u+ A
; k& x( o% H; s* {8 V+ e1 P
How Recursion Works: L1 x( r) f! J" E
" v' k- G8 h& D* E( B) c8 r The function keeps calling itself with smaller inputs until it reaches the base case. # Z: l+ n6 {, Q% A5 U) j$ d. ~! ?& ^/ y) W. M6 h1 L3 \
Once the base case is reached, the function starts returning values back up the call stack.4 l- |7 b8 s' U' k/ X: h: r
0 t. L! B0 w, O& m+ J" p$ `) E W3 [ These returned values are combined to produce the final result. + B% r# f- ]) U! O- v, c, \3 [, U; n- A
For factorial(5): # [/ G6 Y- c6 \6 c# F! r7 |; }) F5 y1 h- m, O, Y
. v1 K% d5 p9 b- x% Q& L: g: b6 p
factorial(5) = 5 * factorial(4)3 a% L1 U. S* x3 W& j
factorial(4) = 4 * factorial(3) 8 ^1 W- Q L6 q+ Cfactorial(3) = 3 * factorial(2)+ b5 H0 j! m0 B. C3 F8 s3 n1 W8 f
factorial(2) = 2 * factorial(1) + h4 @0 `1 F$ \factorial(1) = 1 * factorial(0); O) O) m! P7 ]: H
factorial(0) = 1 # Base case9 Q! Q8 i" Y' h* P
# I6 o' @, N/ f2 H" g7 P6 LThen, the results are combined:9 R9 E! b8 _- H
- o; b; [" E1 \8 N3 @) x! i 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).* t- m' U; K9 P# [3 N7 i8 i
! `% n8 @+ b, z/ z$ u9 U9 A Readability: Recursive code can be more readable and concise compared to iterative solutions. 3 X" Q5 T$ c# U- f/ A 7 S# K3 l( O' ]/ `; k0 t* K) ?# _7 ADisadvantages of Recursion 7 ]7 [: z- f% @- t2 e! j ) J+ W2 u# H" ?; P( n 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. * T* l% i; @9 v* z* I+ p t: J1 e- @ M
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).9 I5 B" x. I3 v/ n5 Z# _
9 h6 R) _$ d) L$ ?6 s/ [4 g( {: W
When to Use Recursion . q9 K5 {# s1 E; r$ o0 V& r 5 I' @4 M1 t# F! Y* O/ p7 ? Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). + R" H) D$ t* Z# ~ 4 N: o- n4 G- T, K Problems with a clear base case and recursive case.5 J4 w% o( _: h6 a3 y* t5 Y
- S9 r: M; a. I1 L) P; yExample: Fibonacci Sequence0 l( d3 Z( E4 Z1 }: u8 f( o% W
& S; H2 b2 N/ [
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:$ d6 V- {4 E% j( l$ Z4 F
5 f' c0 |# N/ O) B3 ~5 W
Base case: fib(0) = 0, fib(1) = 1 & ]. h }( J8 K3 r2 ?0 J& J7 ^2 w6 h' M3 E3 b
Recursive case: fib(n) = fib(n-1) + fib(n-2)2 B% Z' T8 ^& F2 i! q* G
' t# X" E; E1 ~* ]7 d7 Zpython ) |' D" Y- U; ?) S 9 A/ O0 H; }. A- Y2 S' b" z9 T" C( [1 S5 ]( ~; J6 k& T
def fibonacci(n):4 m* a$ |1 T! O1 B4 \3 L4 _
# Base cases. O( v/ Y" Q+ I0 z! J/ a
if n == 0: 8 R/ Y! @- o$ u3 ?. N( s* ` return 0& ]" H4 q- L# r K. O- {, Y
elif n == 1:( |, }) G: |8 y) E
return 1 - Q9 s% ^& z1 _+ B. S" [ # Recursive case 9 p! G6 y2 }) q else:# x2 s& e: Q& q! C
return fibonacci(n - 1) + fibonacci(n - 2)3 I3 Y4 N+ M6 }# p2 W- p3 c: a+ n
, r9 x# U9 ^# y5 d. N8 H
# Example usage , G0 u! f7 x% N4 n1 t; Zprint(fibonacci(6)) # Output: 8 , t) @) ]) z$ }" A4 r! u7 V/ ^4 b+ `* w3 F 8 M7 b, K) b6 I' XTail Recursion. b# @$ B- E. S, V! [! z& d
5 `2 V+ v0 w- T2 X" U2 h( ]5 TTail 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).& O; X9 v+ F' f8 m$ \
/ ~% M* i9 ]9 J3 e* L: iIn 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 现在的开发流程,让一个老同志复习复习,快忘光了。