设为首页收藏本站

爱吱声

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

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

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

    [LV.1]炼气

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 ! i# V6 T! y- b& ^3 }
    ( k4 _" k9 Q0 o6 I7 f/ [
    解释的不错7 x8 d0 Q$ ^1 ]0 Y

    # q; y7 O; K! {5 I$ H# B7 q+ C/ \; |递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    - l8 a3 |, c7 F; j6 L  X. P
    8 ]% f  \- Z; \& ]" k 关键要素
    / s; P. p! y6 x3 u( E1. **基线条件(Base Case)**; ~4 g4 Y# f% m) Q+ \) V+ ~4 P5 f
       - 递归终止的条件,防止无限循环$ V% Y+ w) ^# y. I
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    6 b- \7 |! E+ E
      V4 [, p, j8 X8 G# K' }2. **递归条件(Recursive Case)**9 H$ f  w& h7 j9 P& s2 T# @+ X/ v
       - 将原问题分解为更小的子问题( j3 M* ^8 l7 F/ Z
       - 例如:n! = n × (n-1)!- ?% J3 m+ t& p' Y0 d* [/ l; h

    1 h' f: p1 i8 P8 w5 h" Z0 M 经典示例:计算阶乘" I5 ?2 c' `  _* `0 P1 `/ N
    python# X  M, S# Q# M, H4 I; B6 a# q
    def factorial(n):+ `2 b) N/ i& K
        if n == 0:        # 基线条件; x; A: L) d. P, z  Z! q/ u" N
            return 18 b! G# |. c" E$ E
        else:             # 递归条件
    ' a" a* p( S3 ~, `5 k        return n * factorial(n-1)  }, O, {( q4 ]+ N7 e# ^
    执行过程(以计算 3! 为例):
    7 S# h  l, k  g+ Rfactorial(3)
    2 l& }. P# e$ c  O' p, v8 f: j3 * factorial(2)" k6 O% K; Z& z: D- z
    3 * (2 * factorial(1))
    5 w( S/ N' Z* s: e, h3 * (2 * (1 * factorial(0)))' l. N1 W0 A$ K8 \- R: x* Z
    3 * (2 * (1 * 1)) = 6) Q0 Y( f) k3 w0 M
    - M! \4 a+ h7 `3 Q+ f
    递归思维要点' F' r% p1 U; _0 D
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    4 L7 e/ i; ^5 _2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    / F. R$ Y' `9 k8 t; b3. **递推过程**:不断向下分解问题(递); l, g6 T0 r; P5 `! v) {7 s
    4. **回溯过程**:组合子问题结果返回(归); i" D8 ^; W. d/ ?# @9 V$ G& Y% n
    " F' `: ?7 G  b* R. g- |
    注意事项
    ) f" m' T1 M; y: f0 {! d0 _必须要有终止条件
    ; f7 C# c, [# J4 \5 z' N递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    " _$ S( r. l1 v, r0 y某些问题用递归更直观(如树遍历),但效率可能不如迭代
    3 `& g9 m/ p; [' E! `5 {. |尾递归优化可以提升效率(但Python不支持)
    3 V. q% O; m  p# |* M$ n1 _/ ^" S8 E( k
    递归 vs 迭代3 |" ]& t( ?& i* D7 ?
    |          | 递归                          | 迭代               |& E6 U( n" a8 p3 ~# d. U- U
    |----------|-----------------------------|------------------|
    : N  n% y1 x1 |6 x' _) L+ x; v2 _. `| 实现方式    | 函数自调用                        | 循环结构            |
    % |& k; c$ B! g" D0 }& W# W5 S8 T| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    & T7 ?0 n& I1 _( Y) ]7 \| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |2 {9 h% y5 L  }" a( T
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |- _$ E0 U8 j2 j
    % v0 |4 H( G& L* R
    经典递归应用场景  O2 H$ B" {" b! [8 M% H
    1. 文件系统遍历(目录树结构); {& g7 M& T. I) r
    2. 快速排序/归并排序算法  F* r; T* K5 i% C; ?2 b
    3. 汉诺塔问题
    ! S! W& _! f5 j' W) @4. 二叉树遍历(前序/中序/后序)
    * l1 m: Z7 K% |+ l" b5. 生成所有可能的组合(回溯算法)
    + P2 b1 Y/ q1 K$ r! `
    % U: h2 A2 s! E4 R4 o& u试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,+ R' b9 D. w1 W8 Z
    我推理机的核心算法应该是二叉树遍历的变种。8 n- a7 l) j; w8 l8 c; ?# f
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    # m$ ^6 D3 c0 R( N7 J: [Key Idea of Recursion
    5 p0 C# d- w5 N* B: Y% |: {! s$ A- h: }5 N" |
    A recursive function solves a problem by:( K/ f- F! h' k( i, n

    4 y5 f: N' s) Y+ n! n$ x# G    Breaking the problem into smaller instances of the same problem.
    5 `7 r+ B" u- X; ~8 m7 U( A# ?! A- C1 r7 f, D/ _9 E
        Solving the smallest instance directly (base case).5 K. j# j; X/ c2 S8 K
    7 J) q3 D7 r. n& V8 E- {
        Combining the results of smaller instances to solve the larger problem.
    2 s3 U2 k5 Y8 U! m& I3 J  Y# B; S: x* J: M7 P& M) f/ Y' z% ]1 q
    Components of a Recursive Function- a: b( b4 p- J2 J* E$ X

    . a2 L# H9 w7 L    Base Case:! b8 y2 a, z, T, k, d

    ! H2 U& v7 y, n9 P7 `2 t; a! v        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.- _+ ?- `! F, L7 B8 R& t
    3 L1 C5 n9 A% b4 z
            It acts as the stopping condition to prevent infinite recursion./ w9 N3 ?* m; u: E3 H% r  c, W( P7 S

    & {2 h$ K& M% u$ z" {        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    - N4 c+ O8 l( Z* F" e& o  L- ]5 R  P; ?+ q% |8 m' g$ k
        Recursive Case:
    ! {2 k% d- G# d0 a
    4 H) a) G( e+ `        This is where the function calls itself with a smaller or simpler version of the problem.6 I- q! K0 B+ S

    5 \7 Z3 f! A4 c' L. ^        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).3 K2 ]( t: D/ V

    7 D& N0 Y. V* u* oExample: Factorial Calculation, k$ W9 Q8 }% w$ D4 Q' x

    1 E2 X& b1 l+ y0 D/ i2 }: zThe 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:
    / n# i) P4 ?" V0 `, p/ W4 @3 m* ?5 C. K( b) h
        Base case: 0! = 14 W. h3 A0 H+ V

    ! ?# s4 `+ E: M    Recursive case: n! = n * (n-1)!3 Q' j1 x/ y. R" B2 Z& ~6 w, o
    1 _" i% e. o; t' y. _6 Y5 e
    Here’s how it looks in code (Python):
    : t; k2 H1 c  u: P' \' ~" ^5 Dpython/ q/ Y3 ^: O# v/ z1 }

    , G: [0 M9 ~( ?/ T+ S9 T( U) R* D8 a$ Z
    def factorial(n):0 p  u6 l: L6 Y; b) G
        # Base case9 w# s* c& R$ l/ N
        if n == 0:0 J+ b2 D( j$ ]6 R% \
            return 1& H8 y+ x1 V) c8 v9 w
        # Recursive case& ]% i% D+ w$ l4 K" o$ ]3 p* S1 Z$ c4 N
        else:
    ! p- f2 a. H1 R6 _4 G9 }        return n * factorial(n - 1)# l* X. C, u2 @  C" c
    / W" Q% }5 P9 W% ]
    # Example usage2 |% _5 N6 J! U/ V
    print(factorial(5))  # Output: 1207 p) ]- a: k- _5 n( `3 ]1 S$ v

    $ v* ?1 l0 H% Z: u& nHow Recursion Works# J3 f, q+ @( Y7 L" F
    ( m* }  u6 e! h  }5 O# i
        The function keeps calling itself with smaller inputs until it reaches the base case.$ n. \4 F3 A& A" w5 N
    - U) P3 x: q; O9 N8 y
        Once the base case is reached, the function starts returning values back up the call stack.
    4 `  R$ Z5 l3 a" P  d
    9 K" l/ T# k; o; C0 N: r    These returned values are combined to produce the final result.
    9 u2 D2 m8 B! i" D$ G, z# Q$ v/ x: r% B7 w
    For factorial(5):
    2 m' k, Y! [+ L& v) W7 I2 n
    $ z3 c$ A1 }/ X* U: S2 o& G1 O- M' d: f& W7 Y
    factorial(5) = 5 * factorial(4)3 Y% |/ d  X* f8 y5 |) e4 k8 y
    factorial(4) = 4 * factorial(3)# |8 l1 U8 I5 @* t
    factorial(3) = 3 * factorial(2)
    0 P; i( a' @! E# q+ rfactorial(2) = 2 * factorial(1)3 |/ u" ~% S8 c( |8 r7 a. \, v  w
    factorial(1) = 1 * factorial(0)
    4 a; G& h5 ?* f7 C$ Pfactorial(0) = 1  # Base case# ^% K4 l, `- n

    + S7 h! w) T. y8 Z8 C7 ^4 [2 WThen, the results are combined:) S! p4 i% t2 n' C. H& V' Y: h4 o

    5 r/ V  Z) ~; j
    . s# u2 L6 z/ ]* g# O, _9 `) cfactorial(1) = 1 * 1 = 13 Z( e1 O/ D/ M) @, T8 b
    factorial(2) = 2 * 1 = 2: I7 @' G, o4 F$ J$ S
    factorial(3) = 3 * 2 = 6
    7 d4 I: m) c+ d8 `/ A3 k% zfactorial(4) = 4 * 6 = 24/ W9 L( E1 S$ Z
    factorial(5) = 5 * 24 = 120
    ( A( v' w$ f: L% A# \7 X
    / b. l9 Q! z7 j" R# O3 L9 N. v7 IAdvantages of Recursion; L$ f# s* a8 [# L

    0 Y) e' f2 L& j    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).+ }& T, o5 H' A
    6 N. N' }' f2 l) B
        Readability: Recursive code can be more readable and concise compared to iterative solutions.7 X$ Z' `0 M0 m  z, {

    % m1 J  j' T8 y& s# m! KDisadvantages of Recursion
    3 v7 V4 b# }9 d% x" n9 q% Y7 F+ E$ \9 v) Z
        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.
    7 o- j+ X! |( E) \- y/ w  G9 ~/ h5 j2 M1 d# k9 y1 i
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    + u$ D; X7 r) j4 N+ S! A1 }% m+ ]7 R& ~0 F5 d
    When to Use Recursion! K' o& a, W) B/ E
    $ |; z* F5 u2 z* `$ z
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ) ^9 l7 N  }2 b" L1 D3 N# r3 G7 c( a, }) z5 L# |
        Problems with a clear base case and recursive case.; @+ ]+ C: t' z+ w' B9 s

    * Y) B, [4 c. q# m5 S; RExample: Fibonacci Sequence+ p2 S9 W7 {3 U3 \8 f+ C4 Y
      l0 `, d4 x, T
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:! H7 L, |1 G% l. D/ \, e7 Q
    $ d0 @, H" M& \! {
        Base case: fib(0) = 0, fib(1) = 1! o7 d+ v4 S* g: k( Z( y; t
    4 ^( B( e' ?9 y) Z; K3 z1 F* `5 V
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    8 m4 C( B9 U7 ~! r, l% v8 \4 R' X- ?0 K0 K+ A
    python) k& W/ h) a  w. C- j3 }, e
    / ~) Y; @) q5 `, M" _6 n

    0 x9 N8 @% O# N' M- B7 k7 l- Jdef fibonacci(n):
    4 _! \( S" H0 d- L: K" h8 |8 p% R    # Base cases" \8 y+ T- g7 i1 D$ ~7 q
        if n == 0:
    4 @9 V7 g" ^7 L% p+ F& X2 W4 C        return 0
    7 `" t* H% E6 k5 _2 I6 H) T( u    elif n == 1:
    4 S, v' h+ _, E! P, \7 H( r        return 1
    7 \, P% E- C1 i8 ?2 W) ]    # Recursive case
    7 Y6 q& V, k$ u  X# x1 t    else:
      Q. u# o7 X: ^; H        return fibonacci(n - 1) + fibonacci(n - 2)
    9 B# U6 Z7 S) H; m, Q! d; |% s) v& {* h2 O9 ?( U$ x
    # Example usage
    : D4 t# A4 B+ m0 c0 o0 r& Tprint(fibonacci(6))  # Output: 8; A/ x( {9 u' z  x* X8 P  n
    1 a# Z' H2 ]' x4 H
    Tail Recursion) B4 F9 E6 F0 Q5 D/ C
    . ~2 X) L8 O5 r; D% Z  y2 S) S/ `
    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 e. U$ e3 m; p$ D  K" B- N. V) c8 u8 \0 O0 z) A/ a& h
    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 13:46 , Processed in 0.038908 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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