设为首页收藏本站

爱吱声

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

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

[复制链接]
  • TA的每日心情
    开心
    2015-11-30 11:11
  • 签到天数: 2 天

    [LV.1]炼气

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 , m0 ~2 y# n' ]; t: K9 f
    * o4 _0 x; J; j
    解释的不错
    ' `8 J: k- r# M3 B, Q2 R8 }$ J# T4 G& B/ u8 {2 u8 X8 z3 x2 K1 c
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。0 S& N2 K( l* F% l. ~

    $ ~4 b% k" j. f" X. ~! ^5 `4 F! E 关键要素
    3 r' u( f& a, J* u1. **基线条件(Base Case)**4 B; K3 V# }" I
       - 递归终止的条件,防止无限循环6 P1 b8 n1 d' }  J7 U
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 16 _  v- N: Y! G6 p0 K
    1 X2 o( Z9 u; @, j
    2. **递归条件(Recursive Case)**
    6 |* `" \& i4 ?5 A6 O   - 将原问题分解为更小的子问题
    4 F# i9 J9 r, ?: h% O7 ^! a! U5 [   - 例如:n! = n × (n-1)!
    ) e- @" b+ v- p2 T" z+ g1 r
    8 d0 U8 O& e# ^6 N- e. p; W) b 经典示例:计算阶乘0 Y4 W5 j! o# Y# \/ `( C
    python
    ; X- y  X8 b9 K3 s" @( S5 p; Ddef factorial(n):6 S  S8 j9 Z/ r# w) J: F8 e
        if n == 0:        # 基线条件7 L! z0 {- v( s' Z1 b" o
            return 1
    . Z/ R4 _7 b) a3 g    else:             # 递归条件
    ( J5 F4 Z( z: x% \( r        return n * factorial(n-1)
    2 l$ B: l0 H2 @4 @( N/ B, u2 k执行过程(以计算 3! 为例):) \. i* M! p9 j0 f. y) _$ ~' u
    factorial(3)
    6 t# k- _6 \! x2 G* O* n2 q3 * factorial(2)& w  y5 H/ {0 k7 W
    3 * (2 * factorial(1))# e# Z0 x3 [' d0 a
    3 * (2 * (1 * factorial(0)))
      H& c, B" [  G: s3 * (2 * (1 * 1)) = 6
    ! q; ?$ {  V- A, Y; u$ X* o+ J& K9 ^6 f4 }# s
    递归思维要点, c7 T; I0 {8 F; S4 o
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑6 C0 e- ~, m* O5 G4 N
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)8 R; g' r/ J2 E( _
    3. **递推过程**:不断向下分解问题(递)
    3 h' u- _! R# |% I4. **回溯过程**:组合子问题结果返回(归)1 r* D/ B# s" p6 i  K
    , s- S+ v) d1 p0 k
    注意事项
    - E' L- H; e  C3 F必须要有终止条件
    4 \; D$ o, P: ]2 ^' K, I$ M递归深度过大可能导致栈溢出(Python默认递归深度约1000层)3 J, o" H0 C0 w3 Y
    某些问题用递归更直观(如树遍历),但效率可能不如迭代# }/ F3 q+ A1 }: V  P) K: q+ O
    尾递归优化可以提升效率(但Python不支持)
    6 E1 x3 J0 k! g* `8 i; }. b: c0 a' B8 P" z) ~7 N7 V/ f, Q! `
    递归 vs 迭代( C" j2 m; l. n% }$ G
    |          | 递归                          | 迭代               |
    6 e6 y$ K" ~* J' I! i0 ?) d! E( Y) o|----------|-----------------------------|------------------|' f7 T$ _1 t- p% W: B
    | 实现方式    | 函数自调用                        | 循环结构            |
    ! {1 B6 B! y2 ~/ r| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |- T5 d3 w# w1 \) u: D" j
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    & B, Z: ?5 t& e/ U| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    * T6 U3 _5 d( n* ^! E
    ' E! X/ ~- {9 I; G 经典递归应用场景4 c" A  P: X' s3 S# }
    1. 文件系统遍历(目录树结构)7 r% e6 C# G$ P2 S# ?, _. c
    2. 快速排序/归并排序算法: H% `( M2 D# g8 o
    3. 汉诺塔问题" G2 p) Y* W6 m7 |! g
    4. 二叉树遍历(前序/中序/后序)
    9 K5 n! w+ Q; a5. 生成所有可能的组合(回溯算法)
    0 c0 O$ h* j# U; T( m1 ^+ O) ~9 @3 h0 ?' E) k# R* h1 K& j) \  }
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    难过
    1 小时前
  • 签到天数: 3017 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    6 g5 D; X/ q9 ~" r) P5 _1 o  s我推理机的核心算法应该是二叉树遍历的变种。' Z7 m+ m! B: }. i5 V4 c+ b
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    $ S; `& Q3 p. V3 T3 s2 @2 UKey Idea of Recursion* N5 K5 P7 W, e6 x' b2 `4 E1 M
    $ u! b* w5 F8 F+ y
    A recursive function solves a problem by:$ X5 _8 g( e1 c- ]
    . y6 K$ R: L0 t6 f
        Breaking the problem into smaller instances of the same problem.+ f$ L. E1 l0 G7 T2 \$ \2 f
    8 K) Z0 M* r0 r, Q0 R' V! [1 L
        Solving the smallest instance directly (base case).
    ! d* R. l$ @6 ?3 L) w" L: ^" G* s" i" c2 A
        Combining the results of smaller instances to solve the larger problem.
    & S' r' e5 B9 U* L8 R- o9 U' Z, x7 W) M: T' ^5 L! [4 N' Z% x
    Components of a Recursive Function: F: @# M9 m( P

    9 S5 c8 o3 \( [, d1 l6 @3 ^    Base Case:
    ! `4 _' G% j! {. f3 e1 [' q- l% P$ g0 R5 \
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion." x' z8 r9 ^2 l5 j/ T
    $ f$ f( o3 Y! I
            It acts as the stopping condition to prevent infinite recursion.
    8 \8 k0 J- Q+ f* E5 m( A1 K* u2 s
    " i/ O7 }. s' j3 V  ?4 C4 c/ G        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    ( b7 }( @$ q/ g
    0 s8 R" t7 b, h& W0 A    Recursive Case:  P5 h4 T; j6 k5 O
    ! ]+ ^, \+ T. e) v& y
            This is where the function calls itself with a smaller or simpler version of the problem.
    4 A7 r( A5 Q7 S# |+ w& s# D
    : g0 M- a# `- `" m; r5 A        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    * h( R& B3 g  q: z: _$ h- s: Q
    % E0 Z  N9 C. h- J2 v4 ~Example: Factorial Calculation0 u" `6 y+ Q2 W1 B' e. T

    3 I. P$ I1 f2 M: q6 Z2 r: fThe 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:2 u& w" g, p% _( W3 r3 Y# _4 K+ l/ O
    0 _! f7 V8 U6 @7 @7 W% v% T
        Base case: 0! = 1
    2 @2 [* ~3 z3 ?1 ^. F& I$ a
    0 |. b$ L6 L2 u0 r2 s2 x1 f    Recursive case: n! = n * (n-1)!
    & x) m4 n; m& w7 K& I2 i: U1 o. k% q4 |
    Here’s how it looks in code (Python):
    ! J' ^8 Y1 G. @5 r$ i' ]python
    ! a' b* G% j) M$ }; f5 ~7 g4 Q, A4 K$ o3 g/ Q6 ~) e
    , @$ d- ]2 h$ w2 R4 g0 m* U  L0 G
    def factorial(n):; R1 Q6 B3 N+ h, h$ _
        # Base case. {& p# s" C& }( m; d7 m2 I+ D
        if n == 0:
    / z: B* v: }4 h9 J& }  C0 V- a        return 1
    + }; w( U$ U. U' M& ~    # Recursive case; M$ D8 k' Q6 \9 [* m* C
        else:& J0 J9 G# n: |2 J( m+ W5 d
            return n * factorial(n - 1)
    $ }4 {% p! z% O. R1 B/ b% f) G7 ?, J) ~4 S
    # Example usage9 V/ k5 R3 I$ b- A
    print(factorial(5))  # Output: 1204 D6 C& g# K) m" c0 }
    # n$ B4 J$ l4 G; _( |  }
    How Recursion Works
    & G, ]" Z# a+ w, o: V* K
    , k/ G) S: [1 j2 {, d- i' t    The function keeps calling itself with smaller inputs until it reaches the base case.! X, b6 J. p' m2 ?+ i
    % g  f: r4 A: j3 p* t
        Once the base case is reached, the function starts returning values back up the call stack.
    ; Z& M+ G, k% t9 ~; C% g# P! Y/ c# @/ F& _1 D
        These returned values are combined to produce the final result.
    ( `& w7 F$ w; _7 e. J8 |, t- ~; o5 s+ t# U
    For factorial(5):
    % n- ?- e# e$ L9 N4 L- b
    ! P- k- b0 U6 u* O" {0 S
    2 w+ n4 c, \! I$ b  ^4 H6 b+ N' hfactorial(5) = 5 * factorial(4)
    7 Y  t2 K5 E9 d9 |factorial(4) = 4 * factorial(3)/ b5 F+ V$ C& I/ K
    factorial(3) = 3 * factorial(2)' v6 @, [7 y3 E  d
    factorial(2) = 2 * factorial(1)
    ' H( N+ m( `- B/ ^: a0 f$ nfactorial(1) = 1 * factorial(0)
    ' e  k# w% v, T! n. afactorial(0) = 1  # Base case! p  n6 d% Q; j
    " m/ J2 C) L2 {5 h
    Then, the results are combined:
    7 N0 F8 |! K/ Q! U7 a
    * J: V+ t2 y5 e1 f7 y" j! |, u# t& d- @( c* C. E) _
    factorial(1) = 1 * 1 = 13 z4 x  |4 e6 B2 v+ b
    factorial(2) = 2 * 1 = 2
    8 e* R/ F/ I. p0 w! p, C" jfactorial(3) = 3 * 2 = 6
    ; W. u( V. }; V- o& Kfactorial(4) = 4 * 6 = 24
    ' q' U8 L) B- kfactorial(5) = 5 * 24 = 120
    , Q& h2 f  ^( W1 ]! A" `) b  d6 A; H2 {$ x& |- h
    Advantages of Recursion+ g/ b! R1 r& j  q7 E

    8 j; g* b0 y0 d4 g# F    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).# @1 A8 `) I1 w5 U% T
      a7 n0 O( r. `3 G
        Readability: Recursive code can be more readable and concise compared to iterative solutions.  ]5 x7 T' p. [+ O; x

    & I& t0 d+ ^8 E4 a9 j3 E  jDisadvantages of Recursion
    1 ]$ D: [8 L3 \7 U6 J5 `, v7 M, g* c. V" p6 B* E3 r
        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.& Q# o, Z- {$ P% f( u- u
    $ R3 H: c( h5 J3 v5 g
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).$ S& S. n& f4 [

    * }& j. u. w5 x, I: G; ^7 m6 BWhen to Use Recursion% U# e$ }2 {- e2 u& Z/ n

    & C) S# I. a# l9 R; X& K    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    * v; a0 }4 c& P$ ~. {, {! B+ Y% k
    / R6 J5 ^* X- D# ~3 M" k5 a# }' e    Problems with a clear base case and recursive case.
    : T  M/ ^: `# C, J4 ?7 Z
    * W5 G% H3 c% d2 T# wExample: Fibonacci Sequence
    8 n. a# ?6 @6 N) }; F/ ~; x+ [* V- I2 u! L. s% I: a* J
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:! G- b& a- w1 N
    + O6 _' x' o; C0 J" z% Q" I
        Base case: fib(0) = 0, fib(1) = 18 J* B( u1 F; c% i7 G- ~: o
    & ~- `0 P# s; P/ P/ g' g
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
      J) c2 J; P$ F, T$ m1 l- o# j) W4 F
    python
    : z8 R* f/ ^: |
    0 o0 l( D8 T* D% L4 d8 G* l" F6 n  }: m& X: @9 \+ f% J
    def fibonacci(n):
    3 F) [. u2 q% I- B2 l3 `    # Base cases3 O2 l; g5 e2 M3 m
        if n == 0:3 J9 G, F& @; q0 D1 `: M: t
            return 0/ ^7 _" S- L* A; r
        elif n == 1:3 p7 ?7 K$ }4 o: }# }
            return 1
    ; ^' ^4 q+ T- F1 [    # Recursive case
    . J$ k# V5 z, {, G0 G    else:# G, v8 T; `% o, S, c5 \
            return fibonacci(n - 1) + fibonacci(n - 2)
    2 T: l  J# ^" y8 i
    9 d. f$ |! T3 ?4 x- c  U# Example usage
    4 X" [( c* H) R5 ~! s  Mprint(fibonacci(6))  # Output: 8+ {0 i, p* R* d, `+ k" Q6 \, q

    - S+ |. g& X: n: M9 y# }* ~6 cTail Recursion
    7 w* P' S- h. V. w5 x4 C- c
    - n/ L! P( \" ?# k; l" M6 ATail 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. j* K) z" `# }
    8 W. s: c- s9 u; G9 i# y, {
    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-8-22 07:59 , Processed in 0.036384 second(s), 21 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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