/ t2 V. y& ?+ u0 B( G 经典递归应用场景4 W+ ~' {/ |) [& v' `1 \& K2 l& N
1. 文件系统遍历(目录树结构) 0 L+ J8 x) z2 u% ?9 d8 W5 Q& r2. 快速排序/归并排序算法 + P( B$ n0 ?: h Q' p% v7 U3. 汉诺塔问题: v# ^2 H: S4 ~4 }- R
4. 二叉树遍历(前序/中序/后序) I) {+ y/ d" W6 D2 o V& G5. 生成所有可能的组合(回溯算法)$ O/ m& p0 x1 ?
9 W8 d8 @& q! L" I3 q
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,9 Z: ?$ S/ B# `# s+ `
我推理机的核心算法应该是二叉树遍历的变种。 1 G3 R9 t5 I4 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:$ W2 L1 }' M, L1 S' n* Q' s
Key Idea of Recursion & a4 f- w2 G( l$ r. A2 s! c- `" |7 o6 {. R6 Z
A recursive function solves a problem by:) G+ T/ @& q M
+ y b6 e% ?$ R# F! Q2 m# v
Breaking the problem into smaller instances of the same problem. + {: x- ~1 t1 T8 |% S0 O5 n. S& n% [' A
Solving the smallest instance directly (base case).5 ?) R: e/ |& n; C
. ^) R( M' o; W9 r Combining the results of smaller instances to solve the larger problem., C, Y6 b7 u$ x- b( Z
+ I/ t3 s& C8 |- k3 W+ r# LComponents of a Recursive Function ) Q5 u, U# H# M7 I% _' L2 H3 T: c0 g9 t
Base Case: ; v5 ~+ ?% E9 \3 B0 ^ 9 x. F4 R' a% J M1 Z This is the simplest, smallest instance of the problem that can be solved directly without further recursion.9 o" c1 v' p1 U* I0 K
1 U4 F4 f( g. F R
It acts as the stopping condition to prevent infinite recursion.* ?8 ~# y2 ?) U6 C- b7 D7 Z0 R" f
: E5 u2 J! s3 Y
Example: In calculating the factorial of a number, the base case is factorial(0) = 1.9 X! @# D, n! b
" B' b, O7 |1 c) I" G
Recursive Case:. A$ C; R( H3 N
& b1 [+ p% |: H7 x
This is where the function calls itself with a smaller or simpler version of the problem.# f3 o/ r/ N- H6 J
4 @# B# \6 c. L8 V- v9 z; s5 Q+ | Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).$ D1 [" ]7 \4 |7 \1 x- B
# x! a5 }0 U; J) ?% Z! h
Example: Factorial Calculation8 _6 ]0 d+ g% l1 I# X
. ]& F- i8 q: V# f! R: T% xThe 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: 9 ]. X$ a, i/ |! @ `' `8 `- B/ L4 j. W% z
Base case: 0! = 1( A% }: x. B, r3 ^/ W% i. Z X
; x5 |( n" p1 \" I0 y, E) w3 [, O Recursive case: n! = n * (n-1)! ( o* I5 R# [* b9 X4 N9 e7 x4 c$ }: i4 ~0 B$ H2 p
Here’s how it looks in code (Python):2 t; m* b) g+ H" l [7 G
python) x, X$ [. c6 ~
( R) z5 P& }2 X, C6 E, o3 X
- r2 b3 i6 W4 U! _% Z7 h8 [1 b9 z( Mdef factorial(n): + a4 P$ O9 j' _# J2 o c- a% _2 x/ o # Base case " w) J3 g" u/ e. Z1 _) e if n == 0: ) Y; K1 a1 W% \6 {, j* Q$ Z7 o$ n return 1 8 @& ?8 B2 K3 s# {% q- g # Recursive case2 c1 }' B. w, y4 @0 ~1 N) D" P
else:: g2 ?0 H4 W& K& k) \, m
return n * factorial(n - 1) ; L2 `# o; ^3 G' E3 K ! p' t% Q A4 p8 h0 r# d# Example usage5 x5 b/ Y$ x; k* V
print(factorial(5)) # Output: 120- y3 m, t$ e, H
- L7 _( n' ?3 }8 [
How Recursion Works: {0 M Q/ C2 h7 g3 @, C0 k& i
. f* r7 B& ]' f/ o The function keeps calling itself with smaller inputs until it reaches the base case. 7 O' t) w0 R5 }- |; x% L4 M # l0 L. z+ [+ X9 j$ F) o Once the base case is reached, the function starts returning values back up the call stack.: F {9 l, `: u
) n5 j. K% U4 q p9 m/ l. _
These returned values are combined to produce the final result. , z$ P1 D1 ?# ~ ! V7 p! b8 _ \* lFor factorial(5): U, O6 B# Z- ~" H5 h* G3 C* _ ! t. a7 T+ O0 ~- G% X3 j0 e & ~. f# W- W$ O2 j$ s* V, Afactorial(5) = 5 * factorial(4)0 N" Y, Z% u. u6 z/ E
factorial(4) = 4 * factorial(3)2 i0 d" W" D1 J2 C5 i: c
factorial(3) = 3 * factorial(2), y _" {! q! E. S
factorial(2) = 2 * factorial(1)1 y' j% u4 r. w1 i, |' F7 ]
factorial(1) = 1 * factorial(0)! d/ {- A; T7 v/ A2 S7 J$ ? }9 X( Y
factorial(0) = 1 # Base case 9 s+ i1 v; o+ E% H: H8 R: o1 D W3 D. v$ P/ }
Then, the results are combined: 1 C1 v$ [; \. r/ U7 _ $ d0 y d9 }+ I0 Q- h: M: U& F k, |
factorial(1) = 1 * 1 = 1 4 x" G7 B2 M2 w+ R( w6 v# I# T5 Kfactorial(2) = 2 * 1 = 2 ( M5 P/ b9 E0 tfactorial(3) = 3 * 2 = 6 , u9 m9 q+ `, rfactorial(4) = 4 * 6 = 24 - Q7 i i5 R* }) R" m0 ?# Kfactorial(5) = 5 * 24 = 120 q, ^ W" b; M0 h1 e, |4 N % X7 E$ P# J/ \% G% JAdvantages of Recursion 8 P; M% E! R$ N; I " i9 D4 T& n+ Q' s$ N 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).* _7 {/ M2 u9 Z! u; W
* f4 m% O% f! ~9 h& e Readability: Recursive code can be more readable and concise compared to iterative solutions.# Q: l8 t: F' L' E6 j& p
4 z5 v* s) J$ FDisadvantages of Recursion . Q$ ]7 y: B; d/ z/ i/ V% u5 }( H: X8 N( V' W2 Z9 m) 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. * G5 K2 o0 x8 i6 y9 w X0 S8 ]) z9 ^ Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). : x$ g) f6 k* ]0 q# m+ \' \* Z$ T8 K- I4 U+ L7 Y/ b
When to Use Recursion $ U0 I V' W2 J' ] { e( s4 Z) I! d7 h' Z, v
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).- _" @+ M/ P2 I2 i; w" d% l! x
" N, ]$ z0 `% S" u5 G7 O* z
Problems with a clear base case and recursive case.& L. y% c+ H9 z' u: H% G g# T; W
5 A3 t6 Y. u' ^" M- e
Example: Fibonacci Sequence " W4 K5 F9 u- D" B/ q" W5 T& @( q1 B% K7 b
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: - x, n# `) P# R& l; C' L ' \) n; i9 C/ W F Base case: fib(0) = 0, fib(1) = 1$ q# Q4 g" [, I2 h3 q: N# Y
+ x! ^9 V4 I/ v5 q* O/ T+ i& n Recursive case: fib(n) = fib(n-1) + fib(n-2). t6 `, Y' p4 ^, q$ y
& |8 c O( Y8 }' o
python6 Y! W+ g. a5 C2 F2 i! H
5 D2 G1 \" S) e- v2 |+ C3 T+ h: \' ?! u9 D9 k3 V
def fibonacci(n):- d( t4 M& W+ Q
# Base cases: k# v9 P' L+ D! b
if n == 0: X# _! y# }/ A$ P! O return 0 . H1 T3 x6 V! n4 B elif n == 1: * v, B/ Z& d) q" {$ `2 U return 1 ! R+ Z. _' j! y2 a+ o # Recursive case * v6 x- o) M% v! l: p4 F8 E7 O2 b else: # a: v R, N" T! u/ G6 p2 f5 n return fibonacci(n - 1) + fibonacci(n - 2)+ @* m4 b( W% p) d5 n6 s/ V# p# X
/ [' A& Y9 M7 g5 t# H, M
# Example usage' R) D2 {$ e6 d; b3 ~3 p- x6 ~3 p q
print(fibonacci(6)) # Output: 8 ( C, D& E" _2 Q ]9 ]' d8 R! M. q, E ]2 g* j
Tail Recursion( T6 I5 B8 |2 A% N
+ B; P% h2 G* Q
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).8 J+ P/ t+ {, H/ O+ T z$ L1 J
& [+ a7 l1 P% z4 D- A* e8 F
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 现在的开发流程,让一个老同志复习复习,快忘光了。