设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    5 s* z; e8 Y" U5 q4 o2 [  a# M
    " S3 k8 @$ T9 }" G& \! C& b* w解释的不错
    ; a0 d7 o' b& l* J/ a" c1 F  N4 ?" T/ @- K6 m7 e, G$ }9 Q
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。0 m7 l, u2 g- S' W4 T8 V4 l
    / x! T# ^! J/ q% l* d( W
    关键要素
    + N( L/ r4 q) ]; p3 l1. **基线条件(Base Case)**& I; X3 x# \4 w: E. a3 a' z0 C: u/ O
       - 递归终止的条件,防止无限循环
    6 _- f: k9 l% f" y8 i   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    & F, u2 s  _# M/ R0 V8 L4 h5 s, N% U! j  E1 L$ Y
    2. **递归条件(Recursive Case)**3 V8 Z3 n+ G7 v, S1 e9 o
       - 将原问题分解为更小的子问题
    , z- A4 V' a3 Q* m3 o' F' O   - 例如:n! = n × (n-1)!, G" _3 p" f9 d0 y

    $ C8 q! F+ |; J% q6 T 经典示例:计算阶乘
    ' v+ n% x  `! l' W+ p4 h+ {% mpython
    + l; X1 x  E. z3 [7 e) O6 ]def factorial(n):4 E8 Q* @7 O7 e0 v# s
        if n == 0:        # 基线条件7 q0 X7 x; H, `) W2 n( C+ ^
            return 1$ `* i7 F, o% |: Y
        else:             # 递归条件
    4 Z  i4 R- |; U+ a        return n * factorial(n-1), [$ a" z- s5 o6 i$ E3 ]$ n0 `4 c3 A
    执行过程(以计算 3! 为例):
    0 i! o# n0 a- z3 |7 s/ xfactorial(3)
    0 m! K; d. [) B8 y0 D- ~3 * factorial(2)
    " ?) X( U4 W' u. ?3 * (2 * factorial(1))
    ( ^5 r  X4 U* S6 H) ~3 * (2 * (1 * factorial(0)))  ?: o: h* l" V
    3 * (2 * (1 * 1)) = 6
    " Z7 y. @& O3 B0 v- k+ W
    4 Z. Y8 Y( q; @( d6 R' | 递归思维要点
    ! c0 `4 d: }; }/ k1. **信任递归**:假设子问题已经解决,专注当前层逻辑% m6 ]2 L& B1 a( m' N
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    0 B4 v. n- [% [8 g4 O' g3. **递推过程**:不断向下分解问题(递)
    2 @$ H+ O- H0 \" m8 k* ^8 M4. **回溯过程**:组合子问题结果返回(归)! g1 U  S# V- k* ]: t

    ) m+ n6 c2 V% y1 H 注意事项5 }0 \- f# d3 x/ F3 T" R
    必须要有终止条件3 y) Y# o; E! a6 v4 R1 {
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层), h* g0 ?0 h( W, p, Z3 K
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    * G! \+ {$ I0 n8 F尾递归优化可以提升效率(但Python不支持)# k  T9 C  G/ I; b

    ( q* J0 V8 a3 n; z4 I 递归 vs 迭代
    1 N( R1 Z2 [  H0 F$ U|          | 递归                          | 迭代               |) B+ i6 L' Y- k% F6 {4 l% T) t
    |----------|-----------------------------|------------------|; {4 ]3 G3 R% a0 I- P
    | 实现方式    | 函数自调用                        | 循环结构            |: d6 I7 \" n; C9 v
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |+ J+ h5 n: B! D+ S! m+ n
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ; z6 |! w& n$ m, A| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |1 q1 a* i- ^: E/ |; c$ p
    7 X3 y) @  q! H; {; b
    经典递归应用场景5 z9 W6 l1 ~$ s+ R8 |& V. V% }2 f
    1. 文件系统遍历(目录树结构)
      X+ w) f1 f0 u/ Y+ `0 l5 n7 A2. 快速排序/归并排序算法
    0 w# A$ W# `% G- y3. 汉诺塔问题/ l1 f2 ^* ~! @$ F! e8 p
    4. 二叉树遍历(前序/中序/后序)
    ) S- f+ ]8 t) V, J+ `5. 生成所有可能的组合(回溯算法)7 S6 u, A& a+ n3 q

    & r1 H) v4 ~( E4 d  ^- Z5 o试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    昨天 07:29
  • 签到天数: 3183 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    % U$ A  T# o7 V7 r7 c我推理机的核心算法应该是二叉树遍历的变种。' g6 @( V3 P0 }# H, k; x
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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 y4 c) }8 M, k( a3 m/ I
    Key Idea of Recursion/ Q$ |2 H5 ^+ \
    & ^: c) R5 Q# h( S8 m
    A recursive function solves a problem by:/ e6 {0 B2 N2 U$ A+ Y
    + z" ~& w7 x$ `& _# [" W
        Breaking the problem into smaller instances of the same problem.
    : a( ^. v8 \  x1 G4 o, M: p; B4 O, [# M/ ]) j* [
        Solving the smallest instance directly (base case).- ~+ |2 R9 G4 H/ t" m0 p$ }
    : `; T* _  j, S4 T
        Combining the results of smaller instances to solve the larger problem.
    . h4 _( N' M3 k8 ?0 E3 E  E. `; q; R0 h5 V" q: G* \( W% @# U
    Components of a Recursive Function
    : Z, t$ ]5 |+ D2 o+ g
    9 y# @7 G) b& W* l    Base Case:
    / ?% A5 S. {5 R1 d: c% d/ a8 }' Q3 V' Q- z' D& P0 F8 I
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    ' S  n3 G: f+ d, y2 C5 r8 ~+ T, M+ h3 M. W9 e. P% Z
            It acts as the stopping condition to prevent infinite recursion.* L3 o# B- i2 `
    9 t/ U1 o/ K: }
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.& {% K/ H: z- G8 m
    + O3 l+ D- ]: U: x: s
        Recursive Case:
    ) a5 W5 E, O; `4 A: ?8 @
    2 d; u& b, i6 c& I$ ]+ k/ ]6 ?  d        This is where the function calls itself with a smaller or simpler version of the problem.
    7 h+ p9 W! z& U3 a/ F) I$ k
    5 o) f9 U! o0 d# c$ @1 ~6 k        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).+ G" r5 z! ]: U  u, G& W4 O. Q
    & l* P' y  A7 }( S! K9 C8 [
    Example: Factorial Calculation$ M- y! X  r& q

    " h- U4 P- `9 V9 j7 q; [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:
    # I7 z. i4 K: l4 I9 G5 G
    " n8 r5 H3 z' b: i    Base case: 0! = 1
    5 L4 a! n  \. M9 i! o
      n, ]' e* V( T( L0 ?    Recursive case: n! = n * (n-1)!
    # z- E  r. ]$ x% a5 v
    9 s8 h% Q) s, B8 K. JHere’s how it looks in code (Python):/ T# g% h# r7 d, W; M
    python
    ( V+ P) [7 o8 p) h3 Y- J$ {7 f
    + J/ F9 ]) K9 D- f  R9 r
    , y- o/ A) ^/ z/ f- |: u1 Q2 }2 gdef factorial(n):
    + o+ z: ]8 D3 k7 G+ @3 J# b, X    # Base case0 c. ?  a; ~- T, W# q3 b
        if n == 0:
    - W4 s- U; ^2 @; o9 G. x        return 1
    ) r% L$ Z) B/ R( i; ]& Y3 |1 G    # Recursive case& a, r+ ]' z# ~
        else:4 z$ C/ j( R9 ^* y: s9 J  f* Z: }7 Q# D
            return n * factorial(n - 1)
    ' ?8 }, v; ?6 }/ N+ l9 w2 n& _2 r# p- g9 y$ P' Q: g' v! M" w
    # Example usage( f/ a. A( Q7 h+ [
    print(factorial(5))  # Output: 120' ?/ y( y; l; Q1 e6 I* h

    % t1 ~5 k5 Q. i1 NHow Recursion Works/ B  E5 L8 ~" ^! w. G/ j* J: l" I

    8 Q  P& K  g' N% b0 R# f& |    The function keeps calling itself with smaller inputs until it reaches the base case.
    8 D" s  {' G  [$ p* O" ?9 Y+ u. O, n" m8 N2 x9 f6 j1 B
        Once the base case is reached, the function starts returning values back up the call stack.8 D! A5 s; _! U

    ' T# ~$ M1 S/ y- `! z    These returned values are combined to produce the final result.
    ; T! O; j) K( Y' W* z) o& H/ G, s7 ]2 {0 X% u
    For factorial(5):
    % ?2 g8 Z! B7 y  B% U
    & s+ X0 }! w% l# d( l7 X, `+ N. C8 M; U. H9 g
    factorial(5) = 5 * factorial(4)
    % ?& k1 ~. z. E) |- ifactorial(4) = 4 * factorial(3)
    + ]+ X) x% B" h7 i# [  m% h" lfactorial(3) = 3 * factorial(2); j( d" ?! K" {) L5 L
    factorial(2) = 2 * factorial(1)
      D9 r: ~# m/ ]0 S5 R2 o8 pfactorial(1) = 1 * factorial(0)
    9 j$ ?) u6 K/ @factorial(0) = 1  # Base case
    , {- s. S# V: B" a2 I, O6 D! p
    % O, A$ x' Q( y1 B/ t0 m: ZThen, the results are combined:
    $ B6 }' M1 z1 y$ q+ }* B; ?% d3 o9 G, `) b2 Z6 d

    2 O4 F# f* C! m3 H' x6 Ofactorial(1) = 1 * 1 = 1  a1 P3 a: y' M1 U
    factorial(2) = 2 * 1 = 2
    5 f4 _4 t- T% D. l' Z- _( p9 Bfactorial(3) = 3 * 2 = 6. I* W/ [0 W# I: F  `6 v9 h3 h
    factorial(4) = 4 * 6 = 24: ]6 {% I( U# v/ K
    factorial(5) = 5 * 24 = 120
    2 p" p, J7 h2 i4 m/ C9 x/ w# N3 o; ?% E, C) A
    Advantages of Recursion& M9 K" t4 V5 F' D

    ' N! b7 F+ v! J    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).
    3 ^. `" ~+ X0 E/ t" t" @6 {
    1 o- V- N* C: `5 k( U) ]8 g    Readability: Recursive code can be more readable and concise compared to iterative solutions.- o& i5 S3 }" M! Y9 T
    9 g( W6 B3 V8 I  q
    Disadvantages of Recursion/ y2 d( C  g2 p& [) f

    & p) I" E, _) L: [! H( Q* Q% s    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." B+ T! W8 v% t

    2 q6 i1 W3 K' O' ^$ s3 K! X    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    4 |5 K' i6 _* s6 ]8 r- k9 t, _& F
    When to Use Recursion
    - N$ q  Q' N. e; |) I
    , [4 {) I9 f& h7 m# |* c+ H    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).+ \+ o4 u- g9 C: L$ x- p
    9 i4 Q! Q! Q- q3 f6 c8 L3 D2 F0 S
        Problems with a clear base case and recursive case.
    ! Z6 v! P8 y* v0 v
    5 V- [$ M3 d" ~  x$ ]  {% T* aExample: Fibonacci Sequence
    8 D$ c: g( g- G; C0 S+ O+ r7 M
    * R: J- n( o6 |' \3 MThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:3 x. I2 O% C- W
    0 [6 ~/ u$ x9 [0 n, ]
        Base case: fib(0) = 0, fib(1) = 1
    " G3 d+ N1 F4 ?& j8 i( \3 a
    " z. f: U' B  `% }' g& E    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    / {5 f1 A# |- |% S$ E# }; h
    9 _/ P3 I1 K  X: e$ }python
    ) a, n  h+ x. X$ A' ]" F4 z: X% d. g. L
    # i+ Y7 P: Y* e" t- w9 j( m$ I" n; t5 ]/ C
    def fibonacci(n):
    % X" t9 T/ S% w. e    # Base cases3 R! i3 O6 S5 h% s) S  H; q
        if n == 0:
    + I. l% o# X, ]7 G3 Z3 [        return 0' Z# J/ k, _5 A
        elif n == 1:
    * `. B/ X' X/ X# p        return 1
    % u) K. c5 @+ ~" R) t    # Recursive case$ W+ B& _% a8 V
        else:# ~; m9 l7 @3 d% O. c
            return fibonacci(n - 1) + fibonacci(n - 2)- s( N, t1 i0 W2 f9 r3 b

    & `9 W" M# P& A; v4 S; [1 V6 L# Example usage7 g0 ?, J. S! n7 A2 N
    print(fibonacci(6))  # Output: 8
    ; M8 j$ R7 c0 p8 G- D2 g5 t  @5 S# q: L
    Tail Recursion1 k# [4 U7 ~  E

    7 u) z- L& s) z- d/ sTail 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 e+ a* Z2 u) X8 ~& Q0 @( n2 U4 o& J  T4 l+ T
    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-25 05:13 , Processed in 0.062213 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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