设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    1 {4 O; i7 V) L4 ]; b3 y+ v
    3 f; B. Q2 l; O' x解释的不错0 `3 V8 z( B* n0 p
    / ^% b# V% l$ b# B" B! o+ H. P9 O
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。- v' D2 |$ X8 O6 b$ Z
    # l- O! ^: t/ J& W% V' c, R; G/ _
    关键要素
    ( Q2 d+ @: j0 L1. **基线条件(Base Case)**! M3 }- g, j0 D7 [( C/ r7 ]
       - 递归终止的条件,防止无限循环0 e: O2 _  ?- Q6 I/ ~5 y0 |
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    5 B3 Z4 Y: O$ T2 R+ s6 y0 x
      J) z. X6 H* f: s8 m2 u2. **递归条件(Recursive Case)**
    ( Y/ h* I; x3 w0 r; ]* L   - 将原问题分解为更小的子问题8 x/ T$ x/ I  {* l# G3 a% P
       - 例如:n! = n × (n-1)!7 r2 _/ k+ _$ @2 N( G' ^

    " Z9 z  k: F5 o  R 经典示例:计算阶乘7 d; q! L3 U  D- J. u1 z7 `
    python) X  C' \9 Y# D" P! F
    def factorial(n):' y) `9 e/ A* O+ b' c
        if n == 0:        # 基线条件  [  Z5 P' C7 c) t2 [) r
            return 1
    ) T: B2 q7 T, R    else:             # 递归条件
    - z( t6 t% ]9 N- t; m        return n * factorial(n-1)8 N" P1 B$ {  h3 t- F0 `6 Y
    执行过程(以计算 3! 为例):+ }8 E  u$ Z/ ?9 }+ F
    factorial(3)- m9 K, l; P$ c* o  p
    3 * factorial(2)9 P5 t. B9 q  t( ~( i1 m
    3 * (2 * factorial(1)); ^& Y3 y' v" s( e5 z8 G! G
    3 * (2 * (1 * factorial(0)))
    * ?5 I, X* }7 B6 Z( h3 * (2 * (1 * 1)) = 6) R7 J  r" @! E& p* F) u7 p1 m: P

    2 ^: [/ r  K. O4 b- o 递归思维要点6 U8 {/ _! n0 m  f% K
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    + w( e' s1 z7 _/ w3 H5 S! L2. **栈结构**:每次调用都会创建新的栈帧(内存空间); f* E( Z/ `) _7 C1 C9 S" O) v
    3. **递推过程**:不断向下分解问题(递)" I) H; g1 c+ ~
    4. **回溯过程**:组合子问题结果返回(归)
    - F7 z! ^' V6 u+ q/ ]4 D: k2 X: B
    注意事项
    $ q0 F) Y' I9 Z必须要有终止条件
    + f4 o4 v# |$ Y' o+ q3 x! q7 H递归深度过大可能导致栈溢出(Python默认递归深度约1000层)! d5 e8 T7 {2 p( S" E) a) @
    某些问题用递归更直观(如树遍历),但效率可能不如迭代' p' j; C- u& Q3 d/ g
    尾递归优化可以提升效率(但Python不支持)' G% V% C; Q5 W2 G9 J* i) q

    7 w" `0 ^; O5 J3 T2 F5 s 递归 vs 迭代7 ]7 S' X2 J* O& D% N( `+ Y# \
    |          | 递归                          | 迭代               |) K8 y/ h; v) R' j  y1 O0 O- [
    |----------|-----------------------------|------------------|
    7 F! n& f% w" E3 C$ x| 实现方式    | 函数自调用                        | 循环结构            |- o  r4 T8 \( f. c
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |0 J0 C. O, v$ s5 ^* S
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    % c5 W* ?; g. l; p| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    / Z, L# ~4 ^# N4 a% R3 D  D/ E1 _  N3 i- U. n
    经典递归应用场景
      v# o' q$ i  y4 Z7 O1. 文件系统遍历(目录树结构)( f% h- k  b: n
    2. 快速排序/归并排序算法
    8 W& K+ s2 g0 e. g% w3 [; d3 t3. 汉诺塔问题
    $ s9 {' _' Q9 ?" T/ f4. 二叉树遍历(前序/中序/后序)
    / e" b" t& k# |: Q* {5. 生成所有可能的组合(回溯算法)
    ) M, C: W" V; l! n- e5 P  r/ \6 l2 }- a7 a4 t3 W3 S( H' b' s; C
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    昨天 06:53
  • 签到天数: 3111 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    , S! L& q. k$ Y4 R; Q6 p/ U我推理机的核心算法应该是二叉树遍历的变种。" X* T$ ]1 }6 H6 V3 M
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:8 Y& o4 e# P+ M
    Key Idea of Recursion; e6 b$ J, S, `5 G% @

    7 c6 o# _7 I1 r2 [4 H5 EA recursive function solves a problem by:
    ; S( I; i; L; r- t0 A; ?  R" J3 ^: O" S) d5 U" {" |
        Breaking the problem into smaller instances of the same problem.
    " ]- T' O* G3 s8 P; u6 V* R
    9 U0 T. m, U  x- h1 L  c    Solving the smallest instance directly (base case).- N7 z( @( j) w- S% b
    , u3 Q# ^* P1 R+ c7 w
        Combining the results of smaller instances to solve the larger problem.1 M$ W0 C6 a$ D
    ! X: t' U1 m; [0 q) S
    Components of a Recursive Function
    : ?9 ?/ M$ a0 D& F- o8 n% C% f4 ^( n/ U* ^0 ]. x4 V
        Base Case:/ S# F6 l/ h2 G7 v- L

    " X6 m* c. P# O4 y: b, O; m' P        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.3 \5 w, S. N; d) ]* W) T8 a
    ' ~" X) V2 Z' g3 B' i5 f" e5 R
            It acts as the stopping condition to prevent infinite recursion.+ x4 S* c9 X4 G- I# r* N' g, q

    ) o# B& ^4 ?6 \% E        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.$ D6 D; \0 u3 N2 ?; ]* }, j9 M

    % t0 h, H! V) s2 k' P2 A    Recursive Case:' _% T+ r9 i5 I2 o, ?

    4 y. w4 N' [/ C5 f2 Z+ N        This is where the function calls itself with a smaller or simpler version of the problem.
    # c$ W- w. Y: v* W' G" ^
    $ Q% S4 q' O: d        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).9 E3 z3 j* C1 x6 s, O
    ; _. @& `$ ~% O# _# b: M
    Example: Factorial Calculation% p9 \- |# v( e& ?' g, n+ R
    7 x: f9 Q' X6 C& 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:- |! Z4 r' S9 M7 S: Q  _
    5 ~" E2 y$ r) [
        Base case: 0! = 19 O1 A7 l1 }0 Q5 G

    5 H) q6 V  ^$ A7 K- N9 U: L% M2 a    Recursive case: n! = n * (n-1)!0 e  r* Q, l" m0 [3 ~5 [+ `; H) T

    % o4 q' w* E& n& f9 J: IHere’s how it looks in code (Python):5 Q2 v4 i/ k9 b- m
    python/ Z8 q; ~: q; ~
    3 Y) s2 A# [* U) N
    4 H$ _5 K- e, B5 _3 x
    def factorial(n):; e. r. ^( ~& O6 R5 M
        # Base case
    : b- e1 i# \; w, [: t7 h. C    if n == 0:) ?, M' Y' K" N" E( M$ C
            return 1
    3 O! X# w/ Q+ N6 G2 Y1 _    # Recursive case) |: |. G; Z+ q# S
        else:
    7 o) t4 J. t$ u: e3 F9 _# p' \5 r        return n * factorial(n - 1)
    $ u% Q$ P/ V& f( z3 x& K8 i
    " q0 x& E/ _2 i6 F8 }( g0 _6 T# Example usage; e+ Z$ ?2 N# b. Q3 r
    print(factorial(5))  # Output: 120
    - L6 }0 f* n4 p- e) s( i" P& r' @5 |0 a" c( y
    How Recursion Works
    / I: D9 V, \7 M+ i- t* E3 o( l
    ' L) a9 N+ }6 _5 W    The function keeps calling itself with smaller inputs until it reaches the base case.! v- |, p$ b3 K1 \, ^
    * c) D. S" F: L" h
        Once the base case is reached, the function starts returning values back up the call stack.; O% [- [  U5 q

    + V% X( r0 {5 K, G& i! s    These returned values are combined to produce the final result.* G1 B; o9 }1 E  L% j

    & u' [5 D2 x4 \$ f; P6 FFor factorial(5):
    ' r. f8 Q8 v" J
    ) L" A: z0 R5 c1 I! s7 j: M
    ) k+ U- ~% P7 v# K, qfactorial(5) = 5 * factorial(4)
    ) Q, w0 W' S0 u- x4 m2 pfactorial(4) = 4 * factorial(3)
    " ^4 r' ~4 `2 Z  x" R/ ]factorial(3) = 3 * factorial(2)
    ' ?' W2 X3 X$ k0 F4 J6 h8 Cfactorial(2) = 2 * factorial(1), L9 c0 n" P; h/ u- j9 T! n6 q
    factorial(1) = 1 * factorial(0)8 Z) c" h+ l" h
    factorial(0) = 1  # Base case
    . M9 G7 s7 _; B- ?- W3 I8 z
    " |& O: |% i# J2 vThen, the results are combined:5 ]" S9 G4 f, i& X

    1 ?% J8 N( ?, r0 y
    , }4 O5 U% e$ @6 _: gfactorial(1) = 1 * 1 = 1: D- B4 T& Q5 ~
    factorial(2) = 2 * 1 = 2
    : y0 B  @% D' Y: Afactorial(3) = 3 * 2 = 6! }7 ]/ u( O: I* P4 R+ K
    factorial(4) = 4 * 6 = 24
    ( J* @0 u2 E8 I% u$ y+ u' M' T  wfactorial(5) = 5 * 24 = 120; ?9 Z5 G9 ?4 E. m1 M* R

    5 I$ A9 f0 _- ^Advantages of Recursion
    . r- a7 N* r! A: c4 O% ~/ m# Y2 G- E, v! L8 z. L" U% ^
        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).* N' W& c. Z2 `5 H1 ^  C
    % t) ^3 [. H9 [  [" b
        Readability: Recursive code can be more readable and concise compared to iterative solutions.$ l$ D* h$ V# f  Y0 q4 D) T' p
    ; i& ]. t. P0 T0 Y  _2 _# O% U" }
    Disadvantages of Recursion! Z6 O2 @2 b7 S. W+ ?1 F
    + P1 r' l6 l2 i! U# V% o8 D1 d
        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.
    8 p& C! [% C2 e0 _
    2 u5 d: v) n# A) F3 s7 m    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    $ K5 k- {' t' v5 r5 _3 F& l# c  \+ b
    When to Use Recursion! q% E+ }0 X" w' x

    # A" X. w7 }+ t4 i; D3 L    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).5 @: m9 U9 ~, n! N6 [0 a; x

    . L4 ]* i" A! @% q! Y    Problems with a clear base case and recursive case.
    1 Y# {! j+ q6 W% {6 m, L# u8 F% g! L7 b9 F0 ~# Z# r+ u
    Example: Fibonacci Sequence
    : u1 [$ T7 _; y  _6 e: f* Y, x' \  _! c' ]/ D; d9 z7 s9 e7 f
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:# E* d, |; M( ~6 J; I( t0 i2 _
    3 x. g$ t% f- n( i/ N
        Base case: fib(0) = 0, fib(1) = 1
    2 C, Q7 ?. Q) ]$ \7 L1 u1 _" j7 v9 m' g9 n" n) ~( J
        Recursive case: fib(n) = fib(n-1) + fib(n-2)) ~$ B! G$ S+ P5 e8 `# ?/ d

    - X" E- M6 S- E' Q1 {& Jpython' ~+ s& |) G5 B( Q( {
    7 h: y- w* O5 a% J8 @; q
    ( ^$ X+ B5 T  Z% X( j
    def fibonacci(n):
    ; t$ {# i( s# T1 o" w' e; w" G    # Base cases
    0 {, U+ F. y  R" u    if n == 0:
    ( L* N2 j& b2 ?1 e1 k2 x8 z" R        return 0$ ?  m$ B. _9 u0 y; E$ _% ?, l
        elif n == 1:# {' o% ~/ w* m4 b0 {# M
            return 1% F8 T% ?2 H5 O  w( p4 A
        # Recursive case( F; y8 Z' F" i6 }6 d2 ?
        else:5 _2 G+ N: g; b5 L$ q- ?
            return fibonacci(n - 1) + fibonacci(n - 2)
    / w. W& O7 C- Q6 @& n- ~; X$ L8 i9 ~( k: [4 D
    # Example usage
    + i4 ]+ t9 M+ J5 F$ g. Pprint(fibonacci(6))  # Output: 8
    % x# T5 f7 Y! _( t% y( \
    5 Y* p2 o9 k0 d, K/ _2 TTail Recursion: Y5 s8 u9 z5 b: x) b0 k

    1 V& I# o) p, J0 `% D/ ITail 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).. N$ J+ o* Y* b: q

    8 f7 J& m% h: _! t0 ]0 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, 2025-12-8 00:35 , Processed in 0.069679 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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