9 L' w6 W% H( G/ m" ?2 r试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。作者: testjhy 时间: 2025-1-30 00:07
挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,! s1 R9 A! r- v3 A/ C+ o5 w. s4 a
我推理机的核心算法应该是二叉树遍历的变种。3 C+ c3 k N$ f) Y
另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:, F8 s9 S8 N- g
Key Idea of Recursion2 b6 H# F9 a! X. V; r& z
/ q7 P4 R; \, a/ [; DA recursive function solves a problem by: r4 ~- f: z. ]7 a 1 c, w# q; t4 C. ~" G Breaking the problem into smaller instances of the same problem. ; x- @5 ?/ b1 R+ ?( Q4 d' z. C5 k# k
Solving the smallest instance directly (base case).5 d' D2 v8 d0 @, k
/ d& ?* F: R5 d% @6 ^ Combining the results of smaller instances to solve the larger problem. 7 i* K/ H& X5 C) z2 b6 o3 U& F ) e2 P2 r7 T4 yComponents of a Recursive Function & q$ k: \) b/ o( a3 I$ U6 ^& x . T' \- H. B E# B& b2 ~$ C: g Base Case: 5 v- \' Z; y- M1 \0 ~0 ?" b/ q; ^8 e* B4 y9 c
This is the simplest, smallest instance of the problem that can be solved directly without further recursion.% c, t: O5 u5 I
* S4 _7 }5 ^! X1 ^; X2 f$ Q
It acts as the stopping condition to prevent infinite recursion. 3 t Y: M m5 L+ A5 p9 Z' T( H/ X % n% i& y# F7 Q( K' G2 \. g$ o Example: In calculating the factorial of a number, the base case is factorial(0) = 1. # ^) I$ `' h$ l6 c " e( ]; L6 t1 J7 z# R" ? Recursive Case:+ M- x; ?9 g! D* E2 k
6 [8 x& ?; A, C S/ ?) ]; T R This is where the function calls itself with a smaller or simpler version of the problem.* C. C, |% t1 w& g) B- z
" k* T$ ]- d. ]; e1 u
Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1). + T4 z5 ~1 E% o4 `% U9 N* C; y1 Y) L% `3 ~: _% s( A
Example: Factorial Calculation * |0 V+ W5 L# J H. \2 p2 a ^ l8 M8 I5 N7 n! T1 Y$ XThe 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: 3 N2 W) g5 j4 V+ |" u* B ) c9 t, E5 p3 c Z Base case: 0! = 1 3 [$ X) s) D: F" S2 a: L1 V% c6 ^& I1 N: z- J2 \* Y- P! R0 B
Recursive case: n! = n * (n-1)!" R! W1 ]( Z) a# [
9 o4 V! _# Z; v" D# \4 HHere’s how it looks in code (Python):; V, B8 a0 c4 d& o' A
python $ ?" z6 {" W* k" O: A7 L4 `$ G) P4 N" P$ T. J$ F1 u
1 H( W' p1 G6 x$ t. |/ }) i; \
def factorial(n):; A# S8 F( D! H
# Base case & h/ A. ]3 |# \ if n == 0: # y. h, j# g; @+ I4 S return 1 % b1 J; F: B Q0 A) x # Recursive case 9 n9 i9 b! a; y4 i. R7 i else: 4 q* _" g0 Y8 _' S( ~( G% a0 b return n * factorial(n - 1) $ H. Y+ }# {* v+ }8 b. Y; u . X- r4 Z& _% ^; m+ i0 }& R# Example usage/ U. M" W3 ?: d4 @- F# [, c
print(factorial(5)) # Output: 1207 ?9 V6 o5 \9 R$ M; u% k( M
* a/ N0 c7 U vHow Recursion Works 5 v/ _ z8 R7 F' f R: s, D4 `& a( x - o. d4 ?8 |5 B0 o7 E5 m. ^- \ The function keeps calling itself with smaller inputs until it reaches the base case.' K. [( Y% _* l5 _5 {1 f4 B
w7 y9 H7 x4 G$ @. E) I. p Z Once the base case is reached, the function starts returning values back up the call stack. 4 q" q9 n1 ~4 O! P: w& W4 L1 Y 6 d: d: y4 e8 ]$ m These returned values are combined to produce the final result. ; A# e. v2 q5 ~ 8 @& w6 H, D8 F& p4 s0 V, KFor factorial(5): - {+ L. @7 q& z$ J: K; Q9 t5 v. t4 s$ m
& M, L4 I: n, V3 ?: M" W1 g) t$ Ffactorial(5) = 5 * factorial(4)/ m! _4 j2 P4 r" \3 a
factorial(4) = 4 * factorial(3) : V; U* c9 k$ u, f* M1 M; n5 ffactorial(3) = 3 * factorial(2) # `% L- B9 n6 S" X5 r$ Cfactorial(2) = 2 * factorial(1)2 q4 _; o) x8 @3 u v1 L- N0 _
factorial(1) = 1 * factorial(0) : M; d) c0 U; M' g7 m2 O7 yfactorial(0) = 1 # Base case ! u5 o6 O, D+ M5 ]) ?% W7 i " r# k" _$ b/ B/ G; E+ {Then, the results are combined:4 ]+ w: h$ K# u
, p. X+ O# Y% N) L; {& { M1 P2 e$ Z" ]% Q2 @1 Z
factorial(1) = 1 * 1 = 1 + G8 W! x% Y: U4 y. h# L0 Dfactorial(2) = 2 * 1 = 2 ( D( e. F8 v: _3 V- y* efactorial(3) = 3 * 2 = 6: e. k$ }* m/ [% W6 W7 B3 }) l
factorial(4) = 4 * 6 = 247 J9 ^: z* n. w0 o2 n0 |- z
factorial(5) = 5 * 24 = 120 + ?, r! h) ?4 m ' C; r' g# U- d& k% N- SAdvantages of Recursion7 C$ a! Y2 {0 T5 r; ~1 J% Y
2 {, K- f7 @& L
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). . _0 n' G2 S7 h* }4 E8 { + z2 T- I; d( T8 d3 H Readability: Recursive code can be more readable and concise compared to iterative solutions.% l. x6 j7 v3 ?' D, [+ e0 i
- e3 R: G5 l& L2 N; [Disadvantages of Recursion ' n# J9 o& P9 I {" H ( h& [2 K8 }! ~% Z- @ 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 u q1 H" i! _8 o8 e 6 l; r2 T; b" c6 e5 [ Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization). * U" ]6 }/ }: y7 e7 o5 L5 f: N1 u* o9 g6 ^
When to Use Recursion ; f+ ~: \0 N' w! f4 _% e- e - P3 D8 w* F3 b( B$ W& N( W Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).4 W$ X9 b. n+ I
/ F& z7 @& w$ F Problems with a clear base case and recursive case.3 V9 l2 X. X/ \
, h3 t. \- q+ p+ v }5 ?4 G
Example: Fibonacci Sequence 9 y/ U; X1 W+ |) [6 {& m0 J2 |" g' V6 |" I- g
The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:2 O& [$ ~6 K( f! h% K- ?3 x! o
2 o. K. `( p. g2 s! g/ P Base case: fib(0) = 0, fib(1) = 1 + N& x( c; N( D9 ?) J * L% t" y6 X" h' d$ r Recursive case: fib(n) = fib(n-1) + fib(n-2) : Z; Z: p% l0 i! C6 @4 p ( j( u' H- e- t" _python 9 }1 G1 U* P& q" R D; P" a1 b9 Y0 `# Y @. O
4 b# ?1 w+ K0 ~. T, |- P$ j" Z
def fibonacci(n):7 B$ |! B7 X& t( R5 W& j' |9 ]
# Base cases p2 |; a6 ^ E- `% p+ k" h if n == 0: : ^3 E% _* b% [9 y. S return 0: T% r8 A, H/ w9 l U
elif n == 1: ( ~% \) k9 g) `% h: b( W& ` return 1* R& q8 U( }) |5 }/ t# u
# Recursive case - r6 y( L9 @$ g5 J6 U* [" u# u else:. u# \- F: T6 N; j2 [2 s6 s
return fibonacci(n - 1) + fibonacci(n - 2) 1 C9 |$ `( ]% g- u1 ^) P: t( b3 |7 g9 I+ _+ s
# Example usage 1 }! v1 Y% {) Y e) @/ o$ V. Y. Iprint(fibonacci(6)) # Output: 8 ' a; o( L7 t8 i% ?, {+ j4 U* _% c0 N0 ~; o L- [
Tail Recursion7 g# q( V8 {+ ^. A: |& F+ s1 S
0 H: ~: }. R6 k e9 A, H$ O: CTail 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 }; W( o6 a, F$ g2 z
% L& o3 k: I# B$ s8 r
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 现在的开发流程,让一个老同志复习复习,快忘光了。