8 v# ~$ A: U+ Y# M, Y5 Y递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。: q- y* ^, v1 ]2 [2 u
6 t* Q6 u7 E& J# U$ v6 O- I: C
关键要素$ w2 z" r% Y. H
1. **基线条件(Base Case)** 4 [, ^( {! l; R/ c0 S$ o" Y0 ? - 递归终止的条件,防止无限循环 3 ~ \% [4 p& R' ~ - 例如:计算阶乘时 n == 0 或 n == 1 时返回 17 u4 ?$ t) x; p$ C
; i# F/ j6 o( q c
2. **递归条件(Recursive Case)** 2 L) m( z6 f1 ]+ ?* S - 将原问题分解为更小的子问题 / D" v: l. g! A$ z - 例如:n! = n × (n-1)! * N, Z- F$ m; O+ k 4 V6 m: c3 r- S, M1 T$ P; G8 T 经典示例:计算阶乘 5 ~& E1 t Z" g) L7 V, p% V: S& A+ rpython 0 j/ s# M; v$ Y& |1 y) ]def factorial(n):3 L' E4 g; s! q1 p0 Y
if n == 0: # 基线条件 7 B5 T- L2 O3 O# g5 ]- H return 1& X( x! ~& ~& z c3 D# ?/ o
else: # 递归条件 & a/ u! L( {, K( Z1 N4 v: q return n * factorial(n-1); D! U: D4 b& e5 n8 ]- f0 v
执行过程(以计算 3! 为例): ! p1 D. w' k1 i7 M; P b# Pfactorial(3). u; }- p* B5 L5 D( _2 V( t
3 * factorial(2)# M6 M* y. z. V. B- V
3 * (2 * factorial(1))) c {) `4 y2 K+ U1 }4 k% h5 @
3 * (2 * (1 * factorial(0))) 4 W1 L5 |! \( A8 y# D u3 * (2 * (1 * 1)) = 6+ a- j5 H/ a. s
" o. v# ~& v7 |) q; y
递归思维要点 5 u7 l5 p* Q. m1. **信任递归**:假设子问题已经解决,专注当前层逻辑) k. [: v6 |5 A) `& s& |. j
2. **栈结构**:每次调用都会创建新的栈帧(内存空间)4 O: ?0 J6 p- I# x. D% F+ @" w6 G
3. **递推过程**:不断向下分解问题(递) : a1 Z! c( g R! x4 c4. **回溯过程**:组合子问题结果返回(归) * w, h6 [; M5 B6 E# d+ H4 Z2 L0 ?. _, y( j9 i5 i
注意事项 * g) L3 O0 u! A: V9 g- |必须要有终止条件0 R# d( I) L. E3 g! H% @* y3 y( N1 Q
递归深度过大可能导致栈溢出(Python默认递归深度约1000层) + T6 J- a; n. n" O某些问题用递归更直观(如树遍历),但效率可能不如迭代+ ~: X0 b0 _- F
尾递归优化可以提升效率(但Python不支持) " O* n& c" T. j5 w; i/ R ) |. C* T7 U6 f 递归 vs 迭代 5 _% H) F4 i4 A1 Y6 q| | 递归 | 迭代 |2 o5 R/ O8 ^$ B1 G
|----------|-----------------------------|------------------|* P& R) P5 X2 g
| 实现方式 | 函数自调用 | 循环结构 | " t. w# Z/ J5 @+ F! x| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | * H; v F s/ o& i| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 | & e& o8 t- t) z( }| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | $ w- ?9 |- W2 y, a! T5 x8 d5 r0 n N+ r& x# z
经典递归应用场景2 |: n* P8 a3 ?& R
1. 文件系统遍历(目录树结构)5 }1 I* d- ^4 i4 |. ^1 l; I2 b
2. 快速排序/归并排序算法 $ L$ C8 G7 ^ T! n) x7 m5 H3. 汉诺塔问题 # t5 _, n$ i- l4. 二叉树遍历(前序/中序/后序) + i( N2 W' D" K! A. G) _* |1 I! `( ^2 J5. 生成所有可能的组合(回溯算法)" q0 o. ~7 o8 u8 V2 ]
- S' @, K3 k! j7 c. m
试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,8 j$ e$ ^6 g) i
我推理机的核心算法应该是二叉树遍历的变种。$ r( e) a1 r9 ~
另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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: $ X' @) A/ e; Y: G8 F! }Key Idea of Recursion r7 g, Q! I/ X) |. `* L/ c9 h 9 I: d$ E: g1 |; H, _# i/ hA recursive function solves a problem by:* F* `% m, }& J4 w1 M
9 k- j/ t% k1 t Breaking the problem into smaller instances of the same problem. $ ~& U& a* X7 ]. d7 l8 {; e+ w* e 4 s8 \: h" ~0 ~# Y7 Q Solving the smallest instance directly (base case).# C. j5 }# n+ h6 U# @
! q7 f! ^: y. S$ z
Combining the results of smaller instances to solve the larger problem./ b' T3 H! M4 p7 C- }
6 c1 Q' b3 F- l( B3 @1 u
Components of a Recursive Function * n3 b' k! c! ]$ h; X/ I' D( J, A3 I
Base Case: 3 Z3 _# R. A; s: U2 h3 u1 o ' h3 a4 G: K) X1 q This is the simplest, smallest instance of the problem that can be solved directly without further recursion., g) d: D- ]0 A: o1 a9 F
* f! H. u$ {. F2 j: r7 T
It acts as the stopping condition to prevent infinite recursion., i4 V3 ?( ^: V6 R
) L" ~$ U8 ]5 U. f8 t, q0 }$ P+ k
Example: In calculating the factorial of a number, the base case is factorial(0) = 1. & _- w, o/ E9 Q0 _) w% x+ }% F1 i1 v: E6 A, E/ y
Recursive Case: 2 i" X' b3 {6 }8 N4 F 2 {& U. Q1 p" a This is where the function calls itself with a smaller or simpler version of the problem. $ ?- L# R) j) n1 |7 d7 B9 ]& K! w- ~) M# C4 W6 w
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).' L' z6 ?" H0 d* k
| d( a+ U! n: PExample: Factorial Calculation . R( t- |: ^; R6 \6 D ! B: w& W. @) nThe 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: * t' ?' V8 S. e$ d4 L- v" S7 E# k* ?; h/ F9 @
Base case: 0! = 1! g) @! z" g h: Q" A- T
' O8 o2 L% m6 C; j+ I7 |& L4 i Recursive case: n! = n * (n-1)!* C& f& |) |5 @+ D
' B5 o! e7 a/ B* J* _& Y
Here’s how it looks in code (Python): ' C- u* e& L2 Q j! H$ @python ; f* T" y1 g( ^! U, b( Z2 C; W8 y1 q' X/ u: a/ _
! _( U( o* v! Y- Y# v. ?7 ^
def factorial(n): : D7 j. G0 A ?$ e9 Y # Base case / g7 J! Y$ H) \$ [; f6 n0 H if n == 0: 6 {$ g1 S% R5 z" s; o% S return 1 ' w! @! r$ {& K- G" q2 q9 w7 J # Recursive case. ?8 X8 `. N9 g- J2 D
else: % n$ @/ B) H' w3 C" m! b* i5 _ return n * factorial(n - 1)! Q( N! {( y) H4 b0 P, a
2 d8 y: b) f1 a- b. Q0 g
# Example usage ! T6 W' S" h: B) l) D2 Mprint(factorial(5)) # Output: 120" v4 [9 @. k2 I+ h# J: w
9 O K2 ]) J' T( M( K zHow Recursion Works, K) [5 ^7 F6 p
/ \- x' [9 i5 D. C. {( {, O
The function keeps calling itself with smaller inputs until it reaches the base case. 3 y6 i/ M6 G' P1 X1 E1 u- D6 Z9 Z$ e1 ~4 v. a& W7 i
Once the base case is reached, the function starts returning values back up the call stack. $ j; B4 J1 l% P4 j1 w& M* m0 ?9 Y% g* q* E
These returned values are combined to produce the final result. ) S# L) t0 _# b+ a8 I8 x, ?- I9 b) k3 F7 D- g$ J+ D6 T8 W
For factorial(5):1 t( c! |0 k3 h: w7 ?* B5 Y
7 O+ B' g1 u7 `. Z
4 J! b" m) T& s! r
factorial(5) = 5 * factorial(4) , p1 V4 H$ c% H0 W0 J; W( ?factorial(4) = 4 * factorial(3) 6 f1 ^: l; m' |+ H7 M& M* u% |factorial(3) = 3 * factorial(2) 8 y- Y2 n6 k* }' T2 z/ N* Bfactorial(2) = 2 * factorial(1) % t2 k5 `/ `3 G' y2 b/ ~, Ufactorial(1) = 1 * factorial(0)2 ^) d* E2 O7 I8 S" x& {
factorial(0) = 1 # Base case3 q# I. q) r& Y' Q7 m( S
' }" E4 Q- K# ]3 M. X2 j
Then, the results are combined: - C7 D' P( }. {' E " x# ]" ^0 A+ d) a8 _ " A- b8 A' Z# \$ Y B# X% }1 I Yfactorial(1) = 1 * 1 = 1 P; x! t) Y1 K$ n; E) a& x* lfactorial(2) = 2 * 1 = 2( A0 {$ }4 a$ H P/ u8 N
factorial(3) = 3 * 2 = 6 0 p" f0 I! Z, s0 Afactorial(4) = 4 * 6 = 24 : ?" x. m, A- R3 _3 d# R8 Y9 kfactorial(5) = 5 * 24 = 120, y8 ]0 y( `) L1 {) R
( O1 Z: w9 h' L3 U4 w+ U d/ a 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). . r8 k# V* E& i0 }+ U. d5 J# P% a 3 Z! e* J% r* w Readability: Recursive code can be more readable and concise compared to iterative solutions.: [! F" ?+ w6 ~% W
/ C3 _5 J5 c$ L8 |; n; T" jDisadvantages of Recursion6 j- @6 S, e2 g5 T
! S1 f% z; e4 ]! L$ 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.* {* l- o4 n" k' R5 B+ b! ~1 W/ S
: ~- Z0 k; `% i: I3 |0 q/ h Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). " z; R2 k. s' ^( _3 T; N. ?$ h$ n5 G$ i: N( @
When to Use Recursion- A+ O n, c* {( \5 g
# {2 t) Q1 W0 T F. w# s Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).0 j& w# w" y m9 }. c
) {! _3 j$ _& t- a* E, a1 \ Problems with a clear base case and recursive case./ j# L2 y' ?0 X( n) \2 r, c
; B5 H( Z; C5 v2 b7 L8 E3 s6 P
Example: Fibonacci Sequence' l& O( I$ p" U* ^
' x0 Q1 J9 X/ o4 \( J0 zThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones: 5 W2 x; w- h" @8 G& W, K/ F. l 2 |' ?+ e# {; s5 y Base case: fib(0) = 0, fib(1) = 1 4 |8 D# {& p3 V8 ?; E! F6 |- t6 @3 _, p/ g9 O% T; A2 u
Recursive case: fib(n) = fib(n-1) + fib(n-2) - B: f; F+ J6 C4 c) R2 H- d& J" Y6 G3 m' `3 p" o% j5 _: B
python . y! n, j# t% ?: ?+ n# A : \: ~1 g, z( F! T7 d. v5 v' ]. b. |' g: f0 `* t4 M
def fibonacci(n):; s; P$ K# h8 v' Q
# Base cases& u# q4 P. M5 f: D2 C
if n == 0:4 @6 `2 K2 d# ^, b+ T4 O0 u. `
return 0' J9 A; t4 `- C- O# j% C+ C! }/ H& Y
elif n == 1: 4 x- w0 }; l$ v3 F ]2 m% i/ ~/ q5 H return 1 , C* @ |5 m8 b# [" a( c # Recursive case2 x; }( v, N3 [9 a8 X
else:* [7 C0 A1 {- H7 p; U! x
return fibonacci(n - 1) + fibonacci(n - 2)& P/ @" Q N1 S4 f8 P5 k- ]
6 [1 T; ~' ]$ L# nTail Recursion, \6 H; n$ w5 D" u2 e- j6 }! P0 g
" }6 d1 T! Z' l$ y" C9 f* y
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).! `- s/ {1 @& n9 _$ t7 K
$ b# S- u& K. H* XIn 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 现在的开发流程,让一个老同志复习复习,快忘光了。