设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 * t" U" J# b$ i9 F: t

    : E* L0 s! X0 E解释的不错
    6 H% _  U# P, v
    : E5 n5 ]# [/ Z0 y递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。( D6 d" n" g. [8 b  U; f  J9 l7 r
    , ~# S5 l6 Z" d! [* v* {
    关键要素6 r9 y2 m# ^1 M+ n! N
    1. **基线条件(Base Case)**
    ! D, M, x2 X' l+ m3 [% H: U   - 递归终止的条件,防止无限循环) P+ M3 g0 H+ [3 {1 I
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    : T* m, d5 d$ a* e, g* o9 E, ^5 Z# Q: g- H7 O" D/ E
    2. **递归条件(Recursive Case)**
    , I2 B- |0 s: w' m9 J  A& J' @   - 将原问题分解为更小的子问题9 ~: K/ u; ~5 C+ _; d3 S/ W  n! B
       - 例如:n! = n × (n-1)!* M4 u$ v  t" q4 g  K0 T

    3 Y9 z1 X4 f9 C6 i 经典示例:计算阶乘  p, r+ ]) @! w
    python
    ! a8 ]+ }) U4 w9 p8 G0 sdef factorial(n):
    9 w% ^' W4 U- {# j    if n == 0:        # 基线条件
    9 t) j2 c4 b2 U8 S( E$ t        return 1
    8 W: s" R+ f% D3 A- P: y4 k    else:             # 递归条件4 d' u+ p% Q5 Q7 J- q6 r1 d2 j, |4 {
            return n * factorial(n-1)
    - G+ l2 F8 z7 S  V执行过程(以计算 3! 为例):( `, s9 Q" s: e) f: P
    factorial(3)
    ; y/ }7 S4 G. B* e0 }3 * factorial(2)* O, a% W7 z  m
    3 * (2 * factorial(1))9 _3 G( M# u1 p: b# O
    3 * (2 * (1 * factorial(0)))! ~! w0 W: H; l  l5 M& q
    3 * (2 * (1 * 1)) = 6
    ' V/ N2 C3 O" W' R; v) n' w& A  k( T3 q7 u
    递归思维要点
    ( G7 B$ T* _8 C+ C5 ?8 m1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ( B8 Z$ `, B4 I6 O+ W2. **栈结构**:每次调用都会创建新的栈帧(内存空间)1 d5 F! L2 s* N
    3. **递推过程**:不断向下分解问题(递)9 _' D  J7 `2 B# F0 M" l! l
    4. **回溯过程**:组合子问题结果返回(归)
    ( S+ D3 n0 b3 ^4 I# |" F- Z" b/ a- v8 t5 X3 V
    注意事项
    ( m8 w; o& z7 t# E必须要有终止条件
      N9 n0 ?" A  ?7 M9 }# i递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    3 }0 g- C* l1 e6 H某些问题用递归更直观(如树遍历),但效率可能不如迭代; C, O( s% w+ \3 S5 b
    尾递归优化可以提升效率(但Python不支持)! ?7 d; B3 B0 u
    ) w6 `, C  k; Y% h7 l( z
    递归 vs 迭代2 I5 L4 x; l: X% t
    |          | 递归                          | 迭代               |+ k* k7 P& b: [( _, \+ N
    |----------|-----------------------------|------------------|! @4 `  S1 W  m2 I8 j+ z( [
    | 实现方式    | 函数自调用                        | 循环结构            |
    + b" h6 G; \5 k+ v| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |! b2 }" d, N! Q6 g2 J( Y7 p/ B- v
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |1 ]- f8 S. i  V/ i8 u$ y+ ?: M8 y
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    2 C6 g+ l# }9 P9 U6 V& q5 L& y5 k5 x6 P5 v' g
    经典递归应用场景' z3 l  T. J& c5 M4 E
    1. 文件系统遍历(目录树结构)& a, |9 a, V1 d# ^3 a4 Z
    2. 快速排序/归并排序算法
    : J7 L. d5 \# a3. 汉诺塔问题5 z/ l/ M6 |" S5 d( M: V
    4. 二叉树遍历(前序/中序/后序)/ z$ f- j" B  h2 X* E
    5. 生成所有可能的组合(回溯算法)
    - I6 F- Q8 d  h! l& \5 k' w  L( U+ Z" ~) I  k% |# W. k1 M
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    昨天 06:43
  • 签到天数: 3101 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,4 B( ]; g5 {3 K! f- @4 R4 O' ~
    我推理机的核心算法应该是二叉树遍历的变种。8 w) v3 w3 j2 v
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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/ B7 a1 |8 |( {1 `6 `Key Idea of Recursion
    , q. _# Q+ _1 i: N+ y9 N3 M* U5 f* X" h
    A recursive function solves a problem by:
    ! H% e5 n( b: p! q5 }$ S5 T" t1 Q% x# J
        Breaking the problem into smaller instances of the same problem.5 z+ V/ O4 j4 r- F8 B/ y$ E

    ; m' z! ]" U( b, P    Solving the smallest instance directly (base case).* X1 H5 ~& p0 V3 n' _2 e

    ' N0 n8 |$ {3 v2 f    Combining the results of smaller instances to solve the larger problem.* S" B( G7 j& r( C! A8 V# D

    " {- a, ~" E6 z; XComponents of a Recursive Function
    # \9 x3 ^6 D5 Q1 |+ Y# _- I5 A
    ; E  _0 W5 e. t) m    Base Case:* @2 @% X7 \5 W) N+ C. [
    7 {: l$ j% m* l* Z
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.) G* X  O8 |+ k! w( L# |7 A
    . [/ s+ A* ?0 h8 _9 [( \+ R# e
            It acts as the stopping condition to prevent infinite recursion.
      m. g+ h! \' L6 S5 W2 E8 O& ?( n
    7 I  o  u( L' }% {! p& o  W9 g        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.1 t& i/ K# Q* I& u0 F: p

    - x) {9 W: c1 S- U    Recursive Case:0 Q+ L' z' Q: Q% C8 e9 q

    ' l6 J) f# v7 I( F* X        This is where the function calls itself with a smaller or simpler version of the problem.! J4 a. X" E! T& o7 a

    ! H6 v1 j7 \0 n+ n2 O  ?8 a        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    1 K$ }& l- `3 [" Q
    8 S! L8 o& p+ i* LExample: Factorial Calculation
    2 `" h4 H. w/ ?/ T1 F, S7 S7 [& u  _# ~2 C7 I
    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:( U8 b" p6 p. ~. n( o5 b$ `1 B; D

    ) h, ?' P/ g) u+ F/ p/ J# W  m8 b    Base case: 0! = 1* e4 L# u( C$ j0 U. x' E

    & d2 |; l. P( D    Recursive case: n! = n * (n-1)!9 }! E6 ~6 j9 M0 G

    $ `: Z% P3 Q7 f  @, |5 t% ?Here’s how it looks in code (Python):& U% J/ w* A% e7 i
    python# p! O. W! F# k. |! N

    , g( \9 F& h; M+ e7 V' I* @* T- d3 g8 O! \  v+ ~
    def factorial(n):
    ( D+ X) O6 }% A4 ]    # Base case  U7 Z7 Q2 L0 K& F1 D4 P& M/ I  Y
        if n == 0:
    ) S% F3 X8 k% z- Q        return 1
    7 d$ V0 k$ @  F, W+ I# j& p    # Recursive case
    # ~& L% h( Y$ T# `" G2 j2 l    else:! g) m  M0 J2 q3 R# f# `7 Y( i) Q
            return n * factorial(n - 1)5 v& p- |9 E# D. e; x

    7 `" Z- ]) E4 o+ K' M# Example usage
    ! C+ ^) R  `9 c, J1 {print(factorial(5))  # Output: 120, \& C" ]$ {: e9 n. H) T7 N2 |0 x- u/ C

      d2 P  d* a- I# b3 Y7 Q$ GHow Recursion Works
    ( p/ z, H1 B( B
    6 ~9 l# b# g3 D5 i0 B    The function keeps calling itself with smaller inputs until it reaches the base case.8 F" l# ?8 [5 \8 f* M! p$ u

    ) I& M7 B8 F$ {    Once the base case is reached, the function starts returning values back up the call stack.- Y$ x, }" W4 K1 f7 h6 y  o& I
    + ]' R. C/ H2 R
        These returned values are combined to produce the final result.
    + ]7 V/ i/ s- [3 |7 W4 G2 `# K5 e3 c5 o2 d# ^2 Y" J' @( n
    For factorial(5):) _3 I" G5 @) h# A: q' ^) o

    9 a  ~- ^: T3 G0 w! U7 B8 u' U. t5 L( ], X) s' W- K
    factorial(5) = 5 * factorial(4)3 b8 K3 P" x# Y' `, g
    factorial(4) = 4 * factorial(3)5 T2 k( w' t# h) Y
    factorial(3) = 3 * factorial(2)' _( G, n  }! G" w
    factorial(2) = 2 * factorial(1)9 c, t% l; o8 G
    factorial(1) = 1 * factorial(0)
    , x. {8 ~& g* M4 l! r4 o! z2 ]factorial(0) = 1  # Base case* H! ]" G9 K) I4 n) D$ E% z( x' p9 M

    8 v  ^/ O) G! E# F/ nThen, the results are combined:
    3 |0 S( t: o+ R$ G/ k  T8 Z& W" c1 ~( }2 O- U
    % ~8 @+ h& [' Z% ^" }2 X6 ~4 X
    factorial(1) = 1 * 1 = 19 u! Y0 u2 B# P! p
    factorial(2) = 2 * 1 = 2
    2 x* r& F0 a1 a0 D5 Cfactorial(3) = 3 * 2 = 6
    6 Z+ t' p7 c% M7 cfactorial(4) = 4 * 6 = 24. I2 A* d! V" s) I9 P6 f4 Z
    factorial(5) = 5 * 24 = 120, V7 a$ M0 O8 L2 n$ s/ j/ s3 B
    # u8 o% N2 L3 @% A
    Advantages of Recursion0 m; p" X9 R" i1 z& B
    9 W$ b* j/ R; V* i
        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).
    " B+ R$ A9 I/ D5 l6 [" M& c
    + t0 n0 B* d4 }( Y    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    5 t7 x8 R2 w: J7 L8 ?% q& t% ^2 x8 H. ^: u: z
    Disadvantages of Recursion
    2 f+ s. V1 W/ V6 l" ?  j, _  h- U2 @6 ?$ N  v
        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.2 l% v; H# v$ @8 r
    , |1 h) w, Q. Z; o! ^8 l- F! i
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    2 A! o9 e1 N5 A: f5 C; _
    " Q! B$ c# R8 S5 i$ A% ^When to Use Recursion
    ; a/ F/ b$ N& c$ H0 ^2 I
    1 A" j/ v, ^3 G( x4 @    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    9 j) {7 b6 N% Y
    2 y' H! [" J5 O3 ^: D: y    Problems with a clear base case and recursive case.
    + q6 [2 E" `8 f. h7 @
    & S% z5 h/ c. jExample: Fibonacci Sequence
    ) x! E1 q  E# [: g- U
    % b: f$ A: F) e# ~4 f/ YThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    3 E" F: D2 S6 S  h. _$ M; `4 J9 b; n4 S( M, R9 l1 K1 K! S* f
        Base case: fib(0) = 0, fib(1) = 1" U' n# c& |4 V) s. B2 p( ?

    ' s, i2 Y8 S1 T% M5 P$ O    Recursive case: fib(n) = fib(n-1) + fib(n-2)# p& w" e5 e* e' W6 Y* k, Q
    3 z+ D$ _) x! z$ a
    python
    8 ^. O  W5 G& n# f: p6 e6 M/ T
    7 q# `: ^3 @8 b- J, Q+ w4 z6 d' C9 {/ z- A
    def fibonacci(n):
    6 `% G# G; Y* E- U: C+ K    # Base cases
    * a4 n. Y0 n' q1 M; d0 P! p    if n == 0:& X8 a8 c. v) t0 @" ?7 ?
            return 0" A8 v3 S; k2 c# o5 a" z& o
        elif n == 1:5 B3 C2 z: Y! k
            return 17 [1 N/ @" X- E
        # Recursive case* k7 l3 ?9 J' Y! W' u3 B2 }
        else:
    0 j& N9 |; e. B; y8 r        return fibonacci(n - 1) + fibonacci(n - 2)
    ( b9 t# i/ \1 O. |0 y0 V; M% m+ H+ t3 [; Q/ I
    # Example usage
    " ^% b9 d7 A- S; v5 p+ I0 Zprint(fibonacci(6))  # Output: 8
    ! c. t- L9 d! m% W* j* Q
    5 p4 T! D! s3 Q) H- u' zTail Recursion
    5 g/ P5 t8 g8 c0 L% b, \+ x7 E5 B8 E8 D6 h& f0 D- k) a- n
    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).
      X1 C$ O* w+ O! f+ [
    6 p5 l4 \% w1 f+ q% a& pIn 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-11-25 08:18 , Processed in 0.031870 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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