! r7 | V" k# s! b ?5 @6 ^递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。) c% T/ t$ q& a% g, j7 q* T
& W& b; O" K1 n
关键要素 5 X: C+ h, E2 j/ f1. **基线条件(Base Case)**. Q. c, F) j, ?5 L. c5 G7 v
- 递归终止的条件,防止无限循环 : {. b9 e$ x1 X) | - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 D, r+ P& q" {% s& r6 X4 r
% a2 w f; \% M) N
2. **递归条件(Recursive Case)** ! v; Y) X* Z8 N4 V' T( T) w! [ - 将原问题分解为更小的子问题 7 B3 L1 C% @8 {* ^" h - 例如:n! = n × (n-1)!8 k6 `6 a8 E% e( A
5 @" o3 W# _' P5 j$ A
经典示例:计算阶乘 6 S8 w s+ i' e0 M9 q& i7 @python 9 s# F/ F+ c5 u" a! A! e0 Rdef factorial(n):# e1 _, p4 o; o% `4 E% q2 F
if n == 0: # 基线条件. P' k$ ~" q: U/ u" ]: a
return 1/ i" G5 M7 t' k# ~/ I4 W
else: # 递归条件( a/ v: n" G# ?8 W8 @5 Z
return n * factorial(n-1) : Z' @; M/ W' C9 J( _% I7 o [执行过程(以计算 3! 为例): 2 R6 I! k- ^; zfactorial(3)0 w1 k1 G3 T0 Y5 R6 C! F1 @
3 * factorial(2) r- p' k7 M. [ Y( T4 y! k
3 * (2 * factorial(1))6 i- c& }: q& b, Y% V O
3 * (2 * (1 * factorial(0))) - {8 w$ k6 Z9 B' R: i3 * (2 * (1 * 1)) = 6 + f2 Y/ [1 w/ D8 [! D7 a4 L: x \; y- E9 \) R6 b$ l y
递归思维要点 ( P. G0 l- }2 K0 T# o4 ^. x: i4 N7 z1. **信任递归**:假设子问题已经解决,专注当前层逻辑 $ t! b* H" y1 ~) N2. **栈结构**:每次调用都会创建新的栈帧(内存空间)8 }* [( X9 t3 e2 j6 O4 W
3. **递推过程**:不断向下分解问题(递)$ D# n% v% H7 \* _
4. **回溯过程**:组合子问题结果返回(归)& W6 T: ~9 P2 L9 c: g( T C
- I+ O, I' G: |* ~# | 注意事项 7 [0 y# ]! O7 D必须要有终止条件" R6 e) ~! y) l
递归深度过大可能导致栈溢出(Python默认递归深度约1000层)! p' U$ {; q) ?" o V
某些问题用递归更直观(如树遍历),但效率可能不如迭代 1 A( M( Q8 c8 P- @ W3 e# C尾递归优化可以提升效率(但Python不支持) * D, n/ X* q3 Q3 q& N$ Y( a4 y: K3 R3 r( U- J9 f* ~) M* ^& q
递归 vs 迭代3 L" a; r) x; E5 W- |
| | 递归 | 迭代 |( X1 d" g" x6 {1 R% k0 R
|----------|-----------------------------|------------------| " p+ K9 g+ R- Z( j2 v& A Q| 实现方式 | 函数自调用 | 循环结构 |4 m; w: v7 ]" f3 @9 y$ H
| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | ( a' m6 H' N, m3 x( T# _/ H% d| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |; h) a* \% v6 A4 Q: Z% P
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | 8 m. H3 w0 O7 g. ~) t8 w% J . b5 P. Q1 q0 v) k( t# ` 经典递归应用场景 # Z. R$ m d2 ^6 [% M1. 文件系统遍历(目录树结构)1 g J% a- s% c" E7 ~/ k7 B
2. 快速排序/归并排序算法 1 Z' p$ `3 p$ ]$ u$ e3 X2 m3. 汉诺塔问题 1 ~( I5 _4 |6 c6 q2 ~+ ?3 R5 A$ K3 K4. 二叉树遍历(前序/中序/后序) 5 `% G+ E8 I g: e1 x5. 生成所有可能的组合(回溯算法) 7 Y" b# D& F V) ] 2 \/ ~* `9 D% e+ z试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, 6 ^( h. n& }! H. s我推理机的核心算法应该是二叉树遍历的变种。7 H/ F- i( e/ Z) I) a; x) }
另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: P2 N& P8 o/ o# a
Key Idea of Recursion" f, V" I) W; H1 i
9 Q# T. g/ b3 [4 i [
A recursive function solves a problem by: , m% S! D" g- J, h$ J) c2 T7 U4 _ y1 N8 e; p
Breaking the problem into smaller instances of the same problem.9 c% v" Y: H" v8 }/ V& t0 H \; M
6 r. z/ q8 a* p T+ O Solving the smallest instance directly (base case).4 ^5 \5 W5 X% A9 f3 R
6 A5 _! a3 a/ ^7 H Combining the results of smaller instances to solve the larger problem. 5 `/ |6 {! R( {6 h ( Q' J& G7 R6 g# HComponents of a Recursive Function 4 \& A( l9 O8 C# F6 ^0 k8 d+ P6 h t ( {0 T- a, |3 r5 A( K3 {3 W1 b. T Base Case:1 g3 X2 p4 q6 @/ b
& H% v( C# t5 K6 Y7 F
This is the simplest, smallest instance of the problem that can be solved directly without further recursion., D8 J6 { j0 |1 {& _
; ?6 \; k- _7 L+ n7 C
It acts as the stopping condition to prevent infinite recursion. 3 t$ D) q1 j1 e% w& m5 F% r. z! a1 g0 W+ z8 V7 i
Example: In calculating the factorial of a number, the base case is factorial(0) = 1. 1 M" \3 z7 c5 [/ P6 Q! p % H i7 a1 w' X1 o Recursive Case:0 g1 O1 N& U: n' e |
" d/ R+ G6 R# \6 E; \- \ This is where the function calls itself with a smaller or simpler version of the problem.$ t" }) S, W, N
% u$ H& t$ l7 d) _( M Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). 3 M# h+ _5 ` @- `6 U! M! M& N) b+ V# A' D4 h2 S# o$ s8 p- {) L# A
Example: Factorial Calculation ' Y4 `, x: P4 Z2 F7 O6 T * N( s' e+ u% [1 h, H/ 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:3 O* _5 m# b, e5 o/ F' A
+ { m+ i& w( E, D& E$ B3 ?1 ~
Base case: 0! = 1 , e4 M: @7 Q: Q5 {5 \! j* q0 i6 X , p8 m0 A$ {0 }9 U' c1 D' ^( X Recursive case: n! = n * (n-1)! % ?( c8 v/ W: }" s; F0 A8 f2 S4 N4 X5 m I- X" E
Here’s how it looks in code (Python): ( r# r) z* \6 S) j# G- q1 [python% n. d# ]2 p+ N. ?7 K+ N. g
( Y7 j3 F7 m6 I6 b
1 `. C" k9 D" W7 w& o1 N
def factorial(n): 8 P$ p2 h1 b: Q # Base case ( m3 @/ T$ Y' \& ` if n == 0:: S. m- t6 A' ^! X9 g* w. Y
return 1 % S" `0 D6 L8 D2 Q! v, {( N# Q # Recursive case- k" B$ O% C2 W
else:+ B' ^# C4 j9 f* k" J# V# |
return n * factorial(n - 1) 5 j0 M" a" H9 n* E: c# L6 N2 s) c2 u6 k3 ^ 8 }3 d/ w/ J6 ~) U: f# Example usage/ Q: W5 k* Q+ z8 f4 R
print(factorial(5)) # Output: 120, ^: c9 P( B9 j
1 E, G' D0 Y- j( I4 d
How Recursion Works : I6 s4 h! x5 z. @5 V, u3 P * |. N+ c# _& E; A& L The function keeps calling itself with smaller inputs until it reaches the base case. & h. R, T- g$ f! H' }* `0 Y1 l+ M& A* ?: B: W0 s) Y
Once the base case is reached, the function starts returning values back up the call stack. C, ^) S/ P- r3 c1 H, R1 v
: f% s0 R7 I+ v' k# q5 t
These returned values are combined to produce the final result./ P; d& Z8 P) g/ _8 p4 I( U3 z9 o
4 g. v# C7 ~& o% k( cFor factorial(5):/ L# Z! l; U1 L
; A5 H) e+ n1 @. m
' q4 n' D$ k$ }7 k7 _5 K8 a
factorial(5) = 5 * factorial(4). A; V; u/ j8 g* x4 { V5 v
factorial(4) = 4 * factorial(3), O7 S {' h4 d2 o/ x( u; R
factorial(3) = 3 * factorial(2)7 q' k1 D4 M- ?7 z: m! X
factorial(2) = 2 * factorial(1) / n2 U8 C! v0 \7 Dfactorial(1) = 1 * factorial(0) 9 w/ G! D3 J6 k3 k; Cfactorial(0) = 1 # Base case 7 y1 \1 r3 k$ H; K2 `6 A" K + A9 q% O( o D+ n2 \7 }2 NThen, the results are combined: 0 e2 L; W) u* A6 }$ K$ o. n ! O6 Q0 S4 H% {% c8 z* T3 Y1 w! R5 u& b$ d. V# Z& `
factorial(1) = 1 * 1 = 1& \4 P+ O' d* V$ Z/ ] g
factorial(2) = 2 * 1 = 2: U8 K5 R0 z! H. j' P! g
factorial(3) = 3 * 2 = 6 0 k2 x, {0 U2 `factorial(4) = 4 * 6 = 24; \& K- k0 V1 ]. U6 m! ~
factorial(5) = 5 * 24 = 1203 h. h" A' f6 J4 z4 V
1 i- a9 _1 s# U: o4 K' }
Advantages of Recursion \8 W3 \& R! N* t0 _6 X+ s
- N8 y9 K6 x D$ {
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). . y1 Y5 J% S+ S' X9 s3 t" U6 p W0 Z9 i4 J0 M% A
Readability: Recursive code can be more readable and concise compared to iterative solutions.% Z {% H+ S( C! G6 d7 x
5 x, p8 t, y; }: j4 d5 F9 x
Disadvantages of Recursion $ L }, ?2 T! H5 O , f1 @. M: i5 w$ 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., o% M4 y& ?3 n' N
3 l0 u, Q: a; q6 I/ C' z
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). p5 K7 p) ~: y1 f
- G; F1 n- W8 R" o7 nWhen to Use Recursion q" @' U8 H- B- f; l6 P0 I
+ m8 b0 K' J5 h. q3 \1 X3 L/ @' U Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). ( x u+ O+ V) Y! x& R5 q6 V$ z: A/ W1 A
Problems with a clear base case and recursive case. Y: V5 L' S6 t0 a1 \+ E( j8 ] - o2 l4 I* {6 F4 V, aExample: Fibonacci Sequence& e! A* W6 Z. l8 ~ A: W6 N
2 p' @/ `, O+ D+ X2 h% ?# c
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:1 J! E5 V. p: q3 A( z
' L* Y! }* f2 B0 K; f Base case: fib(0) = 0, fib(1) = 1 " l# H: ?5 o0 x% w ( g8 X# `$ ]) [1 g* v" R, G Recursive case: fib(n) = fib(n-1) + fib(n-2)) D6 t i" h- l8 o
/ {& z: s% Y3 I$ \9 X1 x. H6 K$ J/ Z
def fibonacci(n): 2 r/ e2 I0 t: t4 h) y! J& y6 G4 t2 g # Base cases 6 G/ Z; q; e$ O! ^' e3 r if n == 0:' S: Y/ A; P) H; O: m1 c# s
return 07 ^" p) D- l* ^
elif n == 1: 5 e v/ x$ e7 `/ `* O) P3 o return 1+ q# K0 G+ O B4 l
# Recursive case . S. h# e5 C/ R( ? else: 9 J3 H$ N5 B2 Q/ @6 z; S% W% W return fibonacci(n - 1) + fibonacci(n - 2) 4 K% D5 G6 ~* Q, ?" K 0 @- m: D# Z& q. P, [4 S# Example usage9 ?: E [/ d& m$ [1 W
print(fibonacci(6)) # Output: 8 ' H2 t4 d5 Q3 U0 D/ f0 b2 f$ T9 y. d* q4 u, |( K" O+ d- i8 k
Tail Recursion ( Y7 }- Q; ^0 g( H5 ^ * K3 t& F4 B3 P3 x5 K' ITail 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).7 s! u& T7 w5 ~/ J5 [
6 T. o2 ^7 I+ i+ u
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 现在的开发流程,让一个老同志复习复习,快忘光了。