设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 3 h7 y$ l; T$ U! D

    . G( o2 [- @9 x& I5 I( L  V% n, S解释的不错
    , [0 W, K0 p1 }9 @
    4 F" z+ E' V8 v6 O, K递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。; L' d" c8 \2 z( ?* n

    4 S- ]6 x$ |: |7 w: { 关键要素- B1 S! g; {2 _
    1. **基线条件(Base Case)**
    + J4 a2 u5 V, T3 w+ V! W% n( j   - 递归终止的条件,防止无限循环
    ) V+ {1 `0 o7 ^4 ?   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 16 s7 L- v9 o2 p4 E4 ~5 s# X. q
    5 s+ b" f/ P& ~* {$ [3 _9 R
    2. **递归条件(Recursive Case)**8 k6 T' |4 d5 C8 k% i5 R
       - 将原问题分解为更小的子问题2 k+ H/ K5 [% @% i/ C0 N7 Y! i
       - 例如:n! = n × (n-1)!# G) n$ w" P4 Q& o* y9 ]

    / w; u0 x9 e* w* g7 B3 X. j% h8 u 经典示例:计算阶乘
    9 j  s0 c# s9 O- x2 q" @python
    % B, W; k) F; `  t8 L" W5 g0 W2 mdef factorial(n):
    / U- L; K3 {- Q# M; n: f- S    if n == 0:        # 基线条件
    ! b" q& h0 o9 ?' o' t        return 1% B- Q* B2 j: e2 u4 d+ j
        else:             # 递归条件
    7 l9 [2 `: z% M8 x. y" t2 Y- ^        return n * factorial(n-1)7 d2 s4 X/ T. i4 `4 b* S' _
    执行过程(以计算 3! 为例):9 U7 e8 Y1 G: r! Q$ @: u# d
    factorial(3)
    * _7 @% c! i( s3 * factorial(2)6 n  D! |6 P# ~9 d' I1 A
    3 * (2 * factorial(1))+ i1 n4 s( w" V- [# j; H
    3 * (2 * (1 * factorial(0)))2 I% O- ?- K9 X3 o# ]% T  m8 c
    3 * (2 * (1 * 1)) = 6
    7 a) x1 w8 \) O% z# p0 a/ y  a) L- N
    递归思维要点0 P6 F5 U+ z9 v9 T! p7 r
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    8 W  Z5 u1 H) L6 N0 I  L( h- M2. **栈结构**:每次调用都会创建新的栈帧(内存空间)# h$ P1 W2 I( W% d  d
    3. **递推过程**:不断向下分解问题(递)3 B" N/ }/ B+ U) w- L  d: y* P
    4. **回溯过程**:组合子问题结果返回(归)% @  _+ l. ~' z& X$ C
    $ I8 n+ ^4 A) z* W
    注意事项
    ( O) w. ^3 {8 ]9 @必须要有终止条件
    % x% o, k5 |1 c6 S3 u递归深度过大可能导致栈溢出(Python默认递归深度约1000层)/ t8 [; F; A# z/ m; _: j: X
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    * c) w; @; P; m# y尾递归优化可以提升效率(但Python不支持)3 q( b2 J9 @' T' [

    4 e0 [$ b. J+ s4 h% S1 \+ y 递归 vs 迭代! K& R( g, k' E9 G# B& I3 f* C
    |          | 递归                          | 迭代               |
    2 E# E# ^4 f" Q: `3 r/ d& t$ a5 v|----------|-----------------------------|------------------|
    , ~1 y  B' J5 |+ i, d| 实现方式    | 函数自调用                        | 循环结构            |9 q) e/ m( Z6 T5 Q  r7 v
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    9 {* ?9 {8 r+ c  x9 X| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |5 U2 d  U2 z9 e) U4 i. D1 {
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |" e- C  x0 m' W
    1 s9 m9 O( T( b9 I; j: k
    经典递归应用场景$ }( J0 W1 d* v8 ?# i9 ^
    1. 文件系统遍历(目录树结构)6 W  J9 S" D3 P& L! L
    2. 快速排序/归并排序算法
    ) U$ \0 r9 M( R, \8 n4 b' Q3. 汉诺塔问题
    + L! z' v7 O- L. x4. 二叉树遍历(前序/中序/后序)
    1 I5 y7 s* C( M# f5. 生成所有可能的组合(回溯算法)1 l' ^, \/ L& b. d

    ' N( T9 p5 f& L! V* S试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    慵懒
    8 小时前
  • 签到天数: 3112 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    / @; F: ?6 @* C* u我推理机的核心算法应该是二叉树遍历的变种。
    7 Q( p9 A  h" C" J( r( N另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:# T2 v5 S! m; o+ k- @3 }
    Key Idea of Recursion
    % U7 o/ w8 ]' G& ]( Q6 L+ E' _! r) b  r; x% L0 g$ K
    A recursive function solves a problem by:) z# @" p& x, y; q( c4 H' t; p
    4 {- m  l  Q- F' Z. }- C
        Breaking the problem into smaller instances of the same problem.
    4 i9 i4 K: ^4 J5 c. G3 d. C; b% z
      Q9 _0 j4 c, z  L8 i  _1 n    Solving the smallest instance directly (base case).
    7 }9 u  q& I4 c
    5 i( k& b5 T" ]% c' b7 V    Combining the results of smaller instances to solve the larger problem.& l5 o* o0 M7 J

    ) d/ E% @( [9 u7 Z- H: _3 SComponents of a Recursive Function) l) R' a$ I9 k7 ~1 l

    1 N1 u: f. ^& N. p$ w( N    Base Case:
    1 J) s( H4 d% m/ R' X1 Y" ~* ^8 L) b
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.0 W3 a6 ~5 A; W

    5 q2 h9 I# s' a: a7 H: m0 |        It acts as the stopping condition to prevent infinite recursion.
    1 E8 j9 O" H( |, K; ]. P. H9 x
    8 N% z' g7 s* M$ A" x        Example: In calculating the factorial of a number, the base case is factorial(0) = 1./ d5 O" p. m, z4 f9 i" F1 U' w1 F, M
    5 w* U7 I0 U+ {
        Recursive Case:5 t! {; |2 d. Z3 v, U3 [
    : ?7 Y9 o8 C8 g/ z% q: i
            This is where the function calls itself with a smaller or simpler version of the problem.: Y  G$ d: o  \) ?- A

    $ t' B. _$ h- I  t; Y        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).# B) R! N' B& ]: @

    ( [* \; v0 s( w& z% U+ KExample: Factorial Calculation5 d  g, `) p! f2 B7 u5 B& k' R

    1 O+ g3 C" z! p! y4 T% U0 C" }1 t" ]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:
    # s  K- h, _; D. M# E; Y
    4 T# D  o* ~6 U; Q% Y( `7 b0 v    Base case: 0! = 1% Q: `# G: E8 _% x
    2 s1 I6 K1 I: s& O0 a. J
        Recursive case: n! = n * (n-1)!3 z4 ~  Z6 @+ u8 U  D

    8 V( q. a" @9 b" k0 T) ~Here’s how it looks in code (Python):
    ; I' P$ n8 L6 S9 D0 o3 O5 _python: J+ @/ y7 ]9 \  v  L

    " I/ a) ?6 g+ g, c/ N9 K
    : Q& q9 C' O8 u( R& t0 n; ndef factorial(n):
      a  Y8 x, b# x' i& Q3 E    # Base case
    ! [/ h9 v$ O2 T9 {& X; j, J    if n == 0:9 L% V3 M3 h' F
            return 1
    % U# L' O0 S6 Q6 a7 _" }4 T    # Recursive case
    4 s4 E  W5 r5 {) u    else:: U3 N5 G- I( g9 [0 D8 n# d7 m
            return n * factorial(n - 1)) \, N  i4 `* \& N7 m, V
    # e+ K. N; K2 E7 d. g
    # Example usage
    : c: u0 w9 D5 x1 p. c5 P5 \print(factorial(5))  # Output: 120
    1 S5 ]1 ]6 i: d
    ) {+ `+ \; W: }- DHow Recursion Works) H, W. f. z# ^. {1 K
    ' o& a9 M0 i+ H2 ?, `3 N
        The function keeps calling itself with smaller inputs until it reaches the base case.
    6 f% I$ Y" i: p0 O5 ^/ F# o
    0 S" ^& @8 y7 w; f    Once the base case is reached, the function starts returning values back up the call stack.
    8 J& J5 A& @* h2 `# a4 Q9 M" A" r5 r$ u1 m9 l, n  ]) J
        These returned values are combined to produce the final result." W% f: _" ?. w& c8 ~' w1 \

    6 y4 `% l8 v/ \, R4 QFor factorial(5):2 _, I5 d* Q$ z4 @  `, ^
    + M5 m& ^1 U$ ?9 [* f: @

    4 H; q, X  z  g) afactorial(5) = 5 * factorial(4)
    6 U: q) g3 X( R3 }& wfactorial(4) = 4 * factorial(3)$ p: m# P9 T6 c
    factorial(3) = 3 * factorial(2)
    - L' B4 B, g" H; M) B1 z% \1 D& Xfactorial(2) = 2 * factorial(1)
    5 l! e8 w) I, N1 u4 d6 \# ^factorial(1) = 1 * factorial(0)$ E! o8 O. ?5 `, e# |% k
    factorial(0) = 1  # Base case
    * b) L) c, X  t6 ]- e& |( d+ M! P* I( `8 M2 D
    Then, the results are combined:
    8 n6 v0 b* i# S3 i; b/ h
    % n  r! `; ?+ Z4 ?0 }: O' O
      m/ w2 P/ u. [$ H- B4 rfactorial(1) = 1 * 1 = 1
    ; V; ^$ k- K8 Z+ q$ }1 Hfactorial(2) = 2 * 1 = 2( G' @4 G# U: O3 v, W3 J
    factorial(3) = 3 * 2 = 64 T+ G  y: o  i' r1 Z( d6 B& h$ l& v
    factorial(4) = 4 * 6 = 24# x6 M& b) H0 c) A2 ]0 y
    factorial(5) = 5 * 24 = 120% I8 c1 @" }1 e1 k0 w3 H' N% h

    ! q8 q. P: H+ \Advantages of Recursion
      [: V8 j# n& E- H# Y' E4 S% Q8 D8 ~( h
        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).
    3 d0 i  u- Z( M5 |; u5 g3 I7 P& X4 B- S* g( S
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    6 P3 J# A/ b% N3 q3 V4 G3 b
    6 t: @- I8 G5 x. T8 I3 E5 wDisadvantages of Recursion
    9 d) b7 b: R0 p' ?0 J3 \  m! K( ?
    # d+ f+ n2 I7 P0 O% G    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.* i" t" T0 {* U' p4 f: s

    / }; z, N7 k! }" j    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ' _- @) q. @) J
    " n2 g% W2 H  x$ K3 N' ]  T' U- HWhen to Use Recursion
    ( `9 f! {5 J2 j- w7 e) ~7 ^6 R9 {6 M8 f7 k$ o  V
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    % n1 s( [- m# m# Y9 P1 m" t
    ( k/ S/ a- e- B5 d- Y% Y    Problems with a clear base case and recursive case.( Y$ n% @) {- q) s
    3 t+ |  V: g) G+ d
    Example: Fibonacci Sequence' I, Y( O) }8 n9 W( H( H

    0 z/ w" b! o. s+ J7 ^% GThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    8 d' B3 _; w8 K" B& l4 W. j2 p) B& w* }. {% h1 b  h
        Base case: fib(0) = 0, fib(1) = 1) m; u. x& {1 P, @  n+ P8 P' D3 N
    3 a* e$ u: Z* Y% P3 H7 g, _
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
      L; ?- q1 q) f% w2 z, q
    ( h8 E6 c9 d! Hpython
    ' Y6 v6 H6 _% |1 M( e
    * D5 L6 a1 Q) K! x9 r  w/ D) b+ Z  F5 F
    def fibonacci(n):5 Q( B+ F& t4 H0 P
        # Base cases* }: W. p, u$ h
        if n == 0:+ R. r( u# Z8 K# U, J7 L
            return 0
    ; A* T4 ^/ V$ S- o. Z; `# ]9 t# L- E* m7 ]    elif n == 1:. Y& x/ t0 j& G- U/ e5 z' J. V* K) P
            return 1* n& G' k. P4 e% S3 I: E8 C5 r
        # Recursive case# d0 ^- m* o  P5 s
        else:
    % x* q' ~+ c8 T+ b; K        return fibonacci(n - 1) + fibonacci(n - 2)2 q' `! d# _/ Q" I$ |  {1 c

    8 G' s4 ]( n/ [& n$ P8 D4 _1 }# Example usage
    % x" a' ]; ~$ {print(fibonacci(6))  # Output: 8! F8 e6 k8 ]! J

    $ f0 C$ l6 L3 ~/ x- ETail Recursion' u; @! t, U3 H6 S8 L

    ; n- n; ~" l% J9 |5 eTail 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).9 j8 M0 ~! D1 K1 P/ P4 ~& A1 I/ J
    ! Y4 h4 W/ }8 h6 e1 K6 O
    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, 2025-12-8 16:00 , Processed in 0.039195 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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