3 z& g2 ~2 C3 b- M 关键要素 p* h9 d% v% Q1. **基线条件(Base Case)** / G. G" I/ H. W# o) |# U - 递归终止的条件,防止无限循环 0 k1 n3 X9 L# \4 l2 C( K - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1 6 e. G# [' k) s6 s. u% W! z/ |) o 7 i8 v: D# V% }# D2. **递归条件(Recursive Case)**; T& I+ F9 X0 z+ N# U) j- { @
- 将原问题分解为更小的子问题 4 N3 ^$ n4 i& r" O - 例如:n! = n × (n-1)! ( ^3 a, e! w: t) C# K" I0 C$ ]" \+ {% i- C0 s4 z5 n
经典示例:计算阶乘! ^4 j) n/ a1 D3 L5 C) Z. {7 Z i
python & \1 i# d! k! @: Z8 B6 Xdef factorial(n):+ t e% X8 E% U8 ]* W% L- F
if n == 0: # 基线条件 ' I9 H* @$ `) [2 s return 1 ) ]. F6 w" D2 w else: # 递归条件 - _, L0 A& }" `% w return n * factorial(n-1) 2 A* ~* g) ^, }3 v执行过程(以计算 3! 为例): 3 z# W9 ~9 f$ E( B( bfactorial(3) 3 e: Y% ]0 h3 \( E E4 S3 * factorial(2)# c6 [/ u0 e( n1 O
3 * (2 * factorial(1)) 6 ?8 P$ E; I! S8 X3 * (2 * (1 * factorial(0))) - U2 J+ D' V) S* m3 * (2 * (1 * 1)) = 65 R) a2 i: P3 u/ |5 L( V3 ]2 R! X
1 m9 ^+ ^- @0 e+ A4 X
递归思维要点$ d" D5 F0 ^. C$ x+ C8 ]% U2 O4 Z" K
1. **信任递归**:假设子问题已经解决,专注当前层逻辑% h4 y8 s0 I8 b% M R, q: l
2. **栈结构**:每次调用都会创建新的栈帧(内存空间)+ R* Q. s9 h+ Q) i5 D9 v7 m
3. **递推过程**:不断向下分解问题(递) 5 X. D. W8 O0 A4. **回溯过程**:组合子问题结果返回(归) & f2 }+ s3 j" ~! n6 p9 h / V1 d/ e7 Y3 H; V, x 注意事项, @; m' E$ z0 D
必须要有终止条件9 z- ~- V- j9 s; c& }
递归深度过大可能导致栈溢出(Python默认递归深度约1000层) 8 Y6 c4 q6 t' e) G8 k# L% o某些问题用递归更直观(如树遍历),但效率可能不如迭代) p* x8 w ~$ i, c1 X) E
尾递归优化可以提升效率(但Python不支持)" u6 e6 Y' C2 U0 |$ [
8 m- G2 A' H+ G1 G- v3 P5 S. g/ k8 U 递归 vs 迭代7 V; l: L6 B3 R, ~4 V: D
| | 递归 | 迭代 | 4 ~+ _. Q3 [8 j+ B& ?7 m8 c, ?5 F e|----------|-----------------------------|------------------| # o3 X1 z( G; P* K3 d& e) M- s) _| 实现方式 | 函数自调用 | 循环结构 | 7 Q( R Z+ I; m% q, B. J2 O, Z| 内存消耗 | 需要维护调用栈(可能溢出) | 通常更节省内存 | - w/ ]) ]# `( Q0 ? Y! ]+ D| 代码可读性 | 对符合递归思维的问题更直观 | 线性流程更直接 |1 J+ X- O# {" {
| 适用场景 | 树结构、分治算法、回溯问题等 | 简单重复操作 | 2 x# S. n2 p ~% p8 t i0 a0 d6 A- a4 Y3 X2 ?+ K$ B D; F Q5 a
经典递归应用场景 7 B7 Y% s( D+ b, p1. 文件系统遍历(目录树结构): |. B w* p3 H& z# q) u
2. 快速排序/归并排序算法 0 s: s3 X# z& c3. 汉诺塔问题% a2 z+ I/ P9 y& X$ G! Z
4. 二叉树遍历(前序/中序/后序) ' J7 I7 ~$ {3 I5. 生成所有可能的组合(回溯算法) & M2 l0 N& \2 x( e ; e2 h* R- d: m/ h试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,/ W& g" d2 o- L9 v# g5 L
我推理机的核心算法应该是二叉树遍历的变种。 ; P0 ?. y) q% d( f) P. i3 ~! 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:( K% I: H) h" u7 X
Key Idea of Recursion, m) W/ i- e$ p& ^9 s2 J4 z
1 G+ Q8 a# ~! j( N8 }) K9 G+ v
A recursive function solves a problem by: - C) u" ?0 N7 |, C4 o 6 G2 T1 z1 S J& G- H. i2 F Breaking the problem into smaller instances of the same problem. - S9 w; B; {2 Q3 @8 C) x7 {5 L$ d/ _
Solving the smallest instance directly (base case).! h) K- i6 r* x7 g- I/ _0 w
9 ]( |6 \0 B+ R w2 t( e Combining the results of smaller instances to solve the larger problem.& Z2 i2 N: j% a1 A" A0 z1 o C" N3 Y
( L1 n, }' m) [/ L/ x# G& qComponents of a Recursive Function % q. x6 ~4 r" G" T/ _ 3 }4 I o* R6 ~ E Base Case: 9 ?/ Q0 c5 e) \ 7 S+ j- c8 K! V; D3 |$ h1 B! W( F% }# H This is the simplest, smallest instance of the problem that can be solved directly without further recursion.1 L' f6 ?$ Q$ w2 R: C' P% k
/ D0 S/ @/ H0 U/ _3 M2 |% \ It acts as the stopping condition to prevent infinite recursion. . W' `' m! v$ N9 K( Y& P8 h. u/ g) w$ s" @) ?; x2 z3 m" q) Y
Example: In calculating the factorial of a number, the base case is factorial(0) = 1. 7 s, z) ?/ d1 ~) K' S) j+ m4 |: \) ~* L4 t h. U' W4 Q4 g: w
Recursive Case: , _9 H. @$ C1 h' Y% Q; V1 D y6 O r5 F5 _4 Y( _& X3 k8 F( D
This is where the function calls itself with a smaller or simpler version of the problem. ; e8 M1 j* J# U& m0 m% i/ G) q5 U( ~
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).2 v+ M% \7 J4 z' @% ?, K. R6 F3 Y# p
. H8 q. y! E5 [& ~* U& T1 |Example: Factorial Calculation . A+ G9 V! J) a* N7 v: U6 `, |) m Q0 l8 N( e' f" \* RThe 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:( [& a ?# m0 R: x( j$ y3 {& J% \
: D! `9 u. e7 @4 ?2 r5 p" j Base case: 0! = 1 l: m5 I6 n' S2 t/ _
* s5 x8 i% O/ I! B. d2 j# e) u
Recursive case: n! = n * (n-1)! 8 ~+ u* |9 L4 J* O1 o/ ?. W F0 A6 S' n3 G+ x1 S3 N
Here’s how it looks in code (Python): 9 D7 K4 \ I5 y+ P" A& F+ m; epython 1 x# U, |0 ]# C" X 3 h: w$ C/ h: ^ 7 j( t" T; n- g: Y- Vdef factorial(n): B% |3 `. X( F% C
# Base case & e% v1 z! b9 |/ ~2 ` if n == 0:4 b: n# K( j' v/ v0 ]
return 1/ O: g5 H9 l2 T' e, A' ^
# Recursive case / u+ K6 r! p- r else:7 r/ n: F4 [: `8 |# }; \# D- [
return n * factorial(n - 1)2 R1 X2 P6 c( D! k$ r5 i' O, [
1 M1 n |1 ^( d' I! v& C
# Example usage D" k, i! J5 v9 {" N; vprint(factorial(5)) # Output: 120$ x& t/ z; S6 V4 f* h9 o! o( B8 V8 I- Y
+ F- {+ P2 ~" W+ G3 D
How Recursion Works - o# Q8 Z! v' Q2 q( |4 G0 T8 U% _0 c1 E, X" b
The function keeps calling itself with smaller inputs until it reaches the base case.1 H7 N4 Z) |* k/ b
; u/ j) y& g, H" o Once the base case is reached, the function starts returning values back up the call stack. 9 e/ N; H) ]. Q% j9 { % K8 g( w, L; t0 ~ These returned values are combined to produce the final result., o" }" g9 F* Q8 r
$ V5 y/ |$ A0 e' b. \- qAdvantages of Recursion& s9 }6 Q$ C1 k+ z- Z+ A
' B& M6 d+ p3 g# @; y3 |6 K: W! c
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).; {7 n$ T9 l( r
& N/ d& l9 x P" c' p- O% ]
Readability: Recursive code can be more readable and concise compared to iterative solutions. , }1 J! e0 t B3 {& [8 Z/ ?, t: ?) c2 s3 x2 k+ G/ v
Disadvantages of Recursion0 [: J. Y5 ^0 {2 ~
9 b; ^4 E2 |* l; J" k; t- s 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.3 `2 p) n1 |( `9 P) Y2 b
& ], u# ^0 Y& U8 }2 A# l) l6 {
Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). 2 i1 ?% @4 P* r' Q( l7 G: ^; K7 e
When to Use Recursion. d' i9 n; N! ?4 a0 f$ G# F
9 d2 r4 j" H! @8 y( G' T- A Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).5 D% ~8 A. L0 U2 s
' e% U, M+ M9 W# j* B/ @
Problems with a clear base case and recursive case.+ X/ f7 J# M: m. P
+ J9 h6 {7 M$ o+ ~6 V
Example: Fibonacci Sequence6 q) e: }! C% ~ Q5 G. g3 F1 _
; p0 x) R# m1 O8 }3 |The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:9 r, E' a6 U( n9 `4 Z
9 G" p$ h3 c! B C
Base case: fib(0) = 0, fib(1) = 19 f2 L8 c0 F9 V( R; H
' h. L7 F3 ?" M8 G( J8 F " K# y( I H6 ?, O) d: G% qdef fibonacci(n): $ u* I8 H0 I6 _ # Base cases7 r4 A, k" q) T0 \
if n == 0:( L W# A) E, r7 @; F. ~( Q
return 0! o# J& ?/ p3 B' u5 V3 W
elif n == 1:# i+ ~4 D' {$ e
return 1 ; o" B8 b, P2 o/ l # Recursive case) J9 I) k/ h' c/ {
else: b* P% I6 w# n! o1 U4 o7 s return fibonacci(n - 1) + fibonacci(n - 2) 8 ^* r0 J; x/ |4 u; n6 b% ^' s9 S2 p- P( w' `
# Example usage + f( `+ s& e2 ^9 Dprint(fibonacci(6)) # Output: 8 3 ?& {# ]% S3 r7 {. [ # P0 U3 X8 F: f/ e- `' e- eTail Recursion 6 {5 {: p# S/ B: Q& ] , `' b# R( D% C8 U9 {! l2 DTail 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).3 N" r% W" Q4 U! m
! W. @8 T3 [- D9 n, a& MIn 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 现在的开发流程,让一个老同志复习复习,快忘光了。