设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 - w/ J1 m1 T9 E$ q0 q7 q$ a
    # R0 C: d+ T- X' n9 j
    解释的不错
    & T: a. o: f: t5 s- }+ C' Y$ D
    0 b/ O- ~& _5 Z递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。8 z9 m  [/ A1 R
    8 Q4 b6 y( R- j; J
    关键要素
    , F# i% i; t+ U- a; b0 |7 @1. **基线条件(Base Case)*** j" {% s8 j: {$ v; j3 Q2 D  M$ h
       - 递归终止的条件,防止无限循环- Y' w0 |9 L: W3 Y  _& a4 Y
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1  p" `- G3 B1 u* k

    6 x. E& h8 Y7 I) _8 b" u2. **递归条件(Recursive Case)**
    4 N2 S/ L6 ?/ H8 s   - 将原问题分解为更小的子问题
    0 u- }4 M6 f3 t8 m4 g! m   - 例如:n! = n × (n-1)!6 K, Z$ o5 N$ m% }/ b6 L! N
    ! d0 ^% `2 f3 p8 C6 l& l: Y
    经典示例:计算阶乘9 m, [, I" v" c. P0 {
    python5 Q+ E. G5 r, D! q9 k+ ~
    def factorial(n):0 Q9 h) M+ Q& F: |7 A4 s
        if n == 0:        # 基线条件
    , _8 e# I' U/ f/ L# q. P        return 1
    $ d. W# `  {5 j( k( F8 E1 I! E    else:             # 递归条件
    " D. r6 U& ?( {/ z# \        return n * factorial(n-1)
    8 Q2 [+ e, X2 b3 D7 n" T- S, b# M. u; M执行过程(以计算 3! 为例):
    $ B; G" h* A7 F& m' Nfactorial(3)
    : B  h2 t% S# D: q1 T0 Y3 * factorial(2)
    . V7 ]( r# o$ s5 n1 U* Q0 ?3 * (2 * factorial(1))$ t! \/ `0 m* r# s% M( H
    3 * (2 * (1 * factorial(0)))( Q  D7 w3 G( w) [0 j
    3 * (2 * (1 * 1)) = 62 O( Y0 g" J3 U6 @) q
    ! ?0 X2 J5 A9 D! _+ Q
    递归思维要点
    $ L* e& I7 p% n2 C) D1. **信任递归**:假设子问题已经解决,专注当前层逻辑2 t' c$ F8 K* t) s- Q
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)) \& k3 C8 c* Z. N0 T( ~
    3. **递推过程**:不断向下分解问题(递)
    # d, t7 O. k$ _7 p8 m. X4. **回溯过程**:组合子问题结果返回(归); ^" S/ W  M1 r: i% l: |2 G' q$ g

    0 v# G$ o/ b. {5 \4 [ 注意事项% c" p* q8 Y3 J; m# j$ e1 {9 p
    必须要有终止条件9 _2 p) ?. n* ]* Q+ z
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    ; X' h8 \; N' j' ^8 s" I7 u" B某些问题用递归更直观(如树遍历),但效率可能不如迭代: b& l# L2 D# c- u  s0 t: U
    尾递归优化可以提升效率(但Python不支持)
    * d# @" i4 k/ Y/ c3 v  C/ j
    : m# Y- J- d+ [0 d: G8 g! _ 递归 vs 迭代! e& V8 e8 E  i+ e" d- u7 z% k
    |          | 递归                          | 迭代               |
      _' |+ D5 G- @* W$ }7 U5 R7 ?|----------|-----------------------------|------------------|' T& N- q! R* ~% ?
    | 实现方式    | 函数自调用                        | 循环结构            |1 Q2 z: K1 I" E  h- J1 p
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    , v9 N" }1 c% C3 y! N* Q- {| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    3 Q- V, u* ?- f$ {1 m$ T  S| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    7 n3 l* H6 T) `2 J! j
    9 L! _! O4 F* s" k 经典递归应用场景
    $ r& L, Q; a* J7 \9 A* S1. 文件系统遍历(目录树结构)
    * o6 f1 a; u* g0 [. X% t2. 快速排序/归并排序算法
    2 H7 j4 g( X& @. l1 y3. 汉诺塔问题
    $ z- m! \6 ]! U* D6 c, ~" X4. 二叉树遍历(前序/中序/后序)( b4 h; }; `) X3 f
    5. 生成所有可能的组合(回溯算法)
    / j6 j9 v3 j9 H" d0 M
    # r" ^8 ^# `! f& b/ T1 W3 c) E# M试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
      \2 w$ w5 a& Z8 W3 ?: X我推理机的核心算法应该是二叉树遍历的变种。; s) K! y3 D; ?# x
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:, i7 c# e9 c  ]8 @+ I" r2 N
    Key Idea of Recursion
    9 K! s! {# H, Q( \4 x7 \- l; `/ Z
    A recursive function solves a problem by:" ~8 E2 G3 R. m1 f% ?
    & W0 G/ E. L0 G! N6 n7 @0 `- _3 n
        Breaking the problem into smaller instances of the same problem.  n7 s2 c8 C3 P) y

    - l1 y' }$ I: A: d    Solving the smallest instance directly (base case).6 c- u; N: d- y3 _

    ! y: U: W. W+ m# Y! \- ?    Combining the results of smaller instances to solve the larger problem.
    $ o# ~9 t6 ]' |; ]3 h
    / x6 o/ G$ Y" r; {( v4 r" UComponents of a Recursive Function, u7 o6 @2 [# Q0 h  k' J
    0 }) ~! Z+ y' [) s% T# r4 \
        Base Case:
    . z  O! }  M8 m7 T  E% |
    / s$ @$ f  q7 Y) v$ F. c- V+ L8 g% K        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.$ A7 g$ ^7 b1 |6 [0 A: h
    6 {+ O* F- \: K8 T3 f) k# `
            It acts as the stopping condition to prevent infinite recursion.
    6 o. k2 ^( r9 ]: ]/ }) s( K; i1 D
    2 ~& Y8 }8 W* ^        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.2 s! M1 d& G4 h0 K2 @
    / Z7 U3 I0 C9 S; i( R, D' t
        Recursive Case:- c3 ]6 }! h& h4 s
    4 `$ [5 h4 p" f# Y4 l9 Q
            This is where the function calls itself with a smaller or simpler version of the problem.% ]5 W& r1 h) H

    ' r) y, [0 |, D: s. C        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    5 H1 ~5 R! P4 e# f
    ) S. g* ]7 G7 Y2 \' l' aExample: Factorial Calculation0 w: b$ G! S, ]& u3 p. J

    ; y6 Z- L, V5 m0 `" F% G% W3 ?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:
    0 O9 V3 s0 D5 c9 e! }' G8 s
    / R& s$ P  E. H/ D$ i/ C) f    Base case: 0! = 19 @  p& K' ~$ \2 F  z+ V8 u' A" ?

    - b" s1 J5 Y1 d' Y% h- {) M, F) j    Recursive case: n! = n * (n-1)!
    ' W% S) z% d3 {. f0 l3 R
    : X4 \5 _; M0 {; W- nHere’s how it looks in code (Python):: ~5 D* Y, ^; p5 i8 G+ k6 Z
    python
    0 D. c; w1 B7 ^, r) G# L( Y( a' G& g5 c! ^: S1 X9 H: p. I; _

    6 ]) u! T$ T2 D4 w  l4 @def factorial(n):
    - P" {2 i7 L" i9 F5 e5 u5 m" K3 `    # Base case9 {2 n: ~1 ^+ D+ J$ ]
        if n == 0:) w# N1 p. B0 f3 p5 {; E6 [
            return 1
    - [" G, o, E: R! M2 N    # Recursive case
    8 n! D' w0 M! g% ^. j6 C! K; `    else:
    9 T4 g& j- w) ]0 d* W$ Z        return n * factorial(n - 1)0 r# ?! J; i. |- z
    0 D+ d6 [7 n7 I: c) f
    # Example usage
    8 I/ f8 n) W( J. \$ h" yprint(factorial(5))  # Output: 1206 P0 R6 u6 g9 s( y4 \
    - Z& n  F" k, f. ~% J% e2 N+ [
    How Recursion Works! L" s0 y$ ~! Q1 t
    9 I5 \3 L8 t/ U( G& d2 A
        The function keeps calling itself with smaller inputs until it reaches the base case.
    5 S2 {3 Y) `4 m( t3 t$ |
    & C( x# H+ P# @    Once the base case is reached, the function starts returning values back up the call stack.
    + q* ^6 [  J7 ^" z; O% P* e0 \
    7 r2 s7 u. ^9 X& k    These returned values are combined to produce the final result.
    $ a  L' Z! L8 b9 a: W" T" ~" o9 p8 k! O3 U: Q
    For factorial(5):  `# @9 U0 j. P9 z8 {% j

    4 A2 S- [# v4 _0 M2 l
    ' X- k- C9 \  C8 ], D  H# pfactorial(5) = 5 * factorial(4)
    1 v7 W$ D  G/ j5 p# i% H3 w3 qfactorial(4) = 4 * factorial(3): Y* A9 g0 e+ t) b1 d  ^2 |
    factorial(3) = 3 * factorial(2)
    1 F* ^4 d+ u* V$ W) jfactorial(2) = 2 * factorial(1)
    - @  ~2 D" ~$ U2 _! Y( y" kfactorial(1) = 1 * factorial(0)
    9 w9 p. T1 G& e1 y3 i( l4 lfactorial(0) = 1  # Base case2 z4 K, m( k  q! i" T. c9 W# m

    / r# Z; S2 `0 d6 OThen, the results are combined:
    1 e( ~3 i# a) i+ E$ Y) Y' ^8 V0 I" g  W7 I; p- L
    ' n) m4 @% y+ m( R
    factorial(1) = 1 * 1 = 14 {9 l% }/ a" C% X6 v5 a- y7 E
    factorial(2) = 2 * 1 = 2$ h  Q9 X% x& c8 ]9 C
    factorial(3) = 3 * 2 = 6
    8 l" K5 m( g1 S7 u7 w" C. q" rfactorial(4) = 4 * 6 = 24
    7 _# G) b) B' P! ^factorial(5) = 5 * 24 = 120" m3 G: `1 G  a7 [! U

    - @% B6 o7 g6 s$ t/ gAdvantages of Recursion9 J5 v9 o. d* Y+ B/ n, o- n
    9 R1 ]- x7 [8 y3 Q8 G
        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).
    4 d; V! N9 c, R+ ?5 X/ D/ n$ X0 F- E, g) M; Y
        Readability: Recursive code can be more readable and concise compared to iterative solutions.( ~" T6 r! x- g0 j9 H8 F
    % n7 L  @# b' X& |
    Disadvantages of Recursion
    2 h1 `. r. \6 I* v- K7 ]
    9 j( ]" K4 q1 r6 a$ r" W$ P    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.
    / l) E& r; B0 A. {: i8 c/ j
    7 {4 N9 ~" D1 r! W' n    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).+ Z- K7 o$ {* u( z

    1 P$ u$ }* G; f2 `. x* [: [When to Use Recursion
    ! F$ i# G9 K' q
    0 t: Q* K$ ^5 p7 s    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    , ^) S: I. c3 I6 k2 A$ n/ h) j
    $ e5 S7 w- H2 m6 P/ l/ _6 C7 _* m    Problems with a clear base case and recursive case.
    9 ~% d7 b" J$ Y. t
    & R: D) R; X2 I+ [3 WExample: Fibonacci Sequence
    ; I0 y$ f! q8 h
    * M6 Y3 n, r6 j5 |; WThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:( O$ J( B9 W: E/ a" F* v# z2 I

    4 b; i6 ^  d* m, q& V. O    Base case: fib(0) = 0, fib(1) = 1
    / d, q- A  ]8 y" k( X) q+ k& [
    $ y& d; ~8 Y. H2 R4 D. z/ b    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    , p$ R8 v1 x. Y
    1 R, `2 f4 h8 J6 {0 Rpython1 q6 H1 ?* }7 F+ ?8 |! @* M5 c. O

    * _% n' b; j9 a" G, F8 l* k
    # V5 U% i9 ]+ ]9 F/ w$ rdef fibonacci(n):7 }8 Z  [- h8 j  \
        # Base cases3 ?0 j3 {6 e4 R0 b6 t4 k; a! W
        if n == 0:
    / E" }0 z, Z4 J: [  r        return 0
    # k& J5 y0 u8 O2 @: u# o    elif n == 1:+ f+ F4 {* [" z' h4 d$ n
            return 1
    # f+ {: G- I) ~1 M8 b: q, S# x    # Recursive case
    % o# E* n2 u( m8 H8 K3 Z    else:
    ( R" E) o2 h8 L% i$ K1 ]0 p        return fibonacci(n - 1) + fibonacci(n - 2)9 D4 g+ }5 f( ~$ ?; {. {
    # N0 C( p" `% O! y' ^
    # Example usage. C9 o# E& v) U0 v' t) N! @/ R
    print(fibonacci(6))  # Output: 8
    9 R9 {, B# X: c$ _- z! J  L" y, L4 z
    Tail Recursion
    # s' L4 a" _6 e) D/ {) z: a1 q: W! N- ]( n% e0 U
    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).3 K1 C" j  o/ V) ?6 J% R: Z4 H

    : \+ d; b  I1 g5 M. m) t( a4 JIn 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-5-2 20:35 , Processed in 0.083115 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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