设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 4 L+ ?% R. n6 X' c' A# V  R0 s" |

    - X* d: k% D! C$ p7 @' f解释的不错& w' F/ L) `8 r& |

    5 R4 N) \. n; |5 R% Z- X. a递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    $ v& R  [) ]2 H0 f& G. R7 g7 X/ @! D! M' z
    关键要素
      T  l! c; X7 Q; A2 v, a9 ~- X6 n. a1. **基线条件(Base Case)**) t0 t- k' [5 u3 D: X
       - 递归终止的条件,防止无限循环
    * j. h  B1 O. I3 j   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    + [. ?9 V3 ~! L. I2 g9 A! m8 u6 G: k4 R
    2. **递归条件(Recursive Case)**
    ! ?. }& n/ N! Q( _   - 将原问题分解为更小的子问题
    6 R, p% D1 j' W# E* |! n% a   - 例如:n! = n × (n-1)!3 r5 Z. {4 `) l$ `: I5 Q

    6 Q7 Q% Q1 \8 J" h" g: @8 @ 经典示例:计算阶乘8 V8 r" M; m1 {- Y+ [
    python
    % a( ?0 j) ?% v* |) ~/ udef factorial(n):
    / f6 ]& N$ d4 Q    if n == 0:        # 基线条件
    & w8 P9 k' Y3 [6 Y% M( A9 a        return 1
    # J5 P/ r" k! _" B    else:             # 递归条件4 s8 t  i, j( t0 `4 F  `
            return n * factorial(n-1)+ A' j, Y+ T$ m9 r. `+ I( d( G
    执行过程(以计算 3! 为例):
    ' p2 D* ^7 T0 Sfactorial(3)$ c1 u- q3 r5 d/ i7 b6 B( R5 {
    3 * factorial(2)2 L$ S2 w" o' Y' W
    3 * (2 * factorial(1))
    , u, n1 y" `3 A8 ?% l& d3 * (2 * (1 * factorial(0)))/ N% c7 M7 [8 [
    3 * (2 * (1 * 1)) = 6
    0 M. a4 m( Y$ X3 q7 F1 D9 N8 u' i3 K: j  a$ f& r
    递归思维要点
    & {0 L- m* |6 {1 K) W! d1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ; @; w# S/ L' b+ z: F: \2. **栈结构**:每次调用都会创建新的栈帧(内存空间)' e6 C4 s$ B% E
    3. **递推过程**:不断向下分解问题(递)9 `/ j$ {0 p# h! b) C
    4. **回溯过程**:组合子问题结果返回(归)
    ( }5 M9 p* W6 t9 H$ ~% L: o* P* @! Y7 t; f9 E# P- c+ n& R; q1 [
    注意事项8 z* f- |& p5 y: n# X3 h, f
    必须要有终止条件
    6 W  q* r8 B/ i& Z3 R/ ~$ n递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    4 j) f! Q3 m1 v0 e7 N8 O某些问题用递归更直观(如树遍历),但效率可能不如迭代
    / G4 r$ \. H  v  @+ _. k/ ]尾递归优化可以提升效率(但Python不支持)3 d2 c3 @6 r3 V. r3 U" w

    + N& {, M% {/ \ 递归 vs 迭代
    . A& i& e2 T6 j|          | 递归                          | 迭代               |2 R( J  E9 r  m3 w# x
    |----------|-----------------------------|------------------|& {3 u' S8 b+ P/ |# ?: |
    | 实现方式    | 函数自调用                        | 循环结构            |% ^. X, Y% `! V* H4 c5 a
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |5 u6 J- ?# v% i5 e% a
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |- i2 _( ?, \" [1 w" M$ _
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    6 c* }; e( _; D; y
    # n/ B3 s% `' s+ G1 p5 z- Q' }: r 经典递归应用场景
    2 k, T* M5 f+ i. s& K1. 文件系统遍历(目录树结构)- U+ p( G' q' ?" G
    2. 快速排序/归并排序算法& |$ ~1 Q" _& j0 c
    3. 汉诺塔问题7 Y4 D, _+ {# |6 ^0 I  r8 `# `# L( @# m+ r
    4. 二叉树遍历(前序/中序/后序)
    & ?- n$ s8 v6 ]" Z* `- h5. 生成所有可能的组合(回溯算法)
    ( R5 b; B% N4 J8 O  t  V1 S4 o* o
    , m  H: L5 @1 V$ N# d5 q! ~试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    郁闷
    昨天 07:28
  • 签到天数: 3152 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,$ M. b' v* G& e2 @
    我推理机的核心算法应该是二叉树遍历的变种。8 H8 |6 a3 B5 m- W( N; q4 R2 p
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    # }; K" G8 u! D. FKey Idea of Recursion
    ) S4 P9 q, O2 J
    0 e1 n0 e/ \+ b  i( t% sA recursive function solves a problem by:0 w1 \+ d, O/ a- h+ U
    / \0 ]3 E/ C& C; j3 ~) D
        Breaking the problem into smaller instances of the same problem.6 Q1 {4 w/ `! x) Z
    ( m1 j* Y/ g! K. N, G& o2 ]
        Solving the smallest instance directly (base case).3 Z: g: T% {5 {1 k  m4 U: x

    4 p) {- u: Z* P+ g" s  b" {! M. c* N    Combining the results of smaller instances to solve the larger problem./ j" [! B" T4 Y% {5 K/ Q
    . `9 N2 q1 N9 T1 m/ \  a
    Components of a Recursive Function+ Q) X0 l! o$ S0 c8 P

    5 O4 D5 F+ U6 R5 @' R    Base Case:) h' v3 n) I8 V: e

    + j- m8 z! t; Y: y% T# ~3 g        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    # K$ S$ X9 O  F5 q. D2 F& |5 `
    7 U/ O8 e5 r6 F' w" @/ s  J        It acts as the stopping condition to prevent infinite recursion.
    7 r* \. e& m& f1 w( g: A: ]' K$ y" H7 e5 `/ B
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    . x  `3 {4 ^/ j  [7 J- g" Z" y; }( \
        Recursive Case:8 b+ [/ V! \4 q: E
    % d) q% A- k  Z/ g* C
            This is where the function calls itself with a smaller or simpler version of the problem.# Z' E# l  }8 P& r
    : z6 w3 b( f: ~, S+ e8 Y
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    * j& p1 ^* g0 ?- ~, u8 ?
    3 O0 S( ~5 E7 A! ?+ k% X* i, f& E2 sExample: Factorial Calculation2 x) ]' r* f' t

    4 n# [3 u: _  B) Q; nThe 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:; ~( b6 `% e; k! a
    : J  M4 v  U6 n% V1 x% G% A. y* P
        Base case: 0! = 1! I$ ]8 Z* H( z) c3 ~; K

    8 j0 G5 L9 Q3 w  {    Recursive case: n! = n * (n-1)!( F) ~3 C! U) _" v8 [( W) {
    4 `) i/ M: z8 `# Y  P; M6 ~
    Here’s how it looks in code (Python):
    # @$ m  [, F+ _. l* r5 ^1 e# Mpython
    * A, I4 @. O! w/ `* x' V9 @8 }( a, J0 J! Y  r, X6 U

    4 X: N0 x5 W! X3 sdef factorial(n):( o) L* J" ^; j8 u: e0 S; N8 a8 {
        # Base case8 b1 ]; N* L% u4 I2 L
        if n == 0:
    4 |; ^, F: |# E, f        return 1& s+ U  E, m# M8 g0 ^
        # Recursive case4 V* h8 ]$ g$ A" J
        else:
    * `1 h8 U8 W) J0 r6 b( r- {9 U        return n * factorial(n - 1)1 E. C: M' @1 d6 X. u; p$ I* o' l3 x

    4 i: D' |( J, C) E' Z6 h3 \# Example usage
    ; x$ |' d5 L/ T1 P! dprint(factorial(5))  # Output: 120! G/ [$ [2 x+ y
    1 T+ E) S& g  Q9 W; X
    How Recursion Works: X- h# j" ~, F1 j1 K/ Y

    6 O/ p) l$ U: M9 g' J0 F5 }' x" \    The function keeps calling itself with smaller inputs until it reaches the base case.
    ) m$ ]1 ]# T7 r' D+ w4 T! E6 S3 }- F7 s! G5 d
        Once the base case is reached, the function starts returning values back up the call stack.
      C" w2 q, m) a
    3 g- n6 `* f! b8 A5 r    These returned values are combined to produce the final result.% a& c5 v5 @2 J$ f: W! \# V, k

    ! P0 w+ {) g( v1 L( i* P3 d; yFor factorial(5):
    $ b; C3 j1 J4 E4 I1 G# t* o  L9 q, S

    7 j& Z. k) y, \8 A1 Sfactorial(5) = 5 * factorial(4)" N0 E+ U$ w- h& H# x1 E
    factorial(4) = 4 * factorial(3)
    2 F& h( p4 A' [: j0 P, ]0 q1 `factorial(3) = 3 * factorial(2)7 X: P' C" z: j9 a
    factorial(2) = 2 * factorial(1)
    ) h( v: I# P0 g9 J! Ffactorial(1) = 1 * factorial(0). U# S+ D/ g( y$ o* }6 U3 X( r) ~
    factorial(0) = 1  # Base case+ H: ^  B' v1 R6 v- ?

    ( L2 X0 O) u$ O, A' H; G+ mThen, the results are combined:" W, j4 T2 U4 i8 d: m
    # E, A/ s. _- b7 k
    9 ~+ r- G7 w& R9 U
    factorial(1) = 1 * 1 = 1
    . ^2 D: L' T1 x% E/ o1 J0 c1 t. Ffactorial(2) = 2 * 1 = 2. w. c6 v7 P, r6 V0 q' ]: b
    factorial(3) = 3 * 2 = 6
    6 g( r1 X5 \, @  `" P2 }/ B' g; y  }+ vfactorial(4) = 4 * 6 = 24
      l' F& N6 G# c5 U* gfactorial(5) = 5 * 24 = 120
    ( k- w9 D1 \# \3 L1 _  I- S/ ?" U; o0 ~# K6 [! v
    Advantages of Recursion- G5 X# m8 g& @: r! N
    * o8 f6 G# Y( V, R
        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).* v2 w& }# c$ g" v0 D' s8 R

    : q. t" l3 H" ?: l3 E    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    7 A- e# D+ a# F5 c/ z* g. ^4 s1 @7 U( x
    Disadvantages of Recursion
    % _3 s$ D" S8 q. ]9 v
      q% e  K) J8 o    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.# B2 |% I# n; {8 W5 m

    , S& s4 I+ [  K' g. S* A% J    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ; d; b9 z8 L" ^
    2 y4 l* i, X0 R% F# qWhen to Use Recursion/ a( k7 ]8 Y; |* F# T
      y8 r. K+ B2 S, U. B! d4 w. k
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    % [# |( \: B' f; N
    7 g) d" q" h( v! D& R2 l    Problems with a clear base case and recursive case.
    5 @! ^; ?' T9 G0 m8 W; {$ c* T+ l; K$ y; C5 O
    Example: Fibonacci Sequence
      Y, S7 _" R1 z: G/ E. P" g- k4 j6 o4 A* }1 a+ v0 w, \
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    " H& X5 _' T1 Q' m  N7 c1 y/ f; v; Y8 K7 w1 ], K- U- C
        Base case: fib(0) = 0, fib(1) = 1
    : ]) q$ W( V& g6 e& ~' J4 C2 M8 W: S# N/ T% I8 B+ x
        Recursive case: fib(n) = fib(n-1) + fib(n-2)8 \3 s$ G9 V$ C1 `5 i$ C/ m3 ?2 Y

    : n& i; i4 ^) apython
    % S" f& ^, J3 z- C" ~0 `; t
    ' [  Y( F, g- y- E
    # e( h& N7 a) v9 j4 Q0 D2 x0 cdef fibonacci(n):
    ( R/ L, ^' A- k0 g3 j    # Base cases
    ' _( a5 }5 D! |' C! w, }    if n == 0:
    ) x3 D6 r6 e/ {        return 0
    ' g6 h5 d- p1 V4 l1 g4 x$ @    elif n == 1:: ]  \' U. }5 p! ]
            return 1& W! G' t9 [! Z# }
        # Recursive case
    5 _2 L$ E: c9 z7 z    else:
    / A6 g7 D7 C+ y* d        return fibonacci(n - 1) + fibonacci(n - 2)5 j7 `& p8 ?& O4 y- }

    % a( Y& T+ }0 P( V1 b# Example usage1 @  c1 C- H9 {1 R6 v8 {) b0 w
    print(fibonacci(6))  # Output: 8
    4 C7 p  G6 L+ d8 a  D& Z' ]
    ! P9 S$ b  H/ ~( V$ o3 A" A4 `# OTail Recursion
    ! I. H6 \' \# J4 ]$ t- |- ]! a2 x" }/ O9 q' Z
    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 W' _5 t1 x/ i$ B
    . J6 \3 w! t7 O$ T. {( H; J
    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-1-24 05:12 , Processed in 0.060438 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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