& ]; v* A( p$ J7 e7 A 经典递归应用场景$ D& O4 ^4 z! x1 ^5 E7 i4 B' X! a
1. 文件系统遍历(目录树结构) . I* {) S2 y: Z2. 快速排序/归并排序算法 ' U2 U/ I. B9 @6 {3 T, M3. 汉诺塔问题: b" |$ M& c& K" k! _+ f" o
4. 二叉树遍历(前序/中序/后序) g/ f1 I3 i2 w- K0 U$ p5. 生成所有可能的组合(回溯算法)8 T6 ]0 A2 ^3 l F) c: P" J: C" a. ]
' r2 T; Q( f' k* e0 ?9 u7 m试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,# |: Q- D* |6 O. O q2 h$ Z
我推理机的核心算法应该是二叉树遍历的变种。7 `* K$ h6 @. B4 \2 c! o0 p+ @& [
另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: 3 M0 X. G+ S$ Q7 K0 E2 \- X8 J# [0 sKey Idea of Recursion 6 L c$ X: {+ f: m ( A7 \! k) |8 n+ JA recursive function solves a problem by:: \3 U0 k! F$ `5 R' e( d
* Z4 c, I* A! r9 L5 M
Breaking the problem into smaller instances of the same problem.( Z/ o9 O/ m. r; S1 |+ w
. G7 l. }2 r/ ~% J" B Solving the smallest instance directly (base case). 4 k I% f9 h; D8 ?1 ]5 k( x+ d9 E: Z0 v8 R$ e- j
Combining the results of smaller instances to solve the larger problem. $ {. g) A: {! |$ Y: A* Q- f- x, n& C! d% f6 ?+ j( C
Components of a Recursive Function ! u( L' q# d8 \( Y5 H3 x; H% L8 x+ f* l- i# t [# m/ q& H6 H5 f
Base Case:# f- d) t) p# q$ c' V
# h% r; h$ b. m1 v7 ~" n9 Q# e; ^: @, O% U
This is the simplest, smallest instance of the problem that can be solved directly without further recursion.; i; c: H: k) L: f1 F( N
% X/ [4 q- _' ]# N1 A) q; \ It acts as the stopping condition to prevent infinite recursion. / Y3 l; |4 E# N! N. L$ ]. Q$ ^ o$ g9 l1 B
Example: In calculating the factorial of a number, the base case is factorial(0) = 1.$ h! g) s/ c/ A5 d O5 O
0 c7 M# Q+ B" I Recursive Case: 3 K6 K" b1 _ P, z; Q 0 `# W: { U; s* h! b This is where the function calls itself with a smaller or simpler version of the problem./ i2 y2 d8 d1 R7 I. q. i k
' K0 P8 ~ A) y Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).; R8 C2 {6 \! t+ A& S7 `) p# b
. i( P! }- Z k+ zExample: Factorial Calculation# I' u$ U/ S7 I2 c# a
9 o; }$ N' C' n0 @+ N/ K# |: 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:, A- K" j J* q% K+ r4 g- [
1 N8 z% M+ B b
Base case: 0! = 12 v1 ?+ h) d0 f. X
C' t6 |7 G. |) Q+ L Recursive case: n! = n * (n-1)!. x4 F) Y D8 `/ l, N3 {
- h6 e1 V4 n. ~6 C
Here’s how it looks in code (Python):3 H0 ]+ V" E, ~' O& c! H0 r
python0 @# h$ `* ~# P2 M% l: ]6 {# _ p
+ t2 O! q+ P" j) W2 ] ( X* N. Q" b0 f& a4 [2 u4 w3 Xdef factorial(n):* D+ w& r7 {$ ?6 K+ S/ Q
# Base case ! i* l4 j' k9 w0 ~; V if n == 0: 9 ` {/ n# L4 R- e; [9 j return 13 j; ~% f* S; P( N1 o0 J
# Recursive case 4 Z" r, s# X- @/ T1 X+ W+ P2 q else: , c: t3 d+ ]( Z$ F4 y+ H& T9 ~% H% \ return n * factorial(n - 1) " }8 s4 [3 t% Q* G3 Q) t5 B9 J6 Q3 e. _/ @
# Example usage% Q' P6 \6 B3 t2 o3 l
print(factorial(5)) # Output: 120 - B, e$ s2 k _; ]; H4 p' F- \) t% I8 r
How Recursion Works , M) J4 J! u# A3 H6 H" Q8 J. X' J0 X) n+ U% q5 m# b* u0 q
The function keeps calling itself with smaller inputs until it reaches the base case. ) }3 v4 x2 ?) Y. O* ~" U . t4 i9 @$ Z1 P7 \6 D Once the base case is reached, the function starts returning values back up the call stack.' c; B# J1 P% w3 W/ N! X; p
) t9 x: B; D, e7 N These returned values are combined to produce the final result. 4 y+ n) n% ~7 n) ~8 f8 N9 Z* Z# G' {5 ~
For factorial(5):) n% z { D, `! g& T1 ?+ J
+ j& t6 F# g! C, a ! y6 p. g& I" F$ pfactorial(5) = 5 * factorial(4) . P" R3 j1 M' i$ ~; u2 d" s; B" ?factorial(4) = 4 * factorial(3)* F- A% r2 V, B: d; D
factorial(3) = 3 * factorial(2) / b; a( S* H! c7 bfactorial(2) = 2 * factorial(1)6 Z8 r% C, M2 c# e/ q" h
factorial(1) = 1 * factorial(0) 0 j+ q4 _8 X- d' O* h% u, @factorial(0) = 1 # Base case" A9 N7 [, I) I; }+ V( Z9 I
5 B" N4 E: G/ @) `9 p
Then, the results are combined:7 p, n9 P9 Z# z8 l, C
* W$ N/ z' l a+ t: A) g
! P& y8 r% M3 S4 nAdvantages of Recursion R9 _, }" ` y" u& w 1 E5 n( r6 J7 C4 E2 ^/ R 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). . J& N! E& C, b, d4 u- d2 N# N C9 J, z: s# |4 D
Readability: Recursive code can be more readable and concise compared to iterative solutions.. S# g9 D% s" O5 L, r+ q
2 C* S: U: V) XDisadvantages of Recursion" x/ T; a4 Y8 J2 F/ \
1 S2 _; U$ q* w0 ^% v+ ^7 P
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. 7 d$ B1 i$ A, @0 @$ r2 G- ^, q% U9 b3 g, A/ h' C
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).) v& O, C3 K. R
- q1 t6 b. W8 {When to Use Recursion 0 m6 J- ~1 M' c! K. n8 H9 a" I2 L" \2 Q! M4 m u0 I2 D1 |+ r
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).; s: B |6 K C: S
; Y& ?8 y* j( N4 o. r Problems with a clear base case and recursive case. " u$ ^/ U; Y0 g+ s4 J% J 8 j4 Z9 N% l0 q# b4 g5 aExample: Fibonacci Sequence B( `8 r0 b; m1 D& X
Y+ y2 U- i/ s3 u6 G3 K: eThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: e6 x* n2 }4 P6 w! t, ]* q # Z. F0 |1 q9 k7 t7 x% z* v Base case: fib(0) = 0, fib(1) = 1 $ ?* d% ?7 Z- ]. |' M0 U/ |$ t8 k+ Z
Recursive case: fib(n) = fib(n-1) + fib(n-2). t1 J- n5 f6 [' b* G/ S5 l
" D! Y! G1 U! T) S* n; \! S7 Epython 6 d A8 R. q5 Y/ V- \$ k4 K9 P' ?. U% V- l
" a1 |; h5 v+ x, m. P# Sdef fibonacci(n): $ V3 g) @# P0 r r/ p" v # Base cases- O5 f* o/ ~$ G; D1 A' k; n
if n == 0: & d1 p, g- a/ k, J return 08 Z1 g2 [# H5 n# B" j, j$ Q$ y# P; b
elif n == 1:: P/ B* d6 d& B5 y* ` q o: P1 U
return 1 0 k P3 n- q: e6 l8 l* n # Recursive case# k" p- }1 h+ b( g5 Y/ \
else:9 r4 O) [6 h8 q( [+ h9 F3 i& |
return fibonacci(n - 1) + fibonacci(n - 2) : b0 {- u# R- c) Z- p' d( Q 2 p: O9 N$ \8 p. r) d# Example usage( M$ U. ]" P% M- q
print(fibonacci(6)) # Output: 8 - J& N+ S2 Z! L* w& _2 T* ?! d+ g. Z. b' H
Tail Recursion8 A% y( Q, Q H
{3 B" p6 @: p5 t# K
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).( A) |% e9 k% ?- S0 R# ^
7 f! b: X; v/ G; d
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 现在的开发流程,让一个老同志复习复习,快忘光了。