4 D/ O. B- W; } J 经典递归应用场景" T" D3 Q+ x( g- j
1. 文件系统遍历(目录树结构)- V$ p( m7 o2 p
2. 快速排序/归并排序算法2 J9 b1 f/ G2 H: E8 ^# M
3. 汉诺塔问题 # m8 X& m G, Y4. 二叉树遍历(前序/中序/后序) ! [5 R9 N% i+ {4 l4 n( ?5. 生成所有可能的组合(回溯算法) ( s) i8 _8 s/ i% K/ ^ z0 T3 k. S9 Z* v/ n& g6 C" q B8 g
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,& E# B/ t' i+ m* [
我推理机的核心算法应该是二叉树遍历的变种。 7 r) S0 p. b. z: G: L( V另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: ! ?( o1 R, y% F' }$ `Key Idea of Recursion ( j9 ]- U; `* r }5 }& t2 |( J, J
A recursive function solves a problem by: * W4 w4 I( s- O" K8 y2 K/ \. D' K8 {9 |% J5 E1 w* A k
Breaking the problem into smaller instances of the same problem. ; g* c9 O7 g5 `/ M8 A+ N# L$ x8 }4 S: m' p# v# n5 T
Solving the smallest instance directly (base case). * T2 F9 k% c% I 0 W4 ]& M5 r7 ^$ f Combining the results of smaller instances to solve the larger problem. 7 {6 M9 @" w. S3 o# m* Q$ k( O- x" J3 z" w/ ?
Components of a Recursive Function 8 Y6 a( w6 M' I6 E 0 k( R8 X1 R* S" s, B" ?% F" k H! L Base Case:: d7 ~" j; S* L, c/ S
7 o1 `; R, w% b This is the simplest, smallest instance of the problem that can be solved directly without further recursion., {4 W( k, J$ W! S/ O: H* m
! {- X3 R6 j5 ?# E. Y; j- Z% `4 V It acts as the stopping condition to prevent infinite recursion.0 I# e+ U. D) V6 o/ T" q
( V' G0 ]9 M3 e2 ^6 r O Example: In calculating the factorial of a number, the base case is factorial(0) = 1. # M0 J, n9 u; g # e0 l: H% d7 J* G' ~/ r) _0 h4 A Recursive Case: # I5 h1 ]0 s# _/ p8 G; ~2 n8 Q % b3 r% {/ w* L- M1 n q7 `. ] This is where the function calls itself with a smaller or simpler version of the problem.% j) a8 o/ y7 p" O' Z9 Y4 N) ^
2 n @$ ^ H. z0 q; U2 j% h
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). $ V0 g) P" \3 q& |4 g * ?3 V! B8 `) |6 U+ D$ {Example: Factorial Calculation0 p! J% ?, k; `, B- Z% n2 ^; j- }
; j' R8 x' x' W$ R
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:2 l# D/ k( B1 p. \
3 L# o" t, U" e) E Base case: 0! = 17 C9 }* g% g9 X/ u! c. j
* t3 N& ]) f( E7 d' [: y/ Y
Recursive case: n! = n * (n-1)! 1 M$ g/ R' f1 E9 @4 G" G3 B- f8 W " \8 X7 ]+ u* @% AHere’s how it looks in code (Python):) i e) E% Q* F @6 a* a( O
python . Y2 G% M- h0 q# B& ~" l( {8 u8 G# z6 U; @0 w* F3 N
5 |$ g" |$ u6 O8 {* w, odef factorial(n): 3 U/ ~! E, T4 z6 Z9 ` # Base case2 P T0 v9 q- Z: O3 t
if n == 0:" I2 Y7 a& g( `3 y5 D
return 1 2 s7 U" E3 k: |! p5 j; b0 ] U P # Recursive case 7 k! \1 x- @8 a else: / A6 c+ p9 J/ o. U. u% q" H return n * factorial(n - 1)* S: y0 W- C' {4 Y2 P
; g0 j! m; |3 }$ @* s" z
# Example usage $ |1 c; }7 B1 l- W" cprint(factorial(5)) # Output: 1204 z# l) [) ~# U& |
- s) J6 Y' F& k& {2 X1 e6 hHow Recursion Works0 H1 J1 Z) u" e j x
$ Z7 }( Y- r+ x( u
The function keeps calling itself with smaller inputs until it reaches the base case./ u% m! C. [& l" V- Q
7 N. l* u) H8 R Once the base case is reached, the function starts returning values back up the call stack. V+ j: u: E7 @ P' Y, n. Y
9 T$ ^; m* \7 i
These returned values are combined to produce the final result.9 k( u8 ^8 s# W* [: B
: }/ }+ a L6 J* g: K6 O5 H; i
For factorial(5):) w% E ^- z5 h. D5 d5 k
0 C) J) C% j! b % t2 w" ^$ l; Z8 L0 Ufactorial(5) = 5 * factorial(4)- W! N" r G, b
factorial(4) = 4 * factorial(3) . g# J$ L; f+ m* Sfactorial(3) = 3 * factorial(2)- M1 o& i5 f8 @/ y2 _+ r6 g# J
factorial(2) = 2 * factorial(1) $ J" d7 ]3 ~+ O4 Jfactorial(1) = 1 * factorial(0) : J, L# z- y- j$ z! ifactorial(0) = 1 # Base case. H- M; U: g1 A0 Y* \
9 D, Q7 Q( C0 u3 P5 p5 f
Then, the results are combined:8 h" ?* K! {" ?* W1 Y
$ j% e; Y' p' P l& s
7 @4 F* U3 O* J R/ YAdvantages of Recursion 6 [ R0 ]* G: `: ]/ [7 X5 H ! ~- t/ [2 k! B- F* c9 m 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). 9 j+ q, ?' c1 N# O+ }/ f% R+ q5 _) l6 ^4 h6 ] L. n% y2 c! I
Readability: Recursive code can be more readable and concise compared to iterative solutions.2 ~& _" p# [ j
% h; D/ M" L- s; c4 pDisadvantages of Recursion . f S' Z0 O: }$ m8 E% {- {# N9 f! ?/ x$ H3 F/ ^& `9 U: Q$ v* q
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 [! _, G0 u8 h) }# B- U & y4 \3 J$ Y; y( F/ \1 f Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).0 l2 }& l1 n. Z7 A% `
+ \# a2 V ^$ r$ b; ]
When to Use Recursion * K' N) Y6 @% Y0 N4 ^7 Q: u# X1 ]1 t; ~
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).2 x2 H+ K; [( n
" E9 [8 u0 R, f# n2 x# j
Problems with a clear base case and recursive case. 8 [/ G9 M( M+ M* i! ?! v 0 V+ d' ]/ O: {# N- PExample: Fibonacci Sequence 5 r5 v/ f; `2 k) N r( @5 O1 U5 L3 \5 S2 b# h5 w* b
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: $ i5 y; {) j. R* h3 s3 p " f/ N1 O4 s- C( q Base case: fib(0) = 0, fib(1) = 1 ; U- p: T/ j8 Y- ^. v3 X! ?' K; Q : p* E4 H0 @) ?1 @, F* v1 q Recursive case: fib(n) = fib(n-1) + fib(n-2)# M( t9 t$ c" Z) Q
: z+ k; x8 A0 `# | ?; |def fibonacci(n): * x; ]. V- s! X/ o) { i # Base cases- }6 C. L( p |: ~5 j
if n == 0: . G: ]! m: V0 e8 o return 0* P- N& h0 j2 V5 ?: ]
elif n == 1:. F1 s+ F7 |7 W6 ?/ O* H
return 1 ; W1 J% _7 O: \: p" O8 n # Recursive case 4 z! u6 z8 }4 ]! e else:# P4 u& `/ x2 j. J
return fibonacci(n - 1) + fibonacci(n - 2) : O2 Y) w# A! ?, J, K& \ 0 J* D H* v S) Z0 o# Example usage4 o9 D) m/ v2 a+ f1 k* x) `8 b3 `0 l
print(fibonacci(6)) # Output: 85 w7 O# L& M6 F3 f: i8 ^
, a4 k0 E9 {" P" I4 x1 g2 s
Tail Recursion * |4 Y6 T4 k/ O, ~ % p# P) k# q8 L1 T3 L% l; _; gTail 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 G% j6 Y) R3 Z+ F1 \4 a; Z, e$ `
/ A$ d/ Y" q, j, ]! U1 }9 T
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 现在的开发流程,让一个老同志复习复习,快忘光了。