9 a/ f" S/ H( D2 u 经典递归应用场景, J" {7 h) @; y9 c+ A
1. 文件系统遍历(目录树结构)7 |4 ]9 E7 @+ x3 M5 \9 a3 Z+ L
2. 快速排序/归并排序算法; B9 T5 n9 F$ f( E& L0 M
3. 汉诺塔问题, T$ S2 b# T$ Q; {
4. 二叉树遍历(前序/中序/后序)) T6 y% Q7 Q: Z( C/ ?; `" {
5. 生成所有可能的组合(回溯算法) " g y* @7 e9 c) ?0 |0 {% y1 {/ h. d* I+ Y7 u2 M
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, ; i! x: N0 ^( l我推理机的核心算法应该是二叉树遍历的变种。 / v- c8 ^2 G! p3 G- W另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: . D' U/ Q* I2 X8 S+ |, B5 IKey Idea of Recursion- S$ `$ a7 I. C1 V4 c: {3 {
6 z: K+ w/ a- k& xA recursive function solves a problem by: - A+ N3 x1 A q7 l* w- z( m8 h . j9 Y* W% W! R- N Breaking the problem into smaller instances of the same problem.8 u P/ |) S$ l7 K3 R: j7 j8 s! a
3 ?: N; [" k! h# P6 s( }# r
Solving the smallest instance directly (base case). , ~) m2 W% f3 F6 z' R: ^) r6 G3 P 9 B, n& {4 ~% M" y7 A' p Combining the results of smaller instances to solve the larger problem.& d0 K6 h- E( m( ?6 t
/ t& Z6 Y. W9 u% ~* C0 e9 ?" v% S
Components of a Recursive Function; d) T, ^ Q( ~) r7 K) d. F
: }& p A" |- @- C/ I0 _3 _; r* K Base Case:. q9 n. t$ D$ o0 q0 K! g5 v q
5 b6 Y+ q. S( g$ a9 M
This is the simplest, smallest instance of the problem that can be solved directly without further recursion.' R3 F. i( `" a, Z& ^# ~0 O
0 t: y0 F* X% Q4 k
It acts as the stopping condition to prevent infinite recursion. + P. F' P# ^2 g- k; M& I% S8 z3 F7 ~6 v
Example: In calculating the factorial of a number, the base case is factorial(0) = 1. & F, m1 c, `& J* S r# @% M$ d- I2 k# o " g4 e/ x1 P+ q0 E. r+ I Recursive Case:# a4 Q& N6 Z) @& V% c0 z
% F0 V6 Z5 _* q+ y
This is where the function calls itself with a smaller or simpler version of the problem. ) {& x1 @/ x( R! f1 X/ l+ n$ g8 F, C- A
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). * J' Y3 n" _5 y0 o$ Y8 w8 p% ?' q3 L0 d
Example: Factorial Calculation $ u3 o) I8 H3 C0 H- Z/ e: D5 Y+ Y. Q. d' O- Z$ S( `& T
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:( G! k. }6 L. ^7 \* p
2 [) M8 s# s4 S# r7 F0 O
Base case: 0! = 1 8 w/ H% t# a# ~ c# I( e# T) ^ 5 B5 R g u. d6 D; v" m& Y Recursive case: n! = n * (n-1)!6 F+ R* P! ~: I0 l
' M& ~5 z% r) X& a4 U
Here’s how it looks in code (Python):, U, J& D- l/ h/ d& R
python + n, S& q9 C" e S8 b. Q- ?- f9 ~3 `5 X& N% T$ s" p
; x1 f! l! K% {6 @! i! Vdef factorial(n): $ c1 i' j+ o' ^ # Base case" D1 M M5 z* `. `: f
if n == 0:9 [3 ^9 `6 L: a6 W, D) C
return 1 $ N2 l7 T% X# F # Recursive case1 P9 R$ G$ h( P% T& x1 @) b
else:4 h/ @6 g' ?7 V4 [; G9 Z
return n * factorial(n - 1) 8 @3 M! L; F9 F/ S/ D# y- u% J) D5 ~ K: [5 P. k
# Example usage ; B% J: M3 Y, B e, Bprint(factorial(5)) # Output: 120 ) ?9 h9 x: ^9 H% w5 v1 o! a0 N2 [0 i5 T/ X& G) H' Q
How Recursion Works 3 P6 O! t( D: T9 I% E3 w; h. D+ f1 u6 t8 ?
The function keeps calling itself with smaller inputs until it reaches the base case. P3 W8 y4 D' `$ B& R' H3 ?! @4 a" k8 k
Once the base case is reached, the function starts returning values back up the call stack.( {( B' }: k; N$ }/ u+ v
+ ^& z$ u9 t3 V/ f These returned values are combined to produce the final result. + n1 \5 D- |- v8 k7 H % ^8 [3 S9 f/ Q; WFor factorial(5):* o9 |7 X; K" q- p& S! u) A# [. L
% x/ r* g8 H6 }/ O" S 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). / l5 N- q9 `1 ]0 U5 k2 D N" H) m4 t. ?7 U" l* _
Readability: Recursive code can be more readable and concise compared to iterative solutions. 7 x1 P9 i& `" W* x3 `9 U5 i" k5 D; d* F( F& i+ _
Disadvantages of Recursion; f- B; f- m) K4 O
9 W9 E. b7 d9 A6 Y
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.. P' r+ Y4 P- F7 p6 O7 j
! H+ a- L* g1 J# {# \9 u Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). y5 c9 G( M {
) M# {6 h" n+ C$ tWhen to Use Recursion 8 u4 ^5 w7 k% K$ ^# `' _( @& [* Y$ j+ ?' w* ]5 K) j! Z! O9 e
Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). , V/ h* n3 }* k( q: R( D H# E# \1 \* I% |6 _2 Q Problems with a clear base case and recursive case. + o. g' @7 f3 O' O. _ 0 P! _$ p; M2 F7 c- GExample: Fibonacci Sequence' h; N) v0 h. ]+ W" B2 j
9 `" I* y; i( e1 s. a" OThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:0 b! R$ A: D0 x$ m- Z
; t. [9 h8 v! i- j. P) `* w* n Base case: fib(0) = 0, fib(1) = 1. \- s" H1 h9 A
5 r# j; n t; p" M2 F6 p9 y0 O6 sTail Recursion$ Z5 l4 Q! X" ^% h
. @6 l5 ~8 g, ?
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). 5 |6 h7 } a% s; z7 C9 E- X4 X9 v e' A
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 现在的开发流程,让一个老同志复习复习,快忘光了。