设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 " V+ `; ], e5 M5 c) A. ]/ s6 _

    & ]; m4 ], b3 C4 J6 A解释的不错
    % `, h# P; m7 q4 h3 j4 K: y$ X0 \
    , [/ I7 b/ N. x6 d' W1 L递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。4 M8 q3 X: b) b- C, H7 y: D

    , Z3 [  ?# l4 b/ S; j4 M: q6 v 关键要素) i- Y& K# r& h3 b
    1. **基线条件(Base Case)**
    " R. n# F  y# I! k% ?( y0 o   - 递归终止的条件,防止无限循环
    1 k4 c- T' ^2 m/ H   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    2 ?6 r& C6 i6 n8 s  O) C& e# ~; z( Y" Z( E" Z" `
    2. **递归条件(Recursive Case)**
    # \! x. q/ i; r   - 将原问题分解为更小的子问题
    0 E* _+ i9 Z! E5 B   - 例如:n! = n × (n-1)!* o6 D, F5 o0 e/ e7 G/ X0 c5 y2 |  b

    4 A3 t5 A: S8 Y4 v9 n% ~ 经典示例:计算阶乘
    7 v" b/ u: C; M8 s; n2 M$ v, H. fpython
    - P. D" A1 Q$ ^  a# ^def factorial(n):
    1 `# x0 q8 R) e/ q    if n == 0:        # 基线条件
    5 B6 Z/ w# g$ g" A1 l        return 12 z; Q$ \! [, O
        else:             # 递归条件/ P- B) x9 `9 y- n
            return n * factorial(n-1)/ m9 [" Q# P) o" z
    执行过程(以计算 3! 为例):: ]; G+ u3 B8 x. r% A
    factorial(3)
      ]% v# o: X; {0 c8 a% y- C3 * factorial(2)8 G- z  Z: E; t/ G) r; O
    3 * (2 * factorial(1))9 h1 \0 a3 A0 ?0 a$ i* z
    3 * (2 * (1 * factorial(0)))
    + R9 X6 `% i- n) Q9 V4 d3 * (2 * (1 * 1)) = 6
    % {  l; C/ ]6 Z9 r
    - M8 X- {' j) e* j7 @ 递归思维要点1 i+ _( i' M" p2 N3 u
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    6 C  Q6 A; u- E3 T; `9 }2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    7 H7 J' y6 B0 X. ]3. **递推过程**:不断向下分解问题(递)
    : P- k$ U' u0 {1 Q* ~4. **回溯过程**:组合子问题结果返回(归). _# y% x3 D/ M/ k% x

    + n! u4 G# h! m5 f# m 注意事项4 {" Z) E! ^' ~6 C
    必须要有终止条件  i  ]4 y. {0 J% T
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    1 V) b0 B% Q( G某些问题用递归更直观(如树遍历),但效率可能不如迭代" B; v; w( e1 Y7 @5 H+ ]& Q6 a
    尾递归优化可以提升效率(但Python不支持)
    + V3 k4 b5 x7 [; {0 N
    3 G1 h, T  T1 b/ I) x/ \/ M 递归 vs 迭代
    , y$ g' I/ U/ F8 S2 U- m' ?! R|          | 递归                          | 迭代               |
    ( V5 d0 ]5 F! R|----------|-----------------------------|------------------|
    & o, k/ E/ t, K1 i( ?- {| 实现方式    | 函数自调用                        | 循环结构            |
    6 r$ f3 V5 N7 q; W' o' `| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |; y% r; k8 U6 I, k* E1 v( M2 B
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    8 W" Q* \: J' _- G| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    4 w) @$ Z) L* I- ~$ p  Z$ B" e; A$ N
    经典递归应用场景! A9 ~) O* m& u0 s4 d! o5 o
    1. 文件系统遍历(目录树结构)2 c7 p3 t4 l! k3 i
    2. 快速排序/归并排序算法
    8 F1 S, l7 F; A3 M3. 汉诺塔问题
    / V3 A3 S* i/ r% w7 ?4. 二叉树遍历(前序/中序/后序)
    . e: k* D5 _8 n( {% W1 J5. 生成所有可能的组合(回溯算法)& V4 z) w0 F5 e; w
    6 `- U9 M% Q5 {
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    慵懒
    12 小时前
  • 签到天数: 3167 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,4 z  K2 }, C& t' ~
    我推理机的核心算法应该是二叉树遍历的变种。, @: Z) W# e  c! }- 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:
    ' d7 R; |0 H: u. U* \1 E# qKey Idea of Recursion1 E. n" C' A) T) ^# _
    ! L8 U! R5 b% B
    A recursive function solves a problem by:
    , x& ?8 {( q4 j- C
    - q! J. y! s! x2 y& F    Breaking the problem into smaller instances of the same problem.: B1 R5 y) I0 i3 M- r

    * N% R# g" F  ^. C# ?% g* [7 V( M    Solving the smallest instance directly (base case).4 o+ k! p$ T& Z7 U9 A- V
    + h0 j5 z1 ~; {" _6 g6 {
        Combining the results of smaller instances to solve the larger problem.$ g- v7 i+ @9 j6 v: }
    4 y5 Y0 X; T5 P5 D2 |9 z
    Components of a Recursive Function( d( H5 {8 |, A. m9 A! Y# k/ r1 O
    7 b, d! b2 ^9 f+ A$ I
        Base Case:
    # N! ~6 Q+ q: g4 t, C3 O7 e) \( f' L/ N/ p2 S
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    % A0 d# M; t' w# C7 y' L3 p. a  T% j0 N& ]
            It acts as the stopping condition to prevent infinite recursion.
    ( V! B% B0 x7 U( x$ U2 E% y( f4 ~) k6 I. {
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.- e4 F$ e; }7 _$ ?3 ^
    9 V4 O; T2 m' }' K9 J; {3 ?* [3 A% u% G
        Recursive Case:
    / |0 ?9 }* g( q6 I0 ~5 q) w6 I
    1 b7 m) k9 c5 ?6 ]# J6 k3 c' o        This is where the function calls itself with a smaller or simpler version of the problem.
    6 n% q/ U: I# L, N! j  a8 S; h3 k0 b) I7 `( L1 i* f
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).% [  S# G& N- ]

    . I. f, U9 G' ?2 u+ P& {Example: Factorial Calculation# H; q7 e( x' J4 |. @
    2 r1 i* R- ~6 Y; g
    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:6 j. n+ [  W; P6 Q
    ) g% t! u! \7 p$ b2 S9 D
        Base case: 0! = 1+ [3 u' d* }3 E" R' [: d7 v0 ]8 A

    " [: i/ O8 M; u% I1 b9 S; C, V    Recursive case: n! = n * (n-1)!
    9 {' g$ P4 J& u  ~8 }7 J# r$ L
    4 j+ J7 r+ k8 p0 @3 cHere’s how it looks in code (Python):
    6 f  b' Y$ @8 k; Xpython; m# o& ~1 E  u- n# Z

    + P9 [0 l0 `) ?% J/ ^# p3 d* i. t4 f8 [% K5 t' s
    def factorial(n):) G7 ~/ Z+ d+ w0 @% @) {
        # Base case
    / a: C/ q# `2 K" @( E    if n == 0:: O. a, C  R$ ]1 e1 b
            return 1
    4 J* }- V& A# C& {/ t. C$ h    # Recursive case2 N- C& U9 D9 p( [+ j
        else:$ T' |/ n, _, L
            return n * factorial(n - 1)  P3 A+ P( ^6 S9 ?' T
    / z# S0 t  r0 {
    # Example usage
    & n4 y8 \8 c( ^3 M$ S! hprint(factorial(5))  # Output: 1201 f) m/ q2 V/ u' Q- E& t% l  U

    + i# _) Q5 U7 C5 _; HHow Recursion Works9 \* `: h- F3 h2 {  ?  X
    + p( H- i6 p  p) v( v# n* ?7 \
        The function keeps calling itself with smaller inputs until it reaches the base case.
      K0 ]/ @6 t; G3 [: r
    5 N5 V6 I0 m$ g* G    Once the base case is reached, the function starts returning values back up the call stack.! p+ R9 L- H" l, E7 _
    + Y1 p( _% g5 R; K" [9 P+ W, E/ |
        These returned values are combined to produce the final result.
    8 w9 q5 ^8 z2 U# w; `8 E1 R5 t4 z/ d
    7 v' Y$ x! K5 o( R/ EFor factorial(5):, r, t, C5 [2 @' E2 O# w/ @
    2 m8 ?' X: ?* _+ A

    3 h7 F8 R4 N, U6 H/ `2 \# B& Efactorial(5) = 5 * factorial(4)% M- s0 U% T+ I" |# u: B- k) L" H: c
    factorial(4) = 4 * factorial(3)) _  _7 W. i- p; S
    factorial(3) = 3 * factorial(2)
    2 e6 B6 P. g) m; G7 ?$ M+ cfactorial(2) = 2 * factorial(1)7 h; @. A! k9 M8 i( f; ~$ c9 P! x, K3 s
    factorial(1) = 1 * factorial(0)
    6 F5 x% n7 E7 W7 C: e7 ?# d% Afactorial(0) = 1  # Base case
    6 c1 A3 G1 y+ v( F: [; F( C: n7 h  q8 |
    0 x4 K5 w9 L% T2 ^  z- l  `Then, the results are combined:( A1 I- [) b; t, y, B+ x+ ]8 Y
    & ]; B' p- l- l5 u; O
    & B- e. [' s2 i7 s: z0 h9 K' O
    factorial(1) = 1 * 1 = 1
    - B- Y4 G2 ?. j5 ?% b. Yfactorial(2) = 2 * 1 = 2
    8 `# _, T5 R, q3 R9 i' u2 E2 A! |factorial(3) = 3 * 2 = 6
    / f. N* c- z4 c6 W; m$ X5 j( h2 R) G* Xfactorial(4) = 4 * 6 = 24* z  B: F% ^0 C( }& P  L
    factorial(5) = 5 * 24 = 120$ T3 m7 p9 e5 F% u# C- H
    & g2 \/ K  W/ x) Q- l
    Advantages of Recursion* v  [; V- h* _" w: x

    $ u. ]$ C7 `  v. @$ p    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 W# T9 `2 k" J0 a1 t! C& j7 E' h7 c+ y2 m
    - v. P( n- d* o$ Z/ V# X) y- G    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    ' l9 n) Z, a) m- ~$ J0 x6 ^- r' U! e' w& [* L
    Disadvantages of Recursion+ O( ^) W2 O7 Q$ R" R0 o" J

      e0 s0 P; [# N  k( y3 F    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.
    ; s+ L& ]4 p# d5 c, D$ u0 a7 y( n, a. D% O9 t
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
      {3 F" R( @: F, f
    8 a6 X+ l8 l6 P. }When to Use Recursion
    % {% L& p5 }- Z8 u
    ' y2 `6 Q' t7 D    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).* B8 L, q% @0 b" I) C. e. z+ n! [8 o* l* y

    " d: @3 ~( I8 |8 }; N5 D    Problems with a clear base case and recursive case.
    , q# V! |' m& d7 X  W3 j* s9 p7 f3 F- v# d+ V' G: o
    Example: Fibonacci Sequence
    9 S: L; X9 U, s% `, e/ Q1 i  C4 ]3 J; V5 Y
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:, w3 E6 _) U: G

    / }4 Z2 t; ^& q! R8 Y* B    Base case: fib(0) = 0, fib(1) = 16 z, Z5 j5 R  D. F5 R
    7 L" @3 {2 ~! W9 i$ u" `
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    . j" |- Z- u2 X7 z# ]4 i
      d1 L9 W4 k3 d3 X) l& ~9 p% Gpython
    & ?; b( j- G% m: j
    ( L$ K% U+ x$ R7 l/ t" d# t/ b1 X/ X+ @' _5 X
    def fibonacci(n):
    / c* c' x( T' W7 K0 Q    # Base cases
    8 ?3 p3 z  I; q* p0 o- e    if n == 0:7 B5 Z# B6 R1 Z7 R/ X
            return 0
    & @6 Z- d2 R" e# x6 k) _3 q    elif n == 1:
    6 D& i' i: x* H        return 1
    6 q: ~$ y9 |! K+ G    # Recursive case: Z( J+ a: [+ @6 I' ]
        else:
    - G; Z& w7 j6 ^' H        return fibonacci(n - 1) + fibonacci(n - 2)
    # @+ ~  v, D& F. L3 l
    ; Y) }7 ?8 o1 g& X. d# Example usage
    ) L6 T; M  h0 a. a. z, ^print(fibonacci(6))  # Output: 8
    1 U! M$ \- v5 \9 S9 E- {9 i. ~, B0 J& m
    Tail Recursion
    ! w7 ?" K$ h3 J
    + [! k  `- q' ETail 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).
    . t4 }3 v2 z3 X* O5 v: {8 t# F3 |0 V. p
    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, 2026-2-8 22:01 , Processed in 0.059508 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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