S) Q8 p4 I% k/ M% ?6 I" G! P" O解释的不错7 e' N$ [: Q! L* T
* U d: ^1 w: m% p6 w) M递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。 6 K3 K' V4 ?3 f4 X# N: j5 g6 |+ n9 G& ^: q& b/ a& b
关键要素& Z2 _4 y3 }; Y" S9 V6 Q# H
1. **基线条件(Base Case)** " M v8 s1 I1 G! }% G' P* I4 [ - 递归终止的条件,防止无限循环 $ b' E4 ~4 t( g" O - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 3 T" V- N0 A5 O3 X # C6 x: @* H( v4 f% L* V4 K2. **递归条件(Recursive Case)** % j+ A$ t5 c: D: v$ y( J0 h - 将原问题分解为更小的子问题 1 z0 _5 j' m9 v - 例如:n! = n × (n-1)! 8 H- c& H) S# [) g0 C# |! F% j! }( E
经典示例:计算阶乘1 d+ |" B1 ?' W" _( \+ O
python . ^" m8 g5 Q3 Rdef factorial(n):/ n0 o2 e' K1 X! i2 F
if n == 0: # 基线条件5 x6 L& S2 H) x2 ?5 Z* z/ L
return 1# }7 ]7 b/ n" S2 `' k$ v& I
else: # 递归条件1 R- d# ]8 G$ B4 o3 }6 m9 |: A, x
return n * factorial(n-1)* Q& [# {" V# b
执行过程(以计算 3! 为例): . f, l9 x3 C7 w% Lfactorial(3) ! f% e! Z$ p, w4 a, K4 Q3 * factorial(2). ~- R8 O, f, {/ V- ?
3 * (2 * factorial(1))8 [0 u# N- A' Z& X9 Z
3 * (2 * (1 * factorial(0)))% H0 e$ h9 `6 f( s4 \
3 * (2 * (1 * 1)) = 60 E0 r5 b& ^! z5 m+ T, H" d o/ x
$ Z4 h3 }; O. I! ~) S4 J9 L
递归思维要点' P+ W; R! T0 o" X1 a/ Q
1. **信任递归**:假设子问题已经解决,专注当前层逻辑) o% L2 H/ E1 u! L* g; p" c
2. **栈结构**:每次调用都会创建新的栈帧(内存空间) ' i5 B5 m% A3 C- y3. **递推过程**:不断向下分解问题(递) : l9 O+ Y3 Y' _# f0 E d0 l4. **回溯过程**:组合子问题结果返回(归)- _* }/ Z0 v* Y$ U: X' i
; D0 d! I. S" A/ X# u/ k 注意事项 : f7 D3 \; {; f9 r1 d3 h* f e必须要有终止条件9 ?, Z" k& W# O6 g& m
递归深度过大可能导致栈溢出(Python默认递归深度约1000层) " s9 {& D I: c% R+ C某些问题用递归更直观(如树遍历),但效率可能不如迭代 * K$ V$ k5 V6 K$ }8 k& f尾递归优化可以提升效率(但Python不支持) 8 J( V9 X% o8 ]/ }$ _2 U+ t3 A& T2 x7 n8 [/ H/ p9 W! {
递归 vs 迭代. J) q; b. w; u9 ~$ a; ^/ ?# G. r1 m
| | 递归 | 迭代 |2 d/ C+ A8 v" ] G) j8 [6 Z6 M
|----------|-----------------------------|------------------|: l8 A [( Q8 w4 T6 s) f
| 实现方式 | 函数自调用 | 循环结构 |5 }8 ]; S; P: o) q3 E
| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 |# I1 _9 [7 r" x( z
| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |) t( o2 d0 d- I( L/ Q
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | : Z, |, d8 g7 |) [: W F# d# D+ a$ l0 k3 |4 }5 g 经典递归应用场景 8 g9 G7 B2 ~- i; U: b# `7 J1. 文件系统遍历(目录树结构)0 E f" }" n$ X6 X
2. 快速排序/归并排序算法: l7 u) i7 a9 Z6 A, R0 a
3. 汉诺塔问题 3 x+ | R3 ^; U7 x4. 二叉树遍历(前序/中序/后序)- S' [0 \5 S7 [; Y
5. 生成所有可能的组合(回溯算法)$ U6 k' c5 W& f' U6 h" e, F
6 O/ _2 z1 E2 |$ o9 z+ S试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒, # G; N& H% ~3 c6 [我推理机的核心算法应该是二叉树遍历的变种。5 X3 E/ u. v& Q* c
另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:5 K6 S' e# s2 _+ \
Key Idea of Recursion % A q! ?4 R. ~7 {$ V G( [- a9 V: c/ a0 K, k7 [6 _$ Y
A recursive function solves a problem by: - q4 N: u& U. H1 i % G; C$ U* T4 J M Breaking the problem into smaller instances of the same problem. , z; r6 h5 U: J* I' _9 J* b1 g6 W, H2 c$ O C2 n4 |6 h$ [9 s
Solving the smallest instance directly (base case). & ^4 \$ J- l3 Z) R1 |* ^: G8 U6 i+ T Q3 N9 _ ^' l
Combining the results of smaller instances to solve the larger problem. 8 E" L: F# W; v7 \9 y: e O8 m; z* N0 i9 p" R7 z! FComponents of a Recursive Function 8 o" r6 I; r+ c" i% p1 |, R7 K- w6 Z* Y8 }0 ~- _ V6 |- @
Base Case: 8 ^' f. Z. J/ Z G3 c$ z. [( K+ C2 W: Y9 F' O. t1 G
This is the simplest, smallest instance of the problem that can be solved directly without further recursion. , v$ v# C. C3 g$ x$ o $ @" \$ R. R+ T. {. G _* K5 b; C It acts as the stopping condition to prevent infinite recursion. 1 m* @: T) U5 ?& K . h# p" j. f1 b2 b Example: In calculating the factorial of a number, the base case is factorial(0) = 1. 6 m$ i i5 N1 e' G5 b/ E/ {+ O. m$ v) T4 o
Recursive Case: , n. e' ]1 {. N, u6 x1 |5 u8 J0 r% S j& o
This is where the function calls itself with a smaller or simpler version of the problem. ' Z4 E" K: X/ g , P! R( P0 ]% Z# w Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).6 |8 R) g- g( i( y1 C- C
9 T9 U# n- X2 T" p. ]
Example: Factorial Calculation* r' r9 ]4 E4 V9 a7 X
* M; f+ E. w6 O! E8 A( }* H6 s
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:# h8 q5 N9 `0 A& y2 A# q& Q
* r+ P4 ]4 F7 y" h% w( I' v Base case: 0! = 18 a1 K4 l' W% q5 L: j2 ]
2 k- V3 V% j/ N7 d+ w" [3 @% A) G
Recursive case: n! = n * (n-1)! , @8 ]$ b! o, X' r4 M , |: c7 K. Y* L% ~- N# `6 T: a3 AHere’s how it looks in code (Python):+ ^9 E' G+ a: p- {
python 3 Q. l' @: P, f; v5 g+ t6 v/ ~3 a6 @; n
& [; J8 a9 b7 R% h& |def factorial(n): ) g2 J) v! {. _ # Base case0 _" b5 d2 R9 f! c% E/ m
if n == 0:- B7 m4 |5 o. [; G
return 1 0 t+ c: b8 @ A$ o/ L7 l # Recursive case! T4 ]0 a2 p$ [1 h$ U
else:9 i& C3 }! k: O6 j. F
return n * factorial(n - 1); U; ?, ^ x$ v8 E4 D
5 P S% c9 q8 c- a9 v+ W' q* X+ q# Example usage r' K. H) \8 ^print(factorial(5)) # Output: 120 ; C' l/ I9 N& i6 Q, H 1 H j2 Z7 c4 r" gHow Recursion Works9 i8 o8 m6 `- F4 B
7 e( @" l, u2 {' Q O e9 Y# ]2 ]* W+ Q
The function keeps calling itself with smaller inputs until it reaches the base case.. G0 V/ V7 W( J& @" X' }
. L1 V. ^3 b# p4 q6 g; b Once the base case is reached, the function starts returning values back up the call stack. 1 d) o B! t7 |. O( Z* o$ ^; {+ N0 ]: y
These returned values are combined to produce the final result.3 k, h0 q" i/ A
3 A) y1 r* I' i, y" jfactorial(5) = 5 * factorial(4), P. I9 G: ]" h/ k
factorial(4) = 4 * factorial(3)8 {1 Z& _7 A, ^1 o+ g
factorial(3) = 3 * factorial(2) & j8 Q( w" E" K7 l) m" j- Lfactorial(2) = 2 * factorial(1)" U. g4 J4 C$ R6 |' }
factorial(1) = 1 * factorial(0)1 m: N- P1 g* d% O' |
factorial(0) = 1 # Base case " K, d3 N+ ^: T: D, @4 @4 b+ W% i0 h% J" y$ Z8 Y
Then, the results are combined:9 h! P4 Y) u/ q1 t5 Y5 S* E$ B, Q
0 ^2 m4 o! g- ?/ |
- e! @7 W2 y4 Y, {
factorial(1) = 1 * 1 = 1 . M3 `+ n# {# b; f( Sfactorial(2) = 2 * 1 = 2 3 `5 t, U/ N/ W: {* r6 Y8 [( ffactorial(3) = 3 * 2 = 64 P. l% }. H {( Z' m/ b/ ^2 p
factorial(4) = 4 * 6 = 245 ?) ] i1 ]2 F8 X2 q* b
factorial(5) = 5 * 24 = 120 7 _; s* o, v9 R& B5 h: M* L ) n) m% `8 A: b s( G5 `! ^Advantages of Recursion" T& U; a% X- Z3 {) G
2 R# q, d' r @* W! t- Z 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).2 _8 p* Z( `7 y. ]8 _
# u$ P% R! Z" L1 z# y J Readability: Recursive code can be more readable and concise compared to iterative solutions.. e: Q' _3 A/ q4 x5 `& _0 j, K
4 ^+ _; V1 s, }2 n; j; O( m
Disadvantages of Recursion ) q) j# d' H; J3 Y. m/ _/ e7 Z/ Q0 B" t; ^# \3 G7 k
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. ' R0 `$ {' Q y# c, O/ o7 _# S2 l6 `- G4 U* p
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).' k7 v8 h. s" f3 x, m3 ? ?4 s$ a
* B' q7 L. J. S% V9 K8 Z$ Y% d& v
When to Use Recursion2 c# T) c$ E/ q1 K' e" p* e6 q
7 A4 M0 N7 v/ O# V; `1 W Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort). " k4 I0 A1 n- |$ p, N+ f! `1 x. Z9 W6 d" i& V7 G
Problems with a clear base case and recursive case./ d5 m( _$ d8 M9 G" z2 j; m
5 F* F% _) b3 k# x- K$ z. |Example: Fibonacci Sequence 1 [ W ?0 I B* q3 _! [9 r" O+ c0 }0 a- [8 Y K4 y
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:, `' V( U5 E! ]5 i; E& b
" X; K# e0 x. |! v0 Y/ O* k8 F Base case: fib(0) = 0, fib(1) = 1' @$ X* ?" Z/ k( m/ X
9 l) C- X O/ T( Q
Recursive case: fib(n) = fib(n-1) + fib(n-2), E0 d; O; E% w8 \' ^0 v( Y4 p
) y h. y% \# \& I, p; Q' A4 B& Q4 dpython 6 {5 b' A' V4 N6 K/ d. q! k& Q 5 d) I1 i& F- M! L$ v2 P! d" q3 b/ Q* N& P
def fibonacci(n): , i7 n( |' C. D5 R! z # Base cases( e: K, R! k! Z* F
if n == 0: . q1 n$ e1 [ i- q7 O return 0 2 g8 y" J- ]- }: Q# |# d elif n == 1: d8 j& n, x \: ]% x return 1( P. j3 r' W4 I/ k
# Recursive case $ f7 A- e8 ~* { else:& G r# `9 c& m
return fibonacci(n - 1) + fibonacci(n - 2) ' f0 p+ ]; Z+ b% w% i$ U ) Z4 [% P* N: }1 y4 L: Y4 W# Example usage / n& R3 [# b) w% Q! Kprint(fibonacci(6)) # Output: 8' U) v! R" }( j8 C" L
- v& @$ K( t1 f0 ~. I# G
Tail Recursion0 Y5 e- F% f+ _# H6 _9 H* {
* S- Q% u0 W& ~7 U
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).) t% h) c& g4 V
# I( J$ D( W" ~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 现在的开发流程,让一个老同志复习复习,快忘光了。