0 U* w, U+ J( w# [" s! k试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, 8 F# T/ H# L0 c7 l我推理机的核心算法应该是二叉树遍历的变种。 ; J4 w r+ g+ Z) b6 J& j另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:! w, w/ y/ R2 k+ b0 s
Key Idea of Recursion & R: y. g1 r5 X' |9 w 1 ~, ]# O; u3 d9 I9 K; mA recursive function solves a problem by:1 Q& o2 W9 z2 W9 \
- C. [: [6 R' L" C* t& s" H Breaking the problem into smaller instances of the same problem. : D: A( |5 l- K+ e3 ]% x2 c3 d ' J ~- i( j# l! ?% ~) y Solving the smallest instance directly (base case).! n F! _" L$ t
0 |" a' ]! {0 V: u
Combining the results of smaller instances to solve the larger problem.( \1 A! d- {: H# ?
5 |8 p% W1 O6 I$ N7 e& ^8 d
Components of a Recursive Function 6 v1 e- w; T% U3 t% r0 q9 g4 t: p6 U: X+ u3 e7 X
Base Case: 5 k6 a: C3 k6 e$ Y5 p5 v6 P U' |
This is the simplest, smallest instance of the problem that can be solved directly without further recursion.1 V; o8 P; [/ a$ ~$ I
5 |; I) {/ B r8 ~: f" g8 a7 u) I
It acts as the stopping condition to prevent infinite recursion. 6 ]+ ]: p: J8 D- {+ H. P - Q/ x/ a4 ]3 Y8 D( m. } Example: In calculating the factorial of a number, the base case is factorial(0) = 1.- X8 o/ @- m% `; q3 ]. A
- }/ [# }# g7 ]; k
Recursive Case: ) J: u0 K& M6 }, c" D. Y- w5 o) }' c7 ~% K& j
This is where the function calls itself with a smaller or simpler version of the problem. " j' E' k1 ^; i $ h: w, p! B- a G' m3 D/ ?& Z6 j% W; G Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).- l& [& A7 B- i( p; |
! A6 B2 D/ { ]8 v/ VExample: Factorial Calculation) x2 a6 v- t7 k( a5 A
( N' }8 ^! y8 ~' g- R: f, H. C
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: , n& Q1 A2 U$ h; k! E+ P/ E3 B/ F# e
Base case: 0! = 1 : S5 g9 q- g6 `+ K5 b) _, ~& ^+ ^ ! \+ c: i" _2 Y2 a- o& r6 M" A Recursive case: n! = n * (n-1)!2 G& _$ ?" ?* s/ Z# b; a1 }5 K
; Q/ b7 y( j& C/ v& NHere’s how it looks in code (Python):; w1 Z: q! g+ d" m Y" { u: ]
python. y! k+ a0 v2 J/ k% `5 k5 U
9 F9 n& ?1 G( \ r, f0 a, G! O* n) B- o- t- g
def factorial(n): 9 ^* p( |( I' L! n- ` # Base case ! n1 G% e4 A6 k: ~$ s if n == 0: . p4 ]) s3 Z X8 M return 1 4 N0 f3 h3 Z# k+ W) A" r # Recursive case% m/ k5 B, B0 T
else: & f( \& t4 V# a return n * factorial(n - 1) ' q4 G+ R/ K1 Z* G: ] N3 W) O& c: N% | [# y0 ]* E7 Q* e
# Example usage - J: y+ J4 J8 l, F! iprint(factorial(5)) # Output: 120- T9 o: q( J; Y6 g
+ Z" p5 u4 N3 V6 d+ d! k
How Recursion Works " i1 {2 a% ]" _ ~: i# _( _ + h# O$ Q5 K5 x; L1 [* k/ k% d The function keeps calling itself with smaller inputs until it reaches the base case. ! ?7 \/ y. w1 `2 Z( \& {* ~ , W4 O' R" C2 h8 i2 [ Once the base case is reached, the function starts returning values back up the call stack. , g" L$ |. Z7 V6 A ) d' |& g: Q$ d {% `- Y These returned values are combined to produce the final result. & b! M( \, p7 J: V ; p) U- y0 ?& G1 xFor factorial(5):$ m0 l) p; A1 T4 D+ u4 K
/ [+ s, i4 b5 X8 K' |7 y3 e( n- E& L* W" y& I
factorial(5) = 5 * factorial(4)! M3 { s8 u$ B4 ~* f3 n* i
factorial(4) = 4 * factorial(3) ( C. [6 |( L( A5 d3 H4 Y( xfactorial(3) = 3 * factorial(2) % C8 q0 j$ G, R5 \* f9 E. Efactorial(2) = 2 * factorial(1)$ p. q! z7 X! n, N: f( A
factorial(1) = 1 * factorial(0) 6 }+ k! x; P- R# _# y2 afactorial(0) = 1 # Base case $ U; n7 p0 E, k4 Z8 X& D : j& y2 y; M& ~ MThen, the results are combined: , w; D' L$ y. n5 d% L) v! }8 I- Q% B% `9 G( O, D3 F# p
& ?( l& {( t/ k' y% b l. oAdvantages of Recursion6 a. g0 B9 e# k( _* ]0 i
/ A5 ?6 q1 O5 B/ \
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).$ h7 H8 d+ @" X! o1 h7 o) T2 U
; |+ Y% }) q) ?) [" s
Readability: Recursive code can be more readable and concise compared to iterative solutions. / J i, ^8 |# S8 J! z. t! h# ~% _" [9 ~ T. p8 Z# u
Disadvantages of Recursion 4 u- w+ \; E+ e1 `- o5 A {; q " v# f5 k% N" B 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.1 |3 m4 H0 m. J3 |
" S# k% |4 Z0 q! X1 C* x6 d9 l( H
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). 3 ^& q( w! M/ j1 k p, n5 x+ W |2 o, R" {& p& b$ u9 kWhen to Use Recursion1 [1 G1 S( Z' T6 M
T* w0 x2 G4 f! q% A2 p
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).. ?8 u+ g7 Y5 ]! k
) F+ k: r4 {! k Problems with a clear base case and recursive case. 0 R" b, f( k: J% B7 G( y3 I/ o* s& b+ X8 s$ X6 P7 R, M
Example: Fibonacci Sequence! [" j- M* P1 e% D
- T7 T6 B+ [0 p+ L" |The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: 7 {& P( u! K! _# h; r. g+ p! I1 S/ T8 h$ B& N$ t2 g
Base case: fib(0) = 0, fib(1) = 1% R# K# C( {. k- }5 {; O
' { |4 k( J5 f3 Z, x% r Recursive case: fib(n) = fib(n-1) + fib(n-2)' O+ S& p; `! T, G1 X+ F+ `4 Z' D5 ~
@8 a" G$ U, y( Y |; Z
python- q, k4 p+ w$ Q
/ s( ?" ^) h. B, Y9 f
& b9 u8 B z5 r6 N r! jdef fibonacci(n): 7 J, z* b9 Z+ S3 R" @ K # Base cases1 j" d3 z" E# A3 E7 j# S
if n == 0:! [& U* K( ?* Y3 r& C0 M+ i
return 0+ ~, x7 Z/ u6 T0 @& n
elif n == 1: & ?/ X, q6 _8 [- q return 1 9 U1 R) b- A- k4 n8 d e # Recursive case , O4 ^& e( Z# G; z1 e else: 0 w% ]( J. ]0 H7 f* ?4 |) ^ return fibonacci(n - 1) + fibonacci(n - 2)2 g5 M3 {+ q: J# E* D9 i
# z- N5 w8 k+ z6 [* V0 p# Example usage & x+ f# n, a- e, R% Oprint(fibonacci(6)) # Output: 8- p9 Z' G [9 A8 n
1 U3 {0 @8 O( Y4 [4 z! z! ?
Tail Recursion 1 T* P. M- C6 s- g3 k% j 9 d6 w: R; X, Y3 i8 o) CTail 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). " u0 O0 U, Y8 G' I# f/ P! R V/ q5 S9 C) u+ b" k
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 现在的开发流程,让一个老同志复习复习,快忘光了。