5 |+ u0 E; x7 D! k/ ~ {% ? 递归 vs 迭代2 w0 L$ k# s# I$ y6 O
| | 递归 | 迭代 |# f. _4 o! A3 G; x& }' X3 @
|----------|-----------------------------|------------------| y2 J5 }2 E( O& _# z| 实现方式 | 函数自调用 | 循环结构 |2 [7 ^, o: d) Z( v- X8 N/ L
| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | 0 r- A( T f2 g) `. N3 I: v| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |" [ X( q& Y" E- y
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | ' r$ l: I2 Y$ J$ c; s9 r; Y" m/ L& O
经典递归应用场景 0 K' `! n0 [% i1. 文件系统遍历(目录树结构) , B4 a' D# ?4 b) u* ~% k2 C- b2. 快速排序/归并排序算法 8 v! g% a5 s; L A+ U3. 汉诺塔问题2 x2 }8 }; a/ R: X8 O1 k
4. 二叉树遍历(前序/中序/后序)) i/ y2 c. k* r4 n. r
5. 生成所有可能的组合(回溯算法) 9 M3 b0 u: g% q) z; K+ ^3 c* o; W3 |" ]7 z
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,+ w8 O0 F+ ]8 u$ O' v: a# n( i1 P
我推理机的核心算法应该是二叉树遍历的变种。( C* t2 U+ B: S
另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:; B! g3 f- F# |$ Q6 S
Key Idea of Recursion' R# p8 c S$ c$ h9 \* m; X
1 W$ I0 l" B4 h/ i6 ]' k6 nA recursive function solves a problem by:# d4 y% t5 N1 d7 u% t
: c; S" w, A# C F. c Breaking the problem into smaller instances of the same problem." p6 p9 c! ]* `' l8 P
3 {1 Q' e" M3 h8 c Solving the smallest instance directly (base case).2 B7 M. ]$ I& j7 j3 R5 M
$ L: W6 T9 m9 `
Combining the results of smaller instances to solve the larger problem./ K8 Y2 n1 f( l; J1 w& {; D
- w& _- X, l8 O. g5 ~( p' l1 ~' ?Components of a Recursive Function ) R6 p$ Y* |, g9 u8 m- p/ K1 v/ V$ {# W3 s
Base Case:4 o) F% R8 B; p# q" \4 P. ?
2 m( O. `6 P. u4 B- A
This is the simplest, smallest instance of the problem that can be solved directly without further recursion. I2 w" D% Y# v
. a' a1 `1 l$ O& p6 i4 V- ] It acts as the stopping condition to prevent infinite recursion. ' w3 g9 t& C" h4 B$ p1 D * U; z( K" Q6 I Example: In calculating the factorial of a number, the base case is factorial(0) = 1.0 _. C; t7 N7 v; l& y
4 P' s) o4 v" Q9 F y) M4 k: m Recursive Case: & C7 f( ^! t. H" {1 Q: E ) Q( L! O, T- X* Q4 P/ c3 o# P/ g This is where the function calls itself with a smaller or simpler version of the problem. . y& y0 G# m0 A; y' ]0 y. ?6 o2 E! D% ?( K# z! B5 h0 p$ c
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). & S; j: ?6 D' x& S( I% T9 s: Y' N) t6 {' X
Example: Factorial Calculation $ d/ { [% Y" d, I* t 2 @* }9 ^4 @ p- i/ lThe 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: 7 T( H0 ^8 @& Y M; \8 E) \4 a& e" E; D; t) r9 p
Base case: 0! = 1 ~; _; _7 ]9 K* | , l+ w8 o8 Z/ Z' s! M8 b Recursive case: n! = n * (n-1)!8 ?' z/ ~( F5 [
* a; C' S$ C9 a7 [% AHere’s how it looks in code (Python): 7 f4 w* b, J! Z( J1 E; f+ Rpython- R! I; E* F: t, e
6 d* \% U: J# L- Q. F! @& }/ D
/ t& F* k5 b7 \: |def factorial(n):) o% f9 c+ ]* K L- \5 M
# Base case- | p9 i8 {/ d
if n == 0: * n, t# ^0 ], g+ E" a1 H. n return 1 7 Y% Z' w) y6 t+ X # Recursive case& y& |3 r2 N( V1 ]) c N
else: 7 I$ n9 }0 t! h0 d return n * factorial(n - 1) ; t; T* e5 S B5 B! R6 i3 i! L* Z4 B P9 ?
# Example usage " C3 l! O* B9 c5 m/ R1 Oprint(factorial(5)) # Output: 120, R% P; p" q F; V6 _
# q2 i% D9 J$ T2 S. p
How Recursion Works 4 _$ E. z$ U' O. @5 w- N2 a" y+ ~- p o: u" ]
The function keeps calling itself with smaller inputs until it reaches the base case., o# q) D K. X0 n1 C% ]
, o3 z: P: z* i# a5 o
Once the base case is reached, the function starts returning values back up the call stack. 4 V8 O% Y, ~( f K# m9 T. j; `# X. U+ z. Y! p( Y
These returned values are combined to produce the final result.' @$ H" s' Y7 G- l9 }
9 e" e! C; B* \# ~For factorial(5): 7 ~$ A! C1 ]0 w% P8 s+ u& m + }+ C M4 k, k7 t3 \( ~8 g. i5 B" V7 V: D
factorial(5) = 5 * factorial(4) * l: F- g0 e; qfactorial(4) = 4 * factorial(3) , Y6 `& w6 S/ \factorial(3) = 3 * factorial(2)7 R0 N5 N8 `( C1 W
factorial(2) = 2 * factorial(1)% _( Z2 K4 U5 k$ |' g4 K
factorial(1) = 1 * factorial(0) 3 U6 j$ A2 B, }# I+ Nfactorial(0) = 1 # Base case: S; ?7 l! b# Q& F
# z1 ?! v4 ~" h5 i7 f1 K
Then, the results are combined:# ~" H: b' i- X# K
; D8 k! }* {0 l& h; | - d+ x5 M; i6 A% L7 W+ s" _9 yfactorial(1) = 1 * 1 = 1% @: c3 r2 O* ~! i6 Y/ o
factorial(2) = 2 * 1 = 26 e: g; r3 x J9 J/ Q p
factorial(3) = 3 * 2 = 6 * s) T9 M, ^! O8 Sfactorial(4) = 4 * 6 = 24 % Q. k/ U. P p: |* `) Tfactorial(5) = 5 * 24 = 120/ G" M8 `# g4 J9 _
. W- Z ~ j4 r3 Q7 }# A5 J
Advantages of Recursion8 U2 U3 W* Y M0 s
3 L- p% U8 S4 R: e. L 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). ! Y' B& p) S% R+ `8 w" ~" {0 {8 Z & w/ K& o! e8 x, t" U/ y9 u! w Readability: Recursive code can be more readable and concise compared to iterative solutions.% v! z/ X' X1 E" @: |% @
' o: C; f$ p+ u) @
Disadvantages of Recursion . J* o6 b4 W0 }& e b$ Z& a$ m* s) `$ Z' e( r4 \5 T% r
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. 0 f2 K! p0 q1 V* y0 }8 T+ y; {; y, Y4 E! z i
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). 8 U+ t) M9 C. {* A0 n5 {- W( ^* o" [+ G% _- r' t9 Q
When to Use Recursion 7 m1 ]- Q8 D- r5 N7 i9 G( k) |+ V2 I, l4 j: `! a. S
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). A2 B8 y- \# }- I: J
3 i* ?+ X W6 _' r Problems with a clear base case and recursive case. F& R6 O) d( g, f6 ?7 j, c5 Z4 ~: F% W5 s% _
Example: Fibonacci Sequence j6 [9 f& i8 _7 u! g6 \5 Y9 u7 _* J; ?5 F$ l7 N- I5 {
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: 7 _6 ?/ W) @8 d# p* @) ^: o, r9 R' P, p* |! O% ]
Base case: fib(0) = 0, fib(1) = 12 J, o1 b! m/ j6 k! R' f" `( h
( ]/ M% Z9 |7 u Recursive case: fib(n) = fib(n-1) + fib(n-2) * A# s; T7 C5 B ]4 x8 ~8 }: I3 L" H$ C$ J' ?4 l# [
python 4 Y# O- Q2 ^6 Y" O% b5 I ^5 S) ?% D4 m
. N7 A0 n. {( C( N
def fibonacci(n): : i& ?1 a( B" }9 f/ Q9 e5 y # Base cases! P! O7 F, B) a9 d: k
if n == 0: * O, N! }) d. `* S% x return 0 ' j) O: C0 k7 L3 k8 H3 O. D. R elif n == 1:- a& B) k! g9 A, J5 O
return 1) l4 [) E" K' x* k3 R9 W
# Recursive case & K4 r; o* M; z: i1 l else:. g7 x. r- M4 ?+ ]# ~1 y
return fibonacci(n - 1) + fibonacci(n - 2)+ I# ^# V; S' w8 u) M1 y6 ?
9 X: `& B) O: \ H b, l8 `# Example usage - k' {4 E" O& \0 g6 tprint(fibonacci(6)) # Output: 88 Z w/ m1 U7 N& z
4 E, Z: y) q, { v- }+ W/ l6 g
Tail Recursion, \) x: v+ p/ h( @' U: a; e
" a. i. p; H' _9 U$ }; T
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).1 C/ _2 Q6 ]4 c- e% @! d# J0 ]
7 S1 i8 g( d* S& D! G
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 现在的开发流程,让一个老同志复习复习,快忘光了。