设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    3 z2 Q# U# @) p- ^; v) {1 w/ c5 `) [' u$ ^! w- i7 u1 a
    解释的不错0 K8 _/ p1 `" q& z

    , d9 B. D; A$ ^/ j. H6 T  T' R递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。1 a: \3 P8 R, e* Q5 W' l! o
    7 _, w$ F9 k, C
    关键要素! n4 B- z* n* S& v- v
    1. **基线条件(Base Case)**; X2 O0 M% r* a8 Y" t% o
       - 递归终止的条件,防止无限循环
    , p: K, W% v: k0 a! P% f/ t" W6 B   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 18 d" q+ l* m9 J, G8 [
    4 h; Y0 _% G' V" C
    2. **递归条件(Recursive Case)**# `  `8 i0 G) @5 z) y: ^9 V5 ]
       - 将原问题分解为更小的子问题
    7 r! ~# l1 K9 d  P   - 例如:n! = n × (n-1)!& z1 J# a3 Z, i# T0 q8 i6 j
    3 m$ u, x0 [) j- n1 i
    经典示例:计算阶乘
    3 `* H' w( z, w; W- h7 {  o4 wpython
    - K- G5 D; y% ?& q6 ~def factorial(n):
    ' [: J# H  N) ~8 o, v' M    if n == 0:        # 基线条件
    ) M3 f" ?/ d% P; G0 m- L* B        return 1
    - I& n, |: k+ N# X6 @    else:             # 递归条件6 J7 y# o% H5 I; n
            return n * factorial(n-1); ~3 e; P* h0 I/ q
    执行过程(以计算 3! 为例):' J. c) @3 k( l3 A1 {8 ^
    factorial(3)6 Z9 x' ~' E- Y2 x8 M
    3 * factorial(2)8 ~1 y* x  _! {$ t5 X) ]
    3 * (2 * factorial(1)): F+ N: |  [5 U, K& D$ z! I/ |
    3 * (2 * (1 * factorial(0)))
    # j4 p5 L9 F; t' [9 L0 Q3 * (2 * (1 * 1)) = 68 }' b" x, i4 F8 t7 R
    ( p: K1 m( ~* ]' ~
    递归思维要点
    : C: w! c8 M2 E" w2 o1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    8 C" E' l( K  P0 D  y$ G; w( @$ t2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    + P. x" |8 f9 s$ s. c8 p% s3. **递推过程**:不断向下分解问题(递)
    7 J% Y5 A  ]& \; C1 g, L7 l4. **回溯过程**:组合子问题结果返回(归)
    1 |: w+ f/ t0 D; `/ L! N! `! L8 [: `: d) m3 ^
    注意事项# p. S' B+ N2 l: ~9 z' d. |
    必须要有终止条件
    1 e6 V) |1 k: D& U9 A递归深度过大可能导致栈溢出(Python默认递归深度约1000层). P" y2 ?9 I( v, Z- U' O% ]
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    ) B. c7 M# {7 `. \% H6 w尾递归优化可以提升效率(但Python不支持)
    0 P7 Q. }7 |: y* x% i" b# R8 K8 z% W& I2 I
    递归 vs 迭代
    , D$ A8 o4 x4 a" o|          | 递归                          | 迭代               |- ~1 Q7 _' L; X" ~3 N
    |----------|-----------------------------|------------------|$ o6 x. y# N$ W
    | 实现方式    | 函数自调用                        | 循环结构            |
    & h5 Y2 P5 Q& U! ^1 l| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |+ W; w9 E" z3 B9 S9 T6 j. k$ M# h) Q3 _
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |! a0 p' o6 x6 C  s7 ~6 \5 C, N
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    ! T5 v6 i7 t4 J: k7 _0 y2 s8 R8 _) p  d% B& Y; \! s
    经典递归应用场景5 U- X3 I3 i# F
    1. 文件系统遍历(目录树结构)5 V/ ^# O: B4 E* A  k
    2. 快速排序/归并排序算法3 h9 n) Y9 F7 F. q( O5 u, m
    3. 汉诺塔问题4 \4 S! Z3 G2 y- i2 x& c( K
    4. 二叉树遍历(前序/中序/后序)
    $ y% r3 c* C0 n0 Z  v+ }5. 生成所有可能的组合(回溯算法): M# `- _2 n( i/ V5 @

    2 _1 U  G* s5 s  f  j9 |5 _. P试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    昨天 08:28
  • 签到天数: 3123 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,* P5 q- B. h" l* |9 a8 e1 U+ O
    我推理机的核心算法应该是二叉树遍历的变种。$ j$ }/ V. K2 d. L0 t8 |  }8 @
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:2 h. L6 a: _* b
    Key Idea of Recursion
    $ `4 b- d# i" G. |# G' @  n: `& c1 c; E  [% B8 o. o. d0 N
    A recursive function solves a problem by:2 u: J7 a+ B0 P: [; N8 Q( ^/ q- s

    5 x) L( A% f- a8 `. v    Breaking the problem into smaller instances of the same problem.3 s7 J1 R/ P: Y. |
    ( ^5 `7 t, t( s- `  I
        Solving the smallest instance directly (base case).- [; ]! u8 f# H1 E9 f0 D) k" N/ B
    % m9 }; W: q4 A7 p; N0 D0 L
        Combining the results of smaller instances to solve the larger problem.
    4 @. X( R+ S  [, E! n9 p9 m6 b9 g, i" {: a" N! e% _" y4 {
    Components of a Recursive Function
    3 R6 |, A2 N! K
    & h" T: k. L" V5 d+ y5 G# i( K0 I+ j    Base Case:. |  ~, H1 C7 P6 V3 G( B# i0 Y

    ; ?. C# o2 D% Z/ f7 B        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    7 q6 L  {, L: _. A1 O6 X( {' k2 C0 @
            It acts as the stopping condition to prevent infinite recursion.- l0 d7 u% }: w3 }2 a2 `& g( e

    5 C6 n' y. d4 O: ~" o        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    ' t3 C* @4 G7 `0 D8 d
    ! ~5 x/ c7 \7 s' x6 K7 f) \7 ^    Recursive Case:" O" K3 ?: ]* f" f4 `4 e$ W
    6 X- _/ p* Y# N/ K+ g0 ]9 I
            This is where the function calls itself with a smaller or simpler version of the problem.
    0 I5 s3 R% w; d% @; {, M2 E
    / ?( ~9 [2 D( H        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).0 v) z: }% Y6 K
    # d( A" [; z" k0 W( X
    Example: Factorial Calculation$ x# N2 G8 b- `: Q
    8 R$ e3 u' E' F
    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:( |1 _6 {+ P+ s' |% e/ e/ S
    9 @0 x* ?7 i0 t" T8 E
        Base case: 0! = 1' |5 f8 Q9 E; b' x
    4 E( h4 w* d0 B* d* }/ }) i* U
        Recursive case: n! = n * (n-1)!
    / R; X; k4 F- t, i  n
    + c" e1 K! T. o1 _! k4 wHere’s how it looks in code (Python):
    1 v1 }$ {! n/ l# c, G: ]4 jpython
    5 u+ K9 m6 i% L7 j& w( u9 b: M1 l; Z2 l+ h% G, ^
    / n7 E1 A& s: x
    def factorial(n):7 z/ _) p$ f* c5 Z* K
        # Base case# O+ R7 D5 ^: G
        if n == 0:
    & ^& s$ ^* p: K8 R. x0 X$ y        return 1) O2 F" P+ v5 y) p# N
        # Recursive case3 k- d5 [* Y! x
        else:
    : Z# _7 u2 C5 W1 ~        return n * factorial(n - 1)
    , \4 }4 \) w/ ]4 r- Z- Q3 l' z5 o+ G
    # Example usage  [0 }" j% v9 o! a: D, |
    print(factorial(5))  # Output: 120
    & q6 s: k' D, i3 Y1 ~* a. @6 v
    7 R4 B" L; l8 [0 C7 Q7 XHow Recursion Works+ U8 K0 B* I+ V. m

    0 A' b) Q4 O/ E5 u  {    The function keeps calling itself with smaller inputs until it reaches the base case.
    $ B- C9 Y3 J! ~2 H8 \! q- s8 h
    3 t! d  j2 G3 D6 ~3 S9 X7 J    Once the base case is reached, the function starts returning values back up the call stack.8 w8 h# j9 F0 F$ l+ ^3 u) G

    ) b+ ?% @7 A! A2 t    These returned values are combined to produce the final result.
    ) u/ Q! y+ x* }' ^+ n) T7 ]/ {0 Q" o" K1 P& J
    For factorial(5):
    5 E6 E# l' `9 t3 V7 V. z  |
      ^' Y* P  j' Z2 U- j  B7 ?2 I9 e0 [3 ?- }+ t: g7 I. z7 }* U6 N1 W
    factorial(5) = 5 * factorial(4)  m+ B8 |% K) n9 h" |2 w0 D. I( c
    factorial(4) = 4 * factorial(3)
    / c4 h! f$ d. G- [1 Wfactorial(3) = 3 * factorial(2)
    9 {' |6 W7 G: Afactorial(2) = 2 * factorial(1)/ z4 `0 B, o* v# _0 N
    factorial(1) = 1 * factorial(0)! n9 S; f& [) w7 O3 l
    factorial(0) = 1  # Base case" i, g9 f1 N$ l8 Q

    ! i* z# {  n1 z$ qThen, the results are combined:6 j; T! a) t2 b8 u  g" q) v6 m

    , }' d& l) w9 K; z  m4 A" ]# ^- b  e, f2 H$ z$ G! \5 v! G/ G
    factorial(1) = 1 * 1 = 19 }8 I8 r+ c2 m- ]4 R1 V3 R0 i  U
    factorial(2) = 2 * 1 = 2
    : O, j5 q, l2 r: ^9 Yfactorial(3) = 3 * 2 = 6
    + x- S# {# x; o$ Z3 s0 }factorial(4) = 4 * 6 = 24
    ' }/ t; ?9 N& G" g8 A  ofactorial(5) = 5 * 24 = 120
    # N! `1 v) @! i# a3 k* k1 p$ S" Z3 m! o
    Advantages of Recursion
    % \) H* d# l% m$ `& b0 C* ?7 @/ x$ W6 A# l
        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).
    ) j5 z2 O& |0 L/ A
    # n8 h! p/ Y2 Z' s3 g$ G* ?1 _    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    8 l& w$ o  }& k, S- _4 O3 F
    + t! A3 b7 t9 e4 C0 S; h. q  t# X& lDisadvantages of Recursion) k6 D7 V8 k* O/ a% R5 y

    4 S$ X7 ~$ n. Y) J" H* t    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.% x+ ^  o* ]& C0 k
    . h  n! b, g/ {7 W* }6 s
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).9 |' X- a% z4 K4 t1 n: g
    & y: `  t/ x0 E$ K" u  x
    When to Use Recursion1 Y- H! }# r. r

    6 u3 ]8 W, ?. U! }3 ~; p# Q    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    5 C: Q- Z. P0 G6 w+ N9 s! {( j/ G2 U0 ~7 V
        Problems with a clear base case and recursive case.! n9 O( V/ k* Y5 s1 Y9 b

    9 ^& R# x$ f4 R. ]Example: Fibonacci Sequence
      b; T: i; W$ ~6 O) g
    $ A& j- D8 s9 a4 i% [4 c6 PThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    & O. R2 S% A( H5 f+ H+ _% U  ]
        Base case: fib(0) = 0, fib(1) = 1
    7 l/ Q" \6 u: w' L0 k) K+ v, _% n  N8 i& g4 ?! T8 _. G. ~) |
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ' y; D6 E1 n+ h" @: p
    ! \) f3 R. P. O6 O8 K1 Lpython" V% d4 @, k$ c" a# g6 i

    / d& n5 B5 m, X" ?. f! M. l# N: Q  ?1 o# U9 E2 T2 Z, u
    def fibonacci(n):
    1 t! r2 x5 v  o0 v! d; H. n    # Base cases
    1 d0 z% B$ M: x5 r# _! y6 l  S    if n == 0:
    * x9 D3 f+ ], [5 s+ Y+ ^3 h        return 0) r) t: S& ~0 R1 T: j; \5 ^# j
        elif n == 1:
    0 _, T+ Z1 B8 D3 [6 v* _        return 1
    + a! S$ T* n9 \( j    # Recursive case
    : c( X+ a1 h( V2 Z8 }    else:
    5 U8 M8 V0 B$ y6 [7 x        return fibonacci(n - 1) + fibonacci(n - 2)7 L: v5 R% f( n: x/ [  C% y
    4 W% p4 a- C) ?8 Y% n' q
    # Example usage5 @3 W3 T# s7 U! @4 \: z8 O" M4 T+ {' @
    print(fibonacci(6))  # Output: 83 m5 W6 G- W& x( r1 a

    - I- D$ L- w! ?) n( {0 c* A5 uTail Recursion* R/ \  C: q/ ]  m$ s3 u' V" J8 ?

    ; ?7 w1 F9 R4 K5 E6 B: W0 L& y. GTail 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).
    8 y3 }! y: S& C9 H- ?3 p# H. M
    3 N% N/ `& G8 f% \9 TIn 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-21 03:27 , Processed in 0.029730 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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