( O) q+ |& c* k& @' ^4 P; K解释的不错7 c0 N0 `4 k1 M9 U8 ?3 `
: k0 @& |2 ~8 E2 c C) p
递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。 2 | V {% E9 m& I% C0 J0 k( v& r, U( y" s
关键要素 7 _, S6 r% @( ~2 P1. **基线条件(Base Case)** y5 F- F; n, J, z' h# g- F - 递归终止的条件,防止无限循环 7 I7 }& L! m. D1 l8 _3 K - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1- q; d$ b4 O) J# o2 i$ e" l
) f2 c5 ?6 j' s) E# g1 m
2. **递归条件(Recursive Case)** / h u* K1 }0 j6 n/ u - 将原问题分解为更小的子问题 : C, ?7 W& i+ H, I- E - 例如:n! = n × (n-1)! " d! [. k6 i R1 ?) y - y3 A" L7 y, ~ 经典示例:计算阶乘. _5 b" {) @, L% w; ~4 v8 m9 o3 B
python S& a9 S' P( Ndef factorial(n): * b8 S3 x6 c# `# }: A if n == 0: # 基线条件 ! F- {8 \$ F2 q" T' s return 1 6 }, r) V. N# l& \ |2 e else: # 递归条件4 l8 g, h5 |9 X
return n * factorial(n-1) 9 I8 e7 s( O. r& |6 Z. E执行过程(以计算 3! 为例):3 M8 L" i6 _' @/ q2 E
factorial(3)9 _! H% ]& J5 i9 o6 x7 S$ T% p `4 A
3 * factorial(2). V) X5 w2 @$ I! p; h0 h
3 * (2 * factorial(1)) 7 v& s' g/ ?( k2 [3 * (2 * (1 * factorial(0))) ( h; U# V7 y# M6 P3 * (2 * (1 * 1)) = 6 * m+ h5 I0 S: r3 v& N9 H [# A7 Y: |, [9 f+ A
递归思维要点) e7 _* \+ M# W8 V+ ^
1. **信任递归**:假设子问题已经解决,专注当前层逻辑7 K3 W, p, ~8 }/ r2 g
2. **栈结构**:每次调用都会创建新的栈帧(内存空间)3 G1 k) b2 W& J4 Y
3. **递推过程**:不断向下分解问题(递)0 c; P4 J* `& _/ H/ Q* s
4. **回溯过程**:组合子问题结果返回(归) 0 E( a: ?& B: j+ N p8 n0 ~0 B! x$ a& M: s
注意事项0 m: H5 `( I5 V5 R( h$ Y1 e3 u* g
必须要有终止条件 7 x5 ^/ K/ g4 z8 N6 _: x递归深度过大可能导致栈溢出(Python默认递归深度约1000层) 6 M3 e# m" U2 t- g# i! k' u某些问题用递归更直观(如树遍历),但效率可能不如迭代 2 k; l O' e. C, J6 ^& g尾递归优化可以提升效率(但Python不支持) ; q- @" d* I* D. d3 `3 M6 ?: z/ x# P# L0 M
递归 vs 迭代 8 ?6 H% _' j7 @8 e8 v+ z| | 递归 | 迭代 | 9 K9 ~! p2 E, x0 M|----------|-----------------------------|------------------|: s9 w( v/ f7 ]/ }2 K4 Y( L
| 实现方式 | 函数自调用 | 循环结构 | 7 _$ H% ?5 h0 l1 m5 s| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 |9 f- {" D; N4 m
| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 | ; a4 _8 d: f' ~) G; d1 F) T" v| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | 9 ]$ |4 Y8 j+ l/ |, x; N7 U! _+ M4 L" O9 [8 A G6 D
经典递归应用场景, @$ l7 v9 X$ v5 j* F
1. 文件系统遍历(目录树结构) 8 N' U* L3 J& @) T$ p9 A2. 快速排序/归并排序算法 % d! `! X0 G' V: j0 B! _3. 汉诺塔问题 ( a& q1 S P# C8 u4 _, E, |4. 二叉树遍历(前序/中序/后序) ' o& Z& u2 X1 N% n5 ^: g' Y+ k4 s5. 生成所有可能的组合(回溯算法) - e" V4 G# ]7 I ) p9 E) M/ |: b4 z* Y# \: h$ a试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒," h6 I, K0 W% _) Q
我推理机的核心算法应该是二叉树遍历的变种。 ) Q {+ S1 _+ i% O- `: }: @另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: - O) B) @4 Q8 TKey Idea of Recursion $ R! U4 f7 q4 P W $ k+ G: f& G" M2 j% ZA recursive function solves a problem by:2 y* d9 g" Q. ^; I3 X% u; Y3 G
2 y: H2 r9 t5 h! ^
Breaking the problem into smaller instances of the same problem.6 e, _/ ]3 m. L- d z4 s2 j2 w
7 w1 W/ k# Z. K _
Solving the smallest instance directly (base case).8 c' H9 _! ]* L3 y% C
' d* {, T6 ?" V; ] Combining the results of smaller instances to solve the larger problem. ( S+ \ p4 ]' H/ G 1 ?% k: n) g* W" N- LComponents of a Recursive Function2 I6 ]6 O# U. p4 B- j/ e; r
% k9 d5 Z& \5 A" W$ X" g; ` Base Case:( X( Q# {- {% H8 W% z! j9 [
) ~) T1 m8 z9 x7 @$ t3 z
This is the simplest, smallest instance of the problem that can be solved directly without further recursion. - m( \- q! F" p8 }5 B 2 V" y- }; t+ X+ V It acts as the stopping condition to prevent infinite recursion. $ F0 d5 U& w5 N$ P, k* [ & H n7 N5 d0 t( v Example: In calculating the factorial of a number, the base case is factorial(0) = 1.; q e+ u' T1 j2 |
1 N7 \0 p. o+ R3 ?) ~. `
Recursive Case: . |% R; F4 k8 r- N: i* T3 |, D- v: P+ T+ d
This is where the function calls itself with a smaller or simpler version of the problem." y& k$ E( o# \
) y/ I3 S& Y! s& `7 I+ z Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).7 u* a, \& _" z9 y9 i2 k! [8 e
# B; a" W& I/ B* o% gExample: Factorial Calculation % A7 C/ n% r' y4 V! |7 Y5 \% x6 l) i6 H/ c8 Z3 e0 |
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:! W; c6 J7 r: A; q" {7 J4 F
( n# ]& r- ]3 \5 y' u Base case: 0! = 1 ' O H; m' s/ J; Q: O$ p9 G9 u- t1 Y) O# q- T
Recursive case: n! = n * (n-1)!! J2 q8 E* s4 o3 S3 Z
9 d) }0 m' r7 D
Here’s how it looks in code (Python): $ C# J- n/ n, Z% d8 N( f( Apython% a5 m _5 M* d% Q! C
7 r% h3 i M/ P5 o4 L/ e7 ]4 |/ A/ K1 x6 z3 }$ b2 y
def factorial(n):' }) ]5 }" U) }' F
# Base case) ~" D7 z [' q( \, ]
if n == 0: : j/ a2 n7 {- w0 b K1 r5 C return 1 9 I1 P" s! x; C5 W # Recursive case , C# S. R7 G6 a8 c6 ] else:& t) d/ \# S7 c$ U0 I) w
return n * factorial(n - 1) A# g+ p$ ]) ?& ?6 A7 m' n
2 |& t/ u3 B2 n# Example usage7 t. z4 z z+ ~' B) h
print(factorial(5)) # Output: 120( o+ w" w5 \- `% g
; Y9 N5 x1 b5 ?' g2 } The function keeps calling itself with smaller inputs until it reaches the base case. 5 W# F. J& K$ N: b/ k4 C3 t 2 ^, R0 E$ X! i# h1 |( S$ h Once the base case is reached, the function starts returning values back up the call stack.6 l! t* K9 s2 _ T2 G! m' x% W
3 [. i/ `6 u# |7 R7 x( R0 v4 _: V These returned values are combined to produce the final result.* t4 A0 ]9 E- P* e3 ?% [
+ ]; j7 K* z$ g5 p) ~3 UFor factorial(5): & m1 X m2 W/ S6 X1 J " w7 q$ S4 Q$ d4 r+ W . {+ y ]: K+ B( O. @factorial(5) = 5 * factorial(4) o; i$ Y- j' S
factorial(4) = 4 * factorial(3)3 f7 m, L, F Q9 U J) \- I
factorial(3) = 3 * factorial(2) 2 }9 E* u: A% w/ E# {2 hfactorial(2) = 2 * factorial(1) $ Y7 G# u: c5 u' Y$ [factorial(1) = 1 * factorial(0)& N: N9 `( R6 {, p9 z
factorial(0) = 1 # Base case 0 T# T2 z0 X+ H( g& [1 m 3 |, n1 k' {6 C' HThen, the results are combined:" Z1 q& J. R! Y* b& z& B
" s* g( |% t# @$ a( t; p, ]( N
/ n: y$ @9 s; r% g4 ~
factorial(1) = 1 * 1 = 1: H5 g2 _9 m- W
factorial(2) = 2 * 1 = 2! W* N4 p2 Q8 ]! w1 \
factorial(3) = 3 * 2 = 6 ~1 W2 N" t# b1 y8 [
factorial(4) = 4 * 6 = 24 5 @0 F. Z# w5 B! ]$ J* ufactorial(5) = 5 * 24 = 120 ! v& g/ k! c. D' M& C ; J( O- R8 p6 J5 V5 o6 M) `Advantages of Recursion- c& Z( k( T* E+ O6 f
: C4 a7 Q! T" |5 `
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). ; H" `5 q, c* w) _ ) b2 f* f9 T, Y Readability: Recursive code can be more readable and concise compared to iterative solutions. n1 I9 H+ u; w& K! B* X# D& E, w+ c6 R# K! a8 H9 X7 h3 r8 W7 V# H
Disadvantages of Recursion R# D0 C/ G' I `8 q - \( i) ^- Z0 ^0 {' d 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. 6 S. ~8 ?. {6 _+ k' z1 G, o7 g- ]5 f8 p, L. P7 O+ @' C
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). 0 g! |# z( r- D) N% C# i" O7 E* k* V0 f1 O7 y
When to Use Recursion. I; d4 Y$ Q- G/ h2 w$ \9 e/ K5 I1 O
' X9 Q4 v9 l7 @ l {0 a3 u Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).! P/ _3 u- N/ D; O, @* E. w. ~
1 X* W0 i: e' ~5 ] Problems with a clear base case and recursive case. ) E; |" H/ s# [" ~4 V* q5 D3 f( U( y' R G! M9 r
Example: Fibonacci Sequence - s7 n' p: a2 O. R: i9 m8 i- I 6 n$ T$ F7 H6 Z9 @+ d, f/ F# A. X% y* DThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:1 d( X# ^$ b3 t
! u. `2 w; u( `' l" K1 W- Z$ y- ~ Base case: fib(0) = 0, fib(1) = 1 ! X, Z+ B0 p# x; Q. s6 d; {" u+ w8 o) `+ m+ r1 Y
Recursive case: fib(n) = fib(n-1) + fib(n-2) n+ s3 K9 @" ~. F. C# J# a K/ b2 J. P3 D
python8 ?- c. S& t: q6 G5 M' }3 E
, I7 e" Y5 u' V8 o# f
. I5 o! Y, {: d8 u8 G
def fibonacci(n): * b. W, v$ g0 m. x# S: ? # Base cases9 R- U c7 U. u+ ^2 a. g9 T0 e
if n == 0: # y8 A. o7 k6 V" k3 p7 k( y! r return 0* }8 {& D0 l& |
elif n == 1: * C8 C+ w9 F: s5 h" d return 1! e. k8 A2 ~ z6 u# D' @6 `$ v
# Recursive case9 {. Y. F& }3 i. H8 i
else:6 F0 i Y# }- c
return fibonacci(n - 1) + fibonacci(n - 2)# p/ u) H1 ^3 z0 V
# Y6 N# k3 l5 l. q
# Example usage8 P: c' ^4 f6 w! F
print(fibonacci(6)) # Output: 8 . V6 m$ t5 s1 R, Z) v7 z; R! H3 J
Tail Recursion! N7 C# i& u8 [. G
4 x% {) l Q) n( J8 @7 y( C( S
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). ! U3 h4 b0 v1 I c: }, u0 E( e+ W5 s/ T9 i4 ?1 Z) x
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 现在的开发流程,让一个老同志复习复习,快忘光了。