设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    * t% I: E! l0 |4 L, c% m' Y
    ) Z" [. m4 ~- {0 a) N9 J解释的不错* ]* r, R" m. E$ F% H

    7 Z7 H' X2 F/ P5 W4 P& Q" C+ Q. p, e递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。0 N, |8 m3 d' }/ c" z# ?
    ( U% Q" S$ ]5 `& {' [
    关键要素, x) K4 }/ N( ]$ A
    1. **基线条件(Base Case)**+ c% p$ E* [: X9 `/ x" P) E
       - 递归终止的条件,防止无限循环
    ) c0 V4 T) L% E   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1/ G: w0 y/ j4 O; ]
    / _7 |4 R/ s0 M9 ~7 O4 V# _$ ?7 @
    2. **递归条件(Recursive Case)**' {$ q% R4 H* v5 M/ G  j, P
       - 将原问题分解为更小的子问题3 f1 x1 ?) Y7 T3 B& k# O+ I
       - 例如:n! = n × (n-1)!
    6 A" P1 X$ \1 H8 F& ?+ b2 ]( A  V9 d. Y; r5 v# w1 w# F$ F: u" k5 X
    经典示例:计算阶乘
    # ]2 s  D5 O% Y( `4 vpython/ i% B) @2 z2 r) ^1 s
    def factorial(n):& B. k" C( I) f6 K1 u! O
        if n == 0:        # 基线条件
    / @2 e$ }! N& A+ ]        return 1
    ! D( G! L( y+ f1 F, v8 I    else:             # 递归条件
    0 j# a/ e7 P% m9 n4 c        return n * factorial(n-1): M' I2 m8 N5 K$ Y/ c" F) X; R
    执行过程(以计算 3! 为例):
    ) Z+ B% X: ?6 a# {, ~% X- d+ f& afactorial(3)
    : e6 s0 k0 j: c1 \( g( ^  o  P# L3 * factorial(2)0 M6 m3 x8 U# v+ T/ w; n  c9 `
    3 * (2 * factorial(1))
    ' Y8 I% H2 c2 T9 f. ^+ s& V3 * (2 * (1 * factorial(0)))
    9 \- C- ?% F' C7 l+ i  U! W: ~+ X3 * (2 * (1 * 1)) = 6
    " z8 C; }  B% c" {
    ' `4 t$ X% o0 w" A  |  m 递归思维要点+ q& P3 V/ z9 {. j# n
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑0 i- [: V0 A' U; ?5 G
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    9 p- k; {  ?% C6 u. V1 Z% n3. **递推过程**:不断向下分解问题(递)1 X9 O8 R& a7 p* s
    4. **回溯过程**:组合子问题结果返回(归)
    " e$ N' P# _8 C
    $ I8 G, @& h. S; U/ g7 b 注意事项
    * I# d$ j9 Q4 N4 A1 K3 }: T必须要有终止条件
    - Z* d' \% w+ @1 ~9 L+ T5 ^递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    " _' T( n% l7 V( `某些问题用递归更直观(如树遍历),但效率可能不如迭代
    . {2 M2 r# _: l6 K, ?3 g尾递归优化可以提升效率(但Python不支持)2 V+ t* L% p1 U
      U. |0 m& v+ d+ |8 }  o
    递归 vs 迭代) _, f; L; ]1 _. j, K) L" `
    |          | 递归                          | 迭代               |2 T4 _; A3 j& O
    |----------|-----------------------------|------------------|
    % T4 o" Y1 }" [- B3 @| 实现方式    | 函数自调用                        | 循环结构            |( O7 [7 u4 }2 d' [- x
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    , x& Q7 x' H2 O, f| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    $ r) e/ ?  ]6 L- }2 h| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    8 k6 H! Q$ w, b  L: g" o- s: h" }6 D5 Q; d
    经典递归应用场景6 r$ \& Q( I# d! p0 ^+ s
    1. 文件系统遍历(目录树结构)
      Z. v  Y5 X$ p- t2. 快速排序/归并排序算法* Y3 `2 G# X: o+ M  v4 k) e9 A0 L, Q
    3. 汉诺塔问题1 d2 I8 V) r; y6 \( G9 ~
    4. 二叉树遍历(前序/中序/后序)
    + B: f0 p# t' i5 l8 }) z5. 生成所有可能的组合(回溯算法)* S. x5 ?, i7 @) e6 P# w) h1 c- l
    ) J: }- [7 v/ c# L% i3 o* P
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    ! }: Y: j" W: ?; p+ X  D我推理机的核心算法应该是二叉树遍历的变种。
    - Q9 j6 z" `5 P' ^另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:" y" _. B  q* ^  R7 \
    Key Idea of Recursion
    ( C# x1 X) P, X( M$ x, f" I: o& S& M
    A recursive function solves a problem by:6 Y/ ~) a$ Z1 a( j' G, {
    & h/ f7 w" o4 G6 H2 m7 e0 D* j
        Breaking the problem into smaller instances of the same problem.
    4 o- y3 \1 N4 y. k: e( O8 x
      w2 J7 b3 B- ^& f    Solving the smallest instance directly (base case).% V7 h8 ^/ w" R/ ^

    * G0 O3 k) K) h0 d# Y4 @: t    Combining the results of smaller instances to solve the larger problem.
    ! y% {5 p2 y+ g. S  w4 f0 Y/ z) T; _6 D; h, g
    Components of a Recursive Function, d. d' t5 X4 x
    " `+ @/ m  I5 q! b+ o
        Base Case:* d4 e6 T7 b) n! G5 T/ J; m
    4 c' j+ M* O. X% C- A& [/ G
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    % a! o3 ~6 S( W4 Y8 Q" l( T1 X. _5 ?1 C. c6 g
            It acts as the stopping condition to prevent infinite recursion.
    % F# D6 l6 {' t+ K% ]  j
    ) T9 x$ {* o8 B. _        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.+ V7 h$ D0 @/ Z( w

    + A6 l! L; n. Z8 p% B    Recursive Case:. o/ ^% U: M+ x, k
    ; I; B) R: ?, Z6 H
            This is where the function calls itself with a smaller or simpler version of the problem.
    * G0 n- `5 c7 @. N/ r
    ; ]" f, ^$ j% M! |$ x- P        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    ! L& A- c+ }2 `- C1 G, V8 t3 a9 t! i& Z  n5 ~( p
    Example: Factorial Calculation5 y5 I) K# [$ P  s6 p  m0 S

    / |- B7 c$ |! q4 P# d. uThe 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:
    / \6 w, }) h! c
    5 [: D  [( }5 F9 a5 s    Base case: 0! = 1
    4 U$ @4 d) O: h& v) Z3 P
    * L7 r; ~, I9 k7 D) B: ]6 J0 l4 N    Recursive case: n! = n * (n-1)!
    . X2 r- B$ K, G& _
    ) I; j7 Z/ N* H4 {. `Here’s how it looks in code (Python):8 i5 s5 o5 c+ _0 H
    python. L0 l5 @" V' q  }" o, r# W6 F6 W

    7 d1 j2 U1 T: i0 P5 G
    3 J& o4 \# r& u7 W) \$ sdef factorial(n):
    # O0 z9 i( ?" N$ e6 z. D# U    # Base case
    ( D5 i$ L% F$ u. }% z    if n == 0:
    / ?! [; r9 x7 F        return 1
    & k" v3 |* M( `3 o( g+ @    # Recursive case
    : G4 ?5 H6 P5 l1 z    else:/ U) w7 v3 k( d9 \: T8 d* I
            return n * factorial(n - 1)
    % J9 B+ n0 u. X! L) z2 `2 B7 e' W/ z
    # Example usage4 r4 z, z+ s% I% P7 `
    print(factorial(5))  # Output: 120
    ) b9 E+ w/ @% S' Z- D' i1 \$ M  S" k4 F* r3 {1 |+ K+ q. z
    How Recursion Works8 J! j2 S- F6 b1 u% R+ a' W: D* Q
    2 a8 P% B  j: p& o# B: H
        The function keeps calling itself with smaller inputs until it reaches the base case.) E- \( @# c1 j/ ~+ D1 ^  |

    . y& c, w* Z0 Q) U4 H* j    Once the base case is reached, the function starts returning values back up the call stack.2 Q7 Y% [- f/ v7 n
    3 E& @" b- o% |" B5 }
        These returned values are combined to produce the final result.0 ^; z0 ^) e9 A' P; Z( m2 D+ _
    $ I1 `; j/ Z3 h5 E
    For factorial(5):
    # G" r' V8 M/ _: c* P8 f# J1 b# }$ T# `& Z* P& l$ o( H

    - L- [0 H5 X) S% h8 qfactorial(5) = 5 * factorial(4)
    3 m: U* @! _  l. @: D6 wfactorial(4) = 4 * factorial(3)
    9 c+ Q7 G6 O! h7 M3 [factorial(3) = 3 * factorial(2)
    " t" J  Z- U& y( nfactorial(2) = 2 * factorial(1)
    $ N) A) e! ^- \& l. C, _* hfactorial(1) = 1 * factorial(0)
    * \  C% K5 O" N( }; x7 d' pfactorial(0) = 1  # Base case- ^% A8 \1 o, u/ _4 y

    , K* p" C3 A6 K* D! I2 P1 tThen, the results are combined:
    5 [, X/ J! r3 y: ]; D1 Z9 e$ Y$ T/ B
    1 P) f% I0 C' ?8 U) B4 b9 H
    ; q8 h0 ^+ F& y  Tfactorial(1) = 1 * 1 = 1/ b& C: e: W$ n) c6 {
    factorial(2) = 2 * 1 = 2
    % }! ^; n' ]1 N4 ofactorial(3) = 3 * 2 = 6" v+ F3 U) Y+ U6 y! X; d3 m
    factorial(4) = 4 * 6 = 24
    " Y9 x/ _9 ?+ L" d* Cfactorial(5) = 5 * 24 = 1200 }$ E2 H( O' i+ j" P* C% M

    / w7 T+ l; V1 {5 H5 I! hAdvantages of Recursion; p. O1 h, x. m
    ' @7 `" t- ~+ N! i4 K8 i
        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 ^% u! w4 G* q, o1 Q
    7 ]- b/ E3 u$ ^9 R/ l$ `' x
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    ; [0 A/ W" [: I2 c2 N8 `
    7 X2 n' ?9 p0 r$ k% [# B, a' M! hDisadvantages of Recursion
      G2 E1 [" W7 ~  A' @& q3 b( D. Z9 M6 E( 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.9 n3 R. i8 h' I' I) z/ s2 h4 k

    2 D( j1 |. p+ M; O    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    & X# @6 z! n* t# c1 k( U
    ; i$ W8 A' r0 J" }When to Use Recursion
    + j( U9 n0 x' L& `* K8 L3 f- k( `' I2 a" m
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    : X4 i7 W% z5 s' d3 ?' w% B2 k1 E) r2 M5 |2 d* S4 X
        Problems with a clear base case and recursive case.
    7 F1 ]$ {! }) D1 d0 ]3 H- b  p' l; e9 b2 v) }
    Example: Fibonacci Sequence
    : U% _2 ^, Z5 h$ Q. ]4 y! e1 d% @' F+ c2 P- N! q# y3 _
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:5 [# S' l0 G! B6 r

    4 V5 i$ g' g: [3 f/ L1 ~1 a- A    Base case: fib(0) = 0, fib(1) = 11 [, o- Z% r, I/ s: f
    , O: U3 U% M# D) Q; H  y
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    2 f+ m; s: d" t1 F# [' @4 c3 r) }2 @2 g8 D
    python
    , J. k# }4 A0 s% `& I) R: a3 x" x' C
    ; J" O6 r6 [. q' u, L' t& T4 ]
    def fibonacci(n):4 d1 D7 Q5 F- n4 t/ n3 p9 J
        # Base cases
    4 v) H+ R# {9 T$ d$ [& W$ h    if n == 0:
    ; A* R/ Y0 d4 ~        return 0
    & D- @0 P& M. _$ n. R    elif n == 1:
    3 M+ \) ?9 `# P: y/ r        return 1
    7 N1 v  f6 F; h4 S+ H' h    # Recursive case* j; Q* n" H, O/ h2 Q8 [
        else:
    ' O8 X; P* m/ M& d- o  k  V7 Y        return fibonacci(n - 1) + fibonacci(n - 2)
    7 o3 c8 u2 l9 r. r+ V; m9 @9 x
    5 z& P; P( q. |+ k  e# Example usage  G; W; _( X7 W+ Z0 ~" y' r
    print(fibonacci(6))  # Output: 8
    9 ?8 Z+ P, O+ Q$ y  f4 u5 a
    / R% e7 C0 J! _; U+ PTail Recursion! x: f' s* Z2 Y0 K! P  ?

    : j* W9 q, `# F5 @; i/ sTail 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).
    ; ^# }- C8 I' g
    $ B9 `7 C6 Q( GIn 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-3-24 00:28 , Processed in 0.055867 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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