设为首页收藏本站

爱吱声

 找回密码
 注册
搜索
查看: 2142|回复: 3
打印 上一主题 下一主题

[科技前沿] 突然想到让deepseek来解释一下递归

[复制链接]
  • TA的每日心情
    开心
    2025-9-8 05:08
  • 签到天数: 3 天

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ! [1 p$ o9 z4 f3 h* m' T
    + G2 ?$ w$ S2 _; c/ l/ V* L解释的不错
    # ?* {5 q& N3 K/ m2 R( e1 P* W: Q$ f: P4 ?
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。  z$ W* F6 j3 J1 }7 W: ]

    $ u: s* K' B# H% Q" g 关键要素
    " x& [& K( K- ~8 D1. **基线条件(Base Case)**' Z0 E/ N' P0 ^5 {/ x1 m
       - 递归终止的条件,防止无限循环
    ) a& Y  _! j* G. N. [% Z   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    ) y" p3 t: v# m3 e
    2 z0 x' i" N& }2. **递归条件(Recursive Case)**( ~( D8 R2 s- B2 h
       - 将原问题分解为更小的子问题
    + Z4 ?2 Q1 G6 U   - 例如:n! = n × (n-1)!/ N( ]' n8 Q0 `) z; F8 l

    + H1 C: n, L5 @# r; y# Z, ~6 p 经典示例:计算阶乘
    1 L" ?. S* {- ppython" x# T9 s) ^1 {9 c% ^; h9 f
    def factorial(n):
    5 a4 O& S8 L- j8 s; T& S8 J    if n == 0:        # 基线条件' M9 r& F! S+ [5 m% L5 B) F
            return 1
    . h1 ?( i' l& ], V5 D( g    else:             # 递归条件
    / C4 h* h: K2 b  \1 J5 O        return n * factorial(n-1)
    . P& l- i; T5 d8 J! Y  x+ \执行过程(以计算 3! 为例):
    - |# g; p. A; b7 F8 F- v. @factorial(3)3 A$ c. h5 ?! X  q/ t4 n
    3 * factorial(2)
    / D: v% |% h7 D- E3 }5 e- l% _3 * (2 * factorial(1))
    * v& w; h: L: S* \3 * (2 * (1 * factorial(0)))6 t1 X2 Y5 |% s! V' k
    3 * (2 * (1 * 1)) = 6
    ; e0 J7 k+ W; E# V- _  k9 ^$ e9 W9 F3 A! _+ i+ B. {
    递归思维要点
    ; U; L" G& q) J! _: i1 A3 G. ~5 ?! ?1. **信任递归**:假设子问题已经解决,专注当前层逻辑. S+ U8 N- g1 l7 Q. E3 Z
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    0 \& X! n& x4 Q2 x3. **递推过程**:不断向下分解问题(递)
    : q2 W: b2 q( o* [4. **回溯过程**:组合子问题结果返回(归)
    " y7 S# [- i. X
    4 Q3 A. _2 |! v 注意事项+ h1 b+ Z- f! V* z
    必须要有终止条件
    6 a! S$ c. N5 b; n5 \递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    ' `" x5 r+ E$ _* C0 J" \! h某些问题用递归更直观(如树遍历),但效率可能不如迭代2 P8 }$ W" D7 u0 H+ I: ~
    尾递归优化可以提升效率(但Python不支持)! `* B+ _9 Y, e9 S6 C

    , [: q9 m) j3 E' D, i9 ^ 递归 vs 迭代
    - }; A9 [+ C% k. b) c# Z|          | 递归                          | 迭代               |
    ) H+ }9 _( E" W( H, F) M|----------|-----------------------------|------------------|8 J1 L! o) x6 I6 V5 \; Q
    | 实现方式    | 函数自调用                        | 循环结构            |
    ) t* A- X% h% h6 v8 s| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |9 K- }. V" v, R8 t7 u% {
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ) V; N; [! c5 I| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    : M  m/ |" Q7 [$ G- W- P# _1 Z6 d; [4 ]2 a( M, ~( _  j/ K3 h
    经典递归应用场景
    / D* X+ _+ h$ G! j- A1. 文件系统遍历(目录树结构)+ o7 Y" {) o2 W8 k7 I" G1 U' ~
    2. 快速排序/归并排序算法
    ) o+ U! w5 E* `& e$ k7 U$ t3. 汉诺塔问题3 Q/ }/ x9 L' I4 C3 b$ B# u
    4. 二叉树遍历(前序/中序/后序)
    ( Y  ~7 O, K4 n5. 生成所有可能的组合(回溯算法)
    6 E9 l5 t5 l( E, i- d. Q7 s0 D4 S
    ) R7 n8 Q1 n# U6 Z试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

    参与人数 3爱元 +26 收起 理由
    pcb + 4
    老票 + 16 涨姿势
    住在乡下 + 6 给力

    查看全部评分

  • TA的每日心情
    郁闷
    昨天 07:21
  • 签到天数: 3182 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,1 C5 Y& g# [* g; @
    我推理机的核心算法应该是二叉树遍历的变种。
    6 f8 X6 O9 E0 q7 u) W5 G另外知识系统的推理机搜索深度(递归深度)并不长,没有超过10层的,如果输入变量多的话,搜索宽度很大,但对那时的286-386DOS系统,计算压力也不算大。
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    板凳
    发表于 2025-2-2 00:45:59 | 只看该作者
    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:
    , t( |% |5 t2 @) j% K) ?0 vKey Idea of Recursion4 B. d, Q, H( r! f7 e- z$ z3 P# Z

    : \, }0 y! [/ L# F* z' i+ F8 F2 zA recursive function solves a problem by:
    7 p: P# L1 {+ y- G  B9 ]9 W' ?: U- O2 |' u
        Breaking the problem into smaller instances of the same problem.
    % L2 k- a6 m. g( y
    / C% E' M8 ?5 F9 e( K/ H" {; L    Solving the smallest instance directly (base case).& h, f3 {" P2 c6 y0 O

    * w; B+ Z6 s7 Q0 K6 n/ [; g    Combining the results of smaller instances to solve the larger problem.
    # ?  p! K' Z2 ?' b1 {- U6 b
    . v3 }" A4 s0 t' B. G( z6 M9 fComponents of a Recursive Function
    # N  q/ X: M/ O3 J' @* q* V, G% j0 M5 D/ u4 ]; u1 a4 O/ Z5 g
        Base Case:- _9 H! d8 r% m2 t" {; r; p

    7 W8 Q& j# c* Z- F* L2 @) @        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.# }5 T- r0 P6 ]" I! S: L) V8 o4 }

    1 x9 i" `4 Y# F. \4 G        It acts as the stopping condition to prevent infinite recursion.
    9 F! }7 h( \, M  `9 B" r% g; ^3 [6 o: ?- }
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.! R5 G& T9 [8 t) K1 c; Q" t
    3 {; T$ T8 P* s( [) H. u# o0 }
        Recursive Case:% ?, f/ ~6 I5 |. O! L$ @9 h* w

    7 P' [( r1 r2 ~! C% I        This is where the function calls itself with a smaller or simpler version of the problem.+ C# L* z' o3 v" D3 `, x

    " {& k0 `% J# V0 O( y. `        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    - p3 a# \$ o6 K9 p( t- d' f2 u9 R) [" W
    Example: Factorial Calculation
    4 I- \/ S8 g* \0 q2 r: \& C9 A5 Y  m. [0 T3 s) Y
    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:
    1 ]6 U# ^/ l6 ?# X/ |. a* e+ @* l& t4 i# Y+ N
        Base case: 0! = 1  t/ g! V) o6 `; C9 E; {9 O
    ) m- Y1 {: I: O/ n9 a3 H( s
        Recursive case: n! = n * (n-1)!
    8 e8 ]) `2 w/ i
    4 ?- z0 @1 y/ z/ K- sHere’s how it looks in code (Python):  T" e4 ~# x' x- v/ N- ]
    python
    8 x3 Y) d/ e; w4 A, H  {
    / W- {! ^, B  g& v3 F
    9 Z0 X% _+ Z4 U, _def factorial(n):3 W, S0 \8 _$ Z, e6 r9 h
        # Base case
    1 P8 D' \! _) ]- i# M6 h) m    if n == 0:
    & P. Y8 E3 U0 O        return 1
    9 \6 I! g6 D4 d8 p    # Recursive case
    4 v5 h+ z9 f- Z( t0 ]: s* }5 j    else:
    7 ]' J8 M3 L. Y9 z        return n * factorial(n - 1)5 Z8 j4 \, Q* ]) K( ]
    5 H, O' j6 O  p
    # Example usage
    0 O- ~6 t( w5 e* t1 O8 q5 fprint(factorial(5))  # Output: 120
    : \& L4 r' b/ ]1 p2 ]  Y- q, ~" R1 ~
    How Recursion Works
    * J* Q2 Q- A! U- j. P  D
    : j( G2 Y' n- w+ m3 p- s) E$ A    The function keeps calling itself with smaller inputs until it reaches the base case.6 K3 m' l4 q$ A0 |5 k( F0 `5 s; |
    % s* e, u4 o! b& \$ q; g
        Once the base case is reached, the function starts returning values back up the call stack., T2 w( n5 a' l' r/ s

    2 m/ g% W+ a0 r# B* |    These returned values are combined to produce the final result.$ ~- u! {. P' t$ K

    ' X6 Z: Q0 J3 J4 E7 x' SFor factorial(5):
    1 J$ V- e! ^7 n. r& E- r
    & l' ?+ B; a& B1 h5 h
      H- ?3 q8 r/ s. i5 |3 x# ?( q9 Zfactorial(5) = 5 * factorial(4)& E. o2 a3 M0 ]$ Y9 d- s) K6 K
    factorial(4) = 4 * factorial(3)5 k' n( x' r8 ^4 m0 j7 e
    factorial(3) = 3 * factorial(2)
    " p* y8 W' {# a- ?% Cfactorial(2) = 2 * factorial(1)  W9 u8 o# y) b4 ]
    factorial(1) = 1 * factorial(0)
    * S9 N, T( ~4 rfactorial(0) = 1  # Base case
    0 g# _/ h$ p% S& k' C1 y
    " F; j3 Y0 o6 k, E" GThen, the results are combined:5 ^2 q. x% N8 }$ D8 \# C) n- W4 T

    5 p* P3 R" q* d) c, K3 C+ o8 U
    , V, y7 i0 v% a) q: R% p' u! Q" lfactorial(1) = 1 * 1 = 1
    ' @5 w6 g5 d; z/ H  v+ V7 Cfactorial(2) = 2 * 1 = 21 u2 a% K* k) @' w& Y* P
    factorial(3) = 3 * 2 = 6
    ) g7 B6 r* V. x$ }factorial(4) = 4 * 6 = 24% u7 f# A% {! {: D  @" M
    factorial(5) = 5 * 24 = 120
    # J8 }' B/ Q# \( N( O" B, o5 O1 U$ ]" e: g  v: p( s
    Advantages of Recursion' m$ u1 l- I& d" ]- E+ E6 L; O

    : `" J; S, s0 r/ l  O1 ?9 `' R    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).9 A% w, `$ R% o( E
    ) u! ^* B4 {9 t; p5 C. @
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    1 w% }3 H& u: `6 q$ O% W. n$ L0 \
    Disadvantages of Recursion
    ) T- T6 q/ Y* F  r( ]$ Z) G, A' X( J/ l: j3 [$ |
        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.1 P' e0 I& o) y6 r
    * i7 l9 b6 v! j7 ^- _$ H
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).9 {' ?, ^6 G" A" [2 O
    2 I! v4 t8 n. i/ r6 m8 m, }
    When to Use Recursion1 y" p' b, `- C* n# @
      l  c6 S2 F, H7 @0 `' @  ^
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).7 |- [" {# F1 \1 N$ h

    " _. \; c! m% w6 F9 |    Problems with a clear base case and recursive case.7 u, @0 I/ Q1 u3 e3 g% t! w
    0 F! H0 T0 k2 O
    Example: Fibonacci Sequence
    7 D( \1 b) r% m6 ~! D6 m
    ) X* W5 f/ {  [0 JThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:6 ^% r! ^: O* |, S
    1 n. I7 ^$ W* ?1 d' n
        Base case: fib(0) = 0, fib(1) = 1
    8 [: d0 y  k, l/ i" t/ O# X/ X# s; K; p# Y- H" K3 ^9 l
        Recursive case: fib(n) = fib(n-1) + fib(n-2)3 |( a+ S$ |4 F7 I3 ^$ _
    ( B  m. u. v2 k, F( F
    python1 |: B. t9 G# t9 c4 ^- F
    6 l9 p" I" v9 w) ~$ ?

    / N+ P! Q' }6 b; u8 odef fibonacci(n):
      F( J0 T$ r8 C4 B$ Z+ U    # Base cases
    - ~4 Y1 w" f2 D# S# F% n    if n == 0:6 J+ e* h6 g  N& `! F. D& ?
            return 0* ?8 P, m  a4 l' m
        elif n == 1:
    . W  S9 E! }( c4 A5 H1 B        return 15 ^$ H8 f$ d7 l3 x
        # Recursive case
    + q8 `, D9 M3 a1 A1 D7 Y    else:
    / c8 I& P2 j8 O  F        return fibonacci(n - 1) + fibonacci(n - 2)
    / j0 B. h3 G+ q" ~' ]3 {* u& |& k
    # Example usage
    * a; u0 S* @2 }# @4 F; @, s, jprint(fibonacci(6))  # Output: 8
      l! {1 M% R8 Q' n9 C& [; D( a' A
    Tail Recursion
    1 X; s6 N3 K: i0 \" a9 ^3 J" K% F5 E
    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).
    4 Q5 d% y4 C5 G, F1 N2 R9 w) v. X: B; O& j% ]
    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.
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    地板
    发表于 2025-2-2 00:47:27 | 只看该作者
    我还让Deepseek 给我讲讲Linux Kernel Driver 现在的开发流程,让一个老同志复习复习,快忘光了。
    回复 支持 反对

    使用道具 举报

    手机版|小黑屋|Archiver|网站错误报告|爱吱声   

    GMT+8, 2026-2-24 02:55 , Processed in 0.060473 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表