设为首页收藏本站

爱吱声

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

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

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

    [LV.1]炼气

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 % V* y# e/ S' Q. _3 u

    6 D, S* S- k/ H* m解释的不错
    - z2 `0 P5 I) O8 C2 ]( j' s) x. _# B& f# j) b
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。: `, i0 I8 B5 ?
    2 u. V$ R9 w# o7 x$ X9 N
    关键要素
    , l- X' D+ w7 T* b1 o$ T! M, W; B1. **基线条件(Base Case)**6 H6 z! b/ o/ Q2 q. P( X
       - 递归终止的条件,防止无限循环
    4 b7 i4 o4 v/ M; I   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    ; j+ {, T' F% m! B: ?# V6 |" O  p
    2. **递归条件(Recursive Case)**
    0 r8 \! r% l0 U2 V0 V; j5 E   - 将原问题分解为更小的子问题
    : G9 l1 V2 B/ |' _8 F   - 例如:n! = n × (n-1)!
    . J8 K! G  z3 _" `+ U  O  L
    * i. Y% |3 W' }# \. {3 n 经典示例:计算阶乘
    $ T0 I" y0 l$ k) b2 W1 F0 W6 b! tpython
    7 g7 a! p! ]* u: \+ ndef factorial(n):7 J1 D& `- F& {5 B/ y
        if n == 0:        # 基线条件+ }5 }) t: u" x9 p
            return 1
    ! F% N- n3 P: T    else:             # 递归条件5 g; [3 Q+ ?& k$ Y8 w& ~
            return n * factorial(n-1); J$ G: v7 P& v$ T& k$ R& l
    执行过程(以计算 3! 为例):
    & l! R7 j: I* S5 i9 A4 ~factorial(3)
    / R1 @8 v1 ?* F' G3 * factorial(2)
    6 p( t( @7 @) g% C  {3 * (2 * factorial(1))
    6 u$ x" v! b- c3 * (2 * (1 * factorial(0)))' |- c. R/ C/ W$ t
    3 * (2 * (1 * 1)) = 6
    & W' R7 ?- J! z& f6 R) H" p( {. D* [( y# Y6 C) r; P$ D. l
    递归思维要点
    5 B' E0 {, B- d$ C8 F+ |1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    * v5 w) b; u6 t% O" p2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    ) A+ w8 ]/ `, f% t3. **递推过程**:不断向下分解问题(递)' L7 ?  l- m+ U  o. w$ [  V
    4. **回溯过程**:组合子问题结果返回(归)
    4 h/ Q$ p: f5 X3 l  H) {" {
    1 L  l/ W/ B0 {4 T4 y) t 注意事项
    ! @: q# c! H1 f; t; V必须要有终止条件  U) G: O) r5 ^% X, S  d
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)2 t2 E. k) F( v* `2 O1 R
    某些问题用递归更直观(如树遍历),但效率可能不如迭代: e* f6 a% B& E  ]7 [8 X
    尾递归优化可以提升效率(但Python不支持)0 L6 C6 J' t4 ~+ y
    7 M9 a9 q6 F6 |6 ?+ x
    递归 vs 迭代
    1 \! \( F2 f, s7 G$ g% Q|          | 递归                          | 迭代               |
    ' W. @6 j8 x9 e% l& K4 Y|----------|-----------------------------|------------------|! D3 V9 P4 n8 o4 C$ x! Q/ @( S2 K
    | 实现方式    | 函数自调用                        | 循环结构            |' n+ K; `# M% O5 v% w6 k
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ! }. A6 @6 r( f4 \& \6 |, _0 w| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |$ }/ d) E! o& i0 x& L
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |7 {0 f4 L3 M# t* B4 g

    : A: H% I/ U2 W+ m 经典递归应用场景5 P9 Y) X9 {. P3 j) X
    1. 文件系统遍历(目录树结构)4 [5 x7 Y8 e% f8 D' H- R8 d
    2. 快速排序/归并排序算法
    - l+ C: q8 w- [7 q4 G3. 汉诺塔问题, F& b3 I7 _# k! e# s& g
    4. 二叉树遍历(前序/中序/后序)* G2 d& K2 I' W9 R/ p4 Z
    5. 生成所有可能的组合(回溯算法)
      }$ Q3 {. G  k1 i; ^0 h/ ]) n3 H
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    10 小时前
  • 签到天数: 2975 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,) n2 u& X- a: f7 n( s
    我推理机的核心算法应该是二叉树遍历的变种。& k; }0 y! D7 z/ i0 l: J" |
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    , t& n7 U( g* K, Q& V2 M. eKey Idea of Recursion
    0 H! R1 b8 Q. l) S  m. |) P* S) G- W/ F0 b8 C
    A recursive function solves a problem by:- H' G& `' G+ E* R2 M  \9 p. U' b
    2 Z$ G4 ~/ x1 s$ r3 b3 V2 p
        Breaking the problem into smaller instances of the same problem.+ N2 @8 u, d: s3 |; I7 O

    $ _  h0 f8 q& A0 \0 @) O    Solving the smallest instance directly (base case).
    : c$ z3 B8 W" r6 M% O2 @) Z( ]
    3 z$ I/ u* v. E    Combining the results of smaller instances to solve the larger problem.
    0 j& a4 K' `; j$ k" h9 `7 e
    " k% @3 E% h! C+ B+ MComponents of a Recursive Function
    1 i  U* t; I5 y, _4 A" q
    $ ~/ H; N1 k1 H0 O+ B3 {+ L& ?) K4 I    Base Case:
    7 }" k' j) E+ L! [+ }+ N* Q# F0 [
    - M6 U7 a$ \* h8 k6 f9 O        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.+ G, R+ ], C2 U; X2 K
      c7 v& f9 X+ n9 d
            It acts as the stopping condition to prevent infinite recursion.; j9 ^8 x0 {% Q. J& J( l' L4 {! ?

    + H: ]' p$ |1 l! y" h" x- L        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    ) w: t4 W* P' K4 A1 d! d- A8 q/ v6 m/ j  l  G- I: w8 j5 y
        Recursive Case:6 @5 i: z) V# `9 R1 `! t7 m

    * A& R1 Y* c7 J$ W7 o0 Z        This is where the function calls itself with a smaller or simpler version of the problem.9 \" l6 p" Z8 P% V# J

    2 X/ G' g& N+ o5 b& B4 B5 Y        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1)." G/ Q% o5 ?- |& j
    ' G" R6 W' W0 ^5 u. u2 \
    Example: Factorial Calculation0 Q( |( x5 ]( _

    ' F& i# n* G$ k8 r/ OThe 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:* y2 x( d8 q/ c: U2 j

    3 Q$ u% h1 E7 n5 {. G1 @    Base case: 0! = 1
    $ v" F7 T# M5 ^% Q9 v, n7 d; ]* q; u2 V1 e
        Recursive case: n! = n * (n-1)!
    + R) j, Z! u) H/ ^1 C# p) y* \# P/ G- W3 B7 J7 _
    Here’s how it looks in code (Python):
    ! s9 T5 n$ I$ {: J" }0 wpython3 Z6 e* o) y2 O/ e

    & j/ `8 n1 L* X+ x  S5 j4 M6 w3 [: x6 {% k3 N6 T8 Z2 |5 R9 [
    def factorial(n):6 V2 J1 b; z9 y
        # Base case
    2 Y4 Y$ I1 R7 q3 y- h    if n == 0:
    ) V/ A; m# E- L; h! O. r7 W4 ]0 s        return 1' ^. V$ f* L# g& t$ M: ~  P5 l+ S
        # Recursive case2 U2 i% _& ?* Y0 R& ^2 Y( o
        else:6 l! ]1 K5 d0 S  a1 F4 ?
            return n * factorial(n - 1)
    . E% P: V" I* Z% o: p% C# [. l% t; S; z# m3 d5 E: ]: e' G
    # Example usage1 z% ?& q2 B3 y' p4 x
    print(factorial(5))  # Output: 1206 c2 ?+ s3 s. d. E" ]2 @
    0 @! ~( i: i6 n6 ]
    How Recursion Works
    & f* a8 ?; o+ O
    / o- w0 I5 }& D    The function keeps calling itself with smaller inputs until it reaches the base case.  H! E8 C6 t6 g& M- L$ C

    . l. g7 K; L: |# e1 g% e    Once the base case is reached, the function starts returning values back up the call stack.
    4 G8 w) P& \$ m  F) X! X# v, U# N6 G0 R3 B9 ]
        These returned values are combined to produce the final result.- L+ Q; H2 ~& ~; ]! r- y) @
    : k6 v* F% a4 v5 I8 f
    For factorial(5):
    5 ?- V3 B" f6 b* U( g
    . r% |- q8 C$ D2 W0 v5 p( Z: R0 P' K8 V* T" K. M2 C
    factorial(5) = 5 * factorial(4)! J5 \( f6 d1 I. z2 d
    factorial(4) = 4 * factorial(3)6 P# u! a: I# N/ z
    factorial(3) = 3 * factorial(2)
    7 O0 S0 Q# `# f7 Y' sfactorial(2) = 2 * factorial(1)% E% ^7 _! [: E% r
    factorial(1) = 1 * factorial(0)
    8 x" F& R3 _, ^$ Tfactorial(0) = 1  # Base case
    $ y2 Z2 P2 o9 T4 U7 g+ T
    8 M. N! ~& T0 I" b' _Then, the results are combined:
    . P$ ?1 a5 k. i5 Y8 X, m" U
    2 ?3 i1 r  I6 s+ n& M1 B7 G" r# \& j- ]
    factorial(1) = 1 * 1 = 1
    & q: D6 J& `  o7 w  r4 Qfactorial(2) = 2 * 1 = 2
    . c8 W' i. _( mfactorial(3) = 3 * 2 = 68 Y: O& T7 z" p7 L, C
    factorial(4) = 4 * 6 = 24
    4 h: r7 g( s7 ]+ Dfactorial(5) = 5 * 24 = 120
    " o, @" T/ s% O& ]7 F! W# n" o1 Q4 ~3 J, X9 f
    Advantages of Recursion
    " g2 X0 c' p8 F- o( h3 Y0 Z8 F7 F6 |" f2 ?7 s2 V* V
        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).
    , @* y6 e' ^7 R! q  {4 |! r2 K: z9 a  Q& b
        Readability: Recursive code can be more readable and concise compared to iterative solutions.; V; o* Z0 u, m4 }  l
    % A. x, ]" @7 ]+ \" M/ t- ]8 A) \
    Disadvantages of Recursion
    2 w7 ?& A( A3 M+ N
    : o. d* O# T+ _% J0 l    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 n9 N  F% O' s5 @
    6 L, _' V" w( y4 W  ?% q. [; L    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    % n$ Z$ C# d9 S& f' d2 Z7 E  {8 }
    When to Use Recursion5 c, O0 G) c, \- T; g
    + t$ v' m6 D! E1 h" M8 f
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    3 [% _- J1 z9 T5 i% U3 X
    & S, B) \" I0 n5 w( k3 o    Problems with a clear base case and recursive case.. t2 p" z8 k3 r" a! z* k
    * M) t2 U0 X7 E  _/ {+ U2 M
    Example: Fibonacci Sequence
    * l: T7 v  R+ [4 v: P# N( \( a& i1 p4 L4 z5 g0 p" A: o* }7 \
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:% N6 Y1 \; S! x  s
    ! z8 q3 Q, q+ q3 B) R/ Z) ^
        Base case: fib(0) = 0, fib(1) = 16 Y0 z7 l/ d  q  L5 j3 F' T+ W$ _
    / O1 \/ e# o8 {$ @8 a3 f9 P# c& k
        Recursive case: fib(n) = fib(n-1) + fib(n-2)/ q" J- N3 j. ~: d9 I; i4 u+ w

    ( t1 R/ G, W6 S  e9 {python: P" Q# ?$ a5 V5 g9 C

    7 q7 f) c) ]. _' ]& q0 f: p( _$ F$ O1 W' [8 X+ f" s  D
    def fibonacci(n):
    ' X  B5 r4 o: {    # Base cases5 s5 _; S! X. O+ m
        if n == 0:
      L: s# R9 E; U( {5 ?' ?# d/ f        return 0/ t, L, |: d1 V* J7 K/ O
        elif n == 1:+ [+ a3 J" D- L  ?# }( e
            return 10 C$ w$ d: ]* t7 Z. w/ \2 W: z
        # Recursive case& ]% \2 f: r: X* {  {# D
        else:: L" K5 l% m  T
            return fibonacci(n - 1) + fibonacci(n - 2)! I0 t" F, t5 s. Q7 T
    ' {4 h8 i: d; W$ \# k# R. i( m4 ~
    # Example usage
    . G1 P, E1 D. U$ F0 Vprint(fibonacci(6))  # Output: 8
    8 e0 y0 c/ |5 K. {: v  C
    ) d- j3 o$ o7 kTail Recursion+ B; i4 r0 I  T, P! q, s
    6 d9 g; _0 C7 c7 x$ L3 f
    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).
    9 P, _9 r# U8 E6 |/ U- W( z: G2 }5 ]" R, B' F& j1 z  I# Z$ M
    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-7-10 10:22 , Processed in 0.043228 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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