设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    3 l0 Y" J2 g' J0 O) |" d& m* f* G0 u
    6 J+ ~+ J5 [; v  l! E5 a0 T, [: o解释的不错; D3 W( M  `- |$ i. R8 I6 j

    4 C; y  ]) g6 K9 J4 j递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。0 w2 @* g+ [6 {- l  b( L
    5 k, S/ t* m( H4 D/ s& f. }
    关键要素
    * d" p& D2 x3 B& Q4 J4 |1. **基线条件(Base Case)**
    . y% q0 ~3 C& d& r2 P8 m   - 递归终止的条件,防止无限循环
    % K$ }6 ~4 s  x+ |& I1 ?   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    ; v7 ~9 t; n" s" @* P. X7 k  W( j9 [$ k. T$ o. y: K
    2. **递归条件(Recursive Case)**/ p3 g& u  _; ~
       - 将原问题分解为更小的子问题
    4 y$ p' d( m6 `: {7 v' y   - 例如:n! = n × (n-1)!
    + y* V: Q* S, ^
    ' b4 a9 \) l! e8 i( X 经典示例:计算阶乘
    ) }% {3 i( g  t3 w' h1 xpython) L+ U$ f7 x9 I6 S6 g9 U+ |$ w
    def factorial(n):
    ; e5 a1 y, e6 R  y. _& R, x    if n == 0:        # 基线条件
    & o) G4 w7 Y6 Y        return 15 q( L- E& ~1 K9 v
        else:             # 递归条件* |  P" x9 e$ x3 e
            return n * factorial(n-1)9 N' c6 X: \  n& c
    执行过程(以计算 3! 为例):7 ^7 G/ j" F/ v! Y# K9 E
    factorial(3)3 [( o$ t0 W! {2 x! O8 N+ _/ ^
    3 * factorial(2)
    7 O5 _4 |5 E; T. n3 * (2 * factorial(1))
    / f1 ~% i3 N- o7 _# ]2 y3 * (2 * (1 * factorial(0)))
      C+ A6 {4 P/ v  p2 _3 * (2 * (1 * 1)) = 6  c$ h* Y1 p0 [4 s6 g9 g- G

    / X$ x( c4 f' c+ Y 递归思维要点* n) J  P* {5 V) \. z5 H* A3 J
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    * H: H- C; k. U' |# G1 R, D2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    / B0 M; H3 o  w+ S3. **递推过程**:不断向下分解问题(递)
    . c0 ^- K7 ]7 ?8 D% {4. **回溯过程**:组合子问题结果返回(归)
    5 e9 b* A) P7 d0 [+ N) O7 u1 R
    - }+ |& [+ G5 l2 h# ]+ ^ 注意事项
    3 m7 |. ^2 [8 i3 S; G' @必须要有终止条件; ~3 X- |& N, }9 N1 x
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)$ y6 M8 l5 q/ @+ E
    某些问题用递归更直观(如树遍历),但效率可能不如迭代8 P6 M' J- w4 u2 M
    尾递归优化可以提升效率(但Python不支持)8 H: h2 D6 ]8 k1 H" U) G& v) \
    % A3 W' i( f9 ?' ~! |! ~9 R
    递归 vs 迭代
    3 {  \/ H& U, S% _) u6 q|          | 递归                          | 迭代               |
    2 i2 p8 c- p" F$ e$ E% I& V: `( d|----------|-----------------------------|------------------|. L7 ?" F* X6 @9 S& @
    | 实现方式    | 函数自调用                        | 循环结构            |$ M# q; y+ L% ^5 v- u  Q7 X
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ! x! O5 w/ n* B% {/ f| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    , A, G5 |1 r7 p1 w, t; m| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    ( ?; f( o8 W  J$ G! ~! L- H( O
    - n1 ^- n3 }7 l8 J5 s 经典递归应用场景
    1 A: @  U  f# [- v* q, k2 f* X1. 文件系统遍历(目录树结构)! o8 c) }$ Z3 W% a& e3 I1 X4 g
    2. 快速排序/归并排序算法4 G  [) ~. P4 h! Z( T
    3. 汉诺塔问题
    : }) _" V. ~1 J9 H  M4. 二叉树遍历(前序/中序/后序)% N# b6 w. m; D: k, Y
    5. 生成所有可能的组合(回溯算法)! v/ x1 Y# C. L) T
    : X3 W( W7 V( D* Q; e
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    郁闷
    6 天前
  • 签到天数: 3208 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    5 w7 Z  P6 O% F我推理机的核心算法应该是二叉树遍历的变种。9 J. q+ ]2 G3 R6 p# ^; s* q
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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. K6 Q1 P5 O: ^
    Key Idea of Recursion
    " h2 T; c  j4 Y2 h
    $ ]- q! g# v) C8 o+ ~3 _7 nA recursive function solves a problem by:% Q+ t& w# t* J/ L  m2 ]4 c+ T  M

    4 d: N# M) `5 h$ K- Z    Breaking the problem into smaller instances of the same problem.
    ) v) P- I7 @2 ?0 S( R& B% p
    # ]( o1 [- }) V  Y    Solving the smallest instance directly (base case).0 d  [4 V( q1 ?4 Q7 e: ]

    & m- s* ~% F2 K3 f* S9 Z    Combining the results of smaller instances to solve the larger problem.
    - R9 I1 i" s9 C! P9 ^/ |5 w% Q( n; i/ b1 U# C/ @3 k8 a2 f7 `
    Components of a Recursive Function0 w. y! \; h3 i- O

    & A& H; c1 ?: m" b3 P    Base Case:) r# [$ \: y9 o9 v
    ; G; X1 d: m2 a3 D6 U: U. i
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.; m4 S# d" d4 I3 }3 h" M- \& I
    + \5 j. ?0 Y  J& Z
            It acts as the stopping condition to prevent infinite recursion.! J% \3 p% Q2 C* Q: h
    ' g1 h7 X) F5 O" x! `9 i: Z; e' F
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    + B! d# ~. z1 ~- A
    , B& I; }8 F6 l6 ]/ Z; K    Recursive Case:! {! @& j' f3 [2 Y% B
    9 j' ~5 V$ ~( F( `
            This is where the function calls itself with a smaller or simpler version of the problem.
    1 D2 W# T& l; |  a% P% H4 j" `7 O; @3 O
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    & C: g3 s/ W- [/ P& G# ^9 \) w6 c
    7 p. \5 ?( r7 [8 `: XExample: Factorial Calculation
    % u3 H. L2 U1 @4 u; }0 ]9 Z. \8 d6 @3 [- \: V1 i. ?1 x. n! b" ^7 W8 ~5 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:
    7 _/ g* F+ o; K* g
    0 z: C* t' d6 S" U    Base case: 0! = 1
    8 F) E/ o" A% |% A% D4 l
    8 v: y2 R, N$ P4 R, M9 |, H    Recursive case: n! = n * (n-1)!. L& k+ w0 r; N( h# o
    * w( ^5 r5 F: t7 ~  Q% e" _6 F$ w
    Here’s how it looks in code (Python):
    1 w% L3 u. S3 m. ~python
    % j5 k: s7 s' b5 ^$ s/ p4 p& L
    # ]. X5 o( Y2 v( b+ U/ |+ j+ |- B7 k/ j
    def factorial(n):) x9 h+ V0 q2 T
        # Base case8 T! l9 E/ n( j1 _, U( R3 Y
        if n == 0:
    3 m+ a, n- N* P- N        return 1
    4 G; G2 K" ^8 j. U6 D% ]6 ?    # Recursive case
    8 `; L+ }  ?3 u7 p$ K    else:4 `* ?1 Z* v  ?2 I2 N/ a
            return n * factorial(n - 1)' d, ]9 o0 A* X
    5 z! Z& k  R0 D5 g
    # Example usage3 [, C1 F9 M" Y9 e3 ]; G
    print(factorial(5))  # Output: 120
    3 }0 D# F0 I0 m( y7 {1 k
    + ^; V6 D, S5 ?: IHow Recursion Works/ n1 t+ I1 h! F( R0 q  L

    " D5 ]6 j6 s# m- D8 f/ |    The function keeps calling itself with smaller inputs until it reaches the base case.
    2 x% y5 S" l- n7 p6 M/ z+ M& a# D8 N5 F
        Once the base case is reached, the function starts returning values back up the call stack.
    7 h" o; j$ c: b. U9 ?3 h# h
    0 p4 v* V& f2 X$ W    These returned values are combined to produce the final result.7 y1 N) J# o  T" {8 }0 |3 q

    $ }! h  u+ w4 f* u& n3 OFor factorial(5):9 z0 [  u: y! w) Y5 k/ [5 ^
    7 `* H$ W9 T3 _9 P
    ' s+ d: h7 j  j  ^# r- m
    factorial(5) = 5 * factorial(4)3 O( m% X1 a. Z+ {& ?
    factorial(4) = 4 * factorial(3)6 G$ V; o6 ~2 P( U, ^
    factorial(3) = 3 * factorial(2)6 i7 H/ Z/ R$ t# V. d6 q' w( U$ [
    factorial(2) = 2 * factorial(1)5 n+ l; P+ n, {1 R! C7 z8 ?
    factorial(1) = 1 * factorial(0)
    * S; z- ~% y& cfactorial(0) = 1  # Base case
    % g& i4 X1 h/ u4 \1 }7 ]) l+ D9 u6 q) S- |
    Then, the results are combined:
      U- c, q+ z' k( [2 ]5 I7 \( h- c8 Z& I+ n& A8 @- @5 ~

    # f8 k7 z" D( Nfactorial(1) = 1 * 1 = 11 P$ Q3 R3 Y* V# B/ Q
    factorial(2) = 2 * 1 = 2
    ) D- g1 O/ Q3 o, g1 Ffactorial(3) = 3 * 2 = 6
    # K& `, X1 ?$ X$ s( M! `factorial(4) = 4 * 6 = 249 {4 U: s: K/ d3 ]% c
    factorial(5) = 5 * 24 = 1203 ]# d  M* V: v

    0 F! D6 k# U: S1 N4 O) H0 W3 eAdvantages of Recursion
    & U5 y& d& s, S1 z$ E" O- ?6 g# c2 S  ]3 G0 M' o. M
        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)." P  b: q" H6 e3 G
    " M4 a: C4 z- {1 [6 P
        Readability: Recursive code can be more readable and concise compared to iterative solutions.$ m& a+ ]' W1 h; W) U

    ) k& x' v& o2 q/ C( XDisadvantages of Recursion
    # B' q% O9 x" E* m- E! M3 h( @" e& X, t8 B2 w, _* l) U
        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.
      v; |1 F1 ~  \9 f2 k
    4 K  j) L" d) @" r; s4 @    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    & J! C+ Y6 {- m* {" w' m
    " s* o0 V7 J. MWhen to Use Recursion+ [2 z% X; k2 y! T
    ! x* Q- R( c- b8 `) i
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    8 J8 ^+ f0 i! k; Q% ~2 {& C/ ~2 S/ ?: P8 p1 [
        Problems with a clear base case and recursive case.5 k/ ]1 F! `: M& A" V2 V
    & }& ^% N& N1 M% s3 e
    Example: Fibonacci Sequence
    ) t$ [+ O4 g+ V" k1 k5 |! @' u9 b8 f$ C; P8 Y
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:: q3 ~4 \8 h. D9 l

    # D, F* Q8 F; V& V! ~4 G+ L  _+ s    Base case: fib(0) = 0, fib(1) = 1
    : M7 ^! z" t; M0 |5 U2 M$ {5 y5 M& z* e+ P) T; j; {8 V9 e: J
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ' g3 T  a) f' T8 r  F  S
    * O- l' _+ U- ~+ Ppython
    ! f& v: L: Z) w+ C8 J. g7 b9 d4 Z# Y+ u( N- g

    8 Y5 |) R8 T5 r: _- Z! w  `def fibonacci(n):& K1 L" q2 F8 ?
        # Base cases- l# I4 h2 t/ X# E
        if n == 0:2 O$ \" n$ }5 e1 ]* N9 q/ u( g
            return 0
    + Y- u  H6 ~& c6 U* d    elif n == 1:
    1 @/ H4 e% f$ d7 \8 x( ~        return 1/ X1 C2 j  v9 K
        # Recursive case/ O) C( x2 V# y
        else:
    8 c. m8 z7 X0 S* H1 `- P        return fibonacci(n - 1) + fibonacci(n - 2)* m& P- R- x0 r& @4 ~0 k, F& f

    9 `% ]7 |$ Y, s# Example usage
    / J6 N0 ^5 c  U% ]print(fibonacci(6))  # Output: 8# c0 J: z- z) Q1 d0 ?: v0 A4 s
    4 M5 B; L  @; K( [! V8 Q0 V3 L( Y8 ^
    Tail Recursion
    ( E' ~# S! f3 t: i) S% u( \3 @
    4 o# u- ~4 M; ~* O2 Y$ vTail 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).& E  V  c' d* j2 P, m9 X
    2 m# c2 J3 U% j- c( m  |! @7 b
    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-3-29 13:14 , Processed in 0.074878 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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