( ]; n8 E( F" i8 G5 o4 m解释的不错/ z; `1 T& D& ~! S
) ?: |: L; {: E
递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。$ W( t: E6 p: w
; n3 R4 \/ V8 M! x2 ], K. w$ J 关键要素 1 L) B' C' Y7 Q- A8 o1. **基线条件(Base Case)**! j2 o* Q4 v' Q6 q
- 递归终止的条件,防止无限循环 4 G4 k2 F4 e6 h( y - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 ( U$ e D. p8 G. [8 j, G3 t ! g+ q3 Y6 d7 I- Z: i7 j; M8 \2. **递归条件(Recursive Case)**1 J6 ^ K1 S- f& Z; l9 A
- 将原问题分解为更小的子问题 ! k5 A' {0 U4 {& S - 例如:n! = n × (n-1)! 1 \ }' H, o. {" f& S, C$ T6 @" |% ]* h
经典示例:计算阶乘6 Y* [+ U5 K3 M/ _8 |
python ( @( G4 J& d1 j$ X" Idef factorial(n): S- V. i: B/ [. ` {7 I6 H
if n == 0: # 基线条件 " y0 r( ~. Q, C" E% r o" _7 \ return 1" i" C9 _1 h, _2 f6 e6 L
else: # 递归条件 ; e5 p% h; Y. r3 @; W return n * factorial(n-1) + h- i" `# u* H+ M" ]- a# R5 Y执行过程(以计算 3! 为例):; }$ Y; L" a S, R" M. G
factorial(3)8 n3 U& R* x# K9 z4 r
3 * factorial(2)6 X! ~9 E7 v5 ~1 `7 i, E
3 * (2 * factorial(1))$ ]) i" ^2 d% G
3 * (2 * (1 * factorial(0))) 2 D2 U* s0 j- f* D3 * (2 * (1 * 1)) = 6" K4 B U; N$ p$ u1 \* @
1 {3 C9 ~! t+ G' b: M& C; f+ z) p/ J
递归思维要点 5 D/ \- Y' K- V1 F( B1. **信任递归**:假设子问题已经解决,专注当前层逻辑: N2 s1 ]0 a8 v
2. **栈结构**:每次调用都会创建新的栈帧(内存空间)' h. P: {/ l7 s
3. **递推过程**:不断向下分解问题(递)( e0 B) T8 t5 g% n
4. **回溯过程**:组合子问题结果返回(归); e* u5 n& E! }% t4 }4 q+ w
8 q5 \0 u5 A" Q" T) @' ~* i* @" u$ N( z
注意事项 5 z8 x! n/ a A" ]$ ~必须要有终止条件 5 `# W9 S% B/ d递归深度过大可能导致栈溢出(Python默认递归深度约1000层) Q. G7 @7 U! ]1 }/ J某些问题用递归更直观(如树遍历),但效率可能不如迭代& O2 N1 n5 g4 z r
尾递归优化可以提升效率(但Python不支持) # l8 J2 x9 }% d4 c0 R9 H7 s, @
递归 vs 迭代 0 P& S& S$ t4 Q! W6 j+ ]8 s( ~* q| | 递归 | 迭代 | . L* ~! K5 @( H# [2 @|----------|-----------------------------|------------------| 2 k; L8 x) g- \- h( I$ T4 L| 实现方式 | 函数自调用 | 循环结构 | A# k. M, [- x& ?| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | # @+ T0 P& S7 y; C" `| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |' x# [% A$ t6 B; \4 ]" Y- L
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 |0 _% s/ v( S' K' d9 @& p/ L$ x7 p
7 J) c" u7 L+ d 经典递归应用场景7 y; p1 ^1 M/ J
1. 文件系统遍历(目录树结构) " k8 d+ i+ q. w4 B* y. A7 D; B; e2. 快速排序/归并排序算法" W5 O; u" k; N4 o
3. 汉诺塔问题 ) t, x4 m4 Y+ Z, C ]4. 二叉树遍历(前序/中序/后序) ! ~6 B* e% L) X7 _/ y$ b" ?5. 生成所有可能的组合(回溯算法) 7 n, p( q2 ]& Q1 q/ O2 @# b& w # Q& c4 J! q& {( t; O1 s/ A7 P试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,: c8 |, b7 b& z$ N) V: t. w5 w
我推理机的核心算法应该是二叉树遍历的变种。 0 {- @/ k$ e5 X# U G/ ~另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: ) i/ @' S' o+ |9 |# Q4 ~! X0 pKey Idea of Recursion : Z% K# u/ T. J8 T* Z' a0 W 0 Q2 x) R9 [7 U! }/ C! g3 M+ PA recursive function solves a problem by: " O y3 `8 J* n5 o5 E + T1 U! B9 d! \/ ` Breaking the problem into smaller instances of the same problem.; K0 L! N* r) p, B
3 @% N8 M! ]9 M/ t" ?1 ^ Solving the smallest instance directly (base case). 5 G: ~ v5 n- e! _ * r# c# ?; `5 U- P t( m; l Combining the results of smaller instances to solve the larger problem.# d' a& b9 f5 z( c
/ e2 b5 o7 \0 a- |
Components of a Recursive Function ) v; A, S4 K. D9 ^- Z( V: V) z6 t
Base Case: 0 l5 {! q6 B, M" e, ]3 J( E% {$ Q, k5 X" ]/ y6 x8 n; o7 X! V
This is the simplest, smallest instance of the problem that can be solved directly without further recursion.% G- p; L2 E, L+ o" H' ]8 \9 c
) ^% n* S0 `$ d" v6 J/ \ It acts as the stopping condition to prevent infinite recursion.; N5 Y% U% F* c) m' n: e# n( v
5 a2 f: X& `% u; F3 Y8 O2 i7 G Example: In calculating the factorial of a number, the base case is factorial(0) = 1. 5 A' a, b5 q* ^" \4 T! s* S) D5 w3 W- s) b, Y) m
Recursive Case: : r1 X8 D% t d6 c, C7 j5 j 8 `+ _6 q- v# w" p& ~ This is where the function calls itself with a smaller or simpler version of the problem. 4 P8 z' @) s+ g6 W 4 J9 e& n: F* g$ X3 X V# M; M h Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). ; {$ w p2 I3 b& b# Z : p+ o: \( y% Z" W1 U+ v" jExample: Factorial Calculation+ \7 Y- S! y: W
" p2 G0 s. l _1 `+ 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:$ C9 w7 O. M, P6 V
: l. ]1 h! S0 x. H
Base case: 0! = 1 ) r: Z' ^2 D# L6 i+ g% z % Q3 y6 }% ?0 W Recursive case: n! = n * (n-1)! & i. p* K4 d2 A* a" y/ ^/ q8 |5 ?1 h$ e* r; \- X+ @" l# V* G
Here’s how it looks in code (Python):/ K$ i6 W) I2 f
python! q1 ^) p, f0 \" b. Y7 `9 U
2 j$ T% I9 n* o$ a$ V2 R# N/ |" ~- e4 t- Z: Z A
def factorial(n): ! G9 J* F n. p, X& M# K6 J # Base case " {) }( i5 D1 _. M- Z) V4 d if n == 0: 9 Z) u. |' o5 ~ return 1- ?& i$ ? A& I9 L5 _
# Recursive case * k+ {- ^6 O4 V! B else:5 b5 L" C; s3 U* `! I5 z: l' J
return n * factorial(n - 1)6 E/ m# B2 ~ V1 I' A. S- O
5 N5 d5 v7 v1 D: o# Example usage " v9 ~& u; l) |5 M" n- j' gprint(factorial(5)) # Output: 120 & ^0 q( ?/ y# k# L 7 t" L, ?- \9 G5 t' e THow Recursion Works . d2 r2 I- Q4 u4 K, ?! X ) j% h' P' v. t9 Q* W5 Y" ? The function keeps calling itself with smaller inputs until it reaches the base case.- ^: X! w0 k, ^5 f
6 g* x! M) H! g; s9 x Once the base case is reached, the function starts returning values back up the call stack.5 \/ d) t* ]3 Y) k$ z
8 z2 j' L) J2 T7 L' z
These returned values are combined to produce the final result. 4 E9 K1 k- e0 D- S ( m7 ?9 t0 X* Y: dFor factorial(5):' U* J/ e: s8 Z: m
$ i& O9 K, l7 k* Q
8 o4 a6 @: z' I% i4 J# J/ j+ e9 q! B
factorial(5) = 5 * factorial(4) - ~) z! [& U7 e# |8 T% lfactorial(4) = 4 * factorial(3)% v; D4 a+ `! H/ n. q2 u
factorial(3) = 3 * factorial(2) ~$ C6 l; @) M% u& U3 A' R/ yfactorial(2) = 2 * factorial(1) * M6 `: q! [5 v# `+ Z6 K7 S0 Kfactorial(1) = 1 * factorial(0)! g* o- g3 q$ I5 A2 C. D d0 f" p
factorial(0) = 1 # Base case + [ i9 H+ s; e7 \7 c & _; M, u) c$ s% o# f2 Q. ?! ]* hThen, the results are combined: 5 V8 D4 V$ e/ p w( n9 U* a4 G( l# B/ d ) k* }; [1 B- T' H 4 N+ J6 Q$ X# ]% x2 f& wfactorial(1) = 1 * 1 = 1, I: {2 j0 `: M4 _, W/ J
factorial(2) = 2 * 1 = 24 M& {1 U! ?: p9 {3 \
factorial(3) = 3 * 2 = 6$ |) \; J, P) J2 W4 |
factorial(4) = 4 * 6 = 245 r ~1 \; v+ [3 d
factorial(5) = 5 * 24 = 120$ P8 w6 g, C2 ?7 n# O
) l# |/ c! a( PAdvantages of Recursion % \7 u0 ^- A; H3 M7 p* I7 ~ E8 F. |/ c# S% F6 u1 T* M" S4 @
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). $ t* ]1 ~4 m9 L& r: y5 ~ ! r- p7 ?+ M& v; s Readability: Recursive code can be more readable and concise compared to iterative solutions. 1 w! e! Q" [4 j# B% f. O 7 d: ]7 K+ F6 C8 O) uDisadvantages of Recursion ! r9 N' `) U) m* R7 Y # X. X j4 a% \! T7 v: e 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.% D! j+ \% f8 ~( G D. L. K
; y0 q8 b' \4 X3 Y; Z
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). N- |5 H2 ]' k% b& C
+ o7 v) l8 w- _9 r' G
When to Use Recursion) [; _, X# b+ x0 Y, ?2 l
5 h ]' R" |1 g; K# s1 X3 e- J Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). + }; P" w& X: E8 @5 T' Z9 Z: \, G2 R# _7 f" y( \
Problems with a clear base case and recursive case. 2 i) e/ {) w3 H: \) M7 w1 U. F1 s; w5 I: m0 f
Example: Fibonacci Sequence/ |- @. R9 s0 V H/ z4 f
; Y5 b5 W, ?* K7 k3 I" L eThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:8 W# t* M: r2 W. R% e. J9 p0 e0 g- Y
$ y/ A1 x" @ {6 G
Base case: fib(0) = 0, fib(1) = 11 [( k4 O. Q4 y
( e6 C) B- F' o2 ? Recursive case: fib(n) = fib(n-1) + fib(n-2) # o0 `. Y; B8 f N+ H; R9 o5 A e% p3 e
python ' i* O/ x( E) x% d2 B$ Z: ^4 g+ O3 l- S
: z7 `$ Q. k3 Gdef fibonacci(n): ) v/ `! u. _3 M" S" \0 u& P # Base cases $ u9 O2 p! T6 \0 K8 @ if n == 0:# }+ R: \6 [( S' G% X$ j
return 0$ X/ W' o8 F6 J1 f* [& F
elif n == 1: 1 E4 H, K. @2 F$ @% ^$ ]2 ` return 1 2 V% f3 {2 G& @$ `4 M. T # Recursive case % r- r! q% z: K* W else:! r3 \8 l+ z6 K! o4 e
return fibonacci(n - 1) + fibonacci(n - 2)& X% e6 v; c" N0 E& A1 T
9 i& ?- o7 E# W6 Q0 n0 P# Example usage$ a$ I0 \' C+ o1 W+ Z3 f) r. N: ]
print(fibonacci(6)) # Output: 8 R0 i5 A" O! X% M+ D& v7 q1 P4 Z8 }7 b
Tail Recursion 9 Q4 K. C. D1 _) J5 D( ]7 J: K# i ( E" y O5 ?: oTail 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). ( x2 w M% p4 q& F 0 _. G/ e7 k$ b$ x# u- G' HIn 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 现在的开发流程,让一个老同志复习复习,快忘光了。