设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ' M) ?) j7 z4 M% ?+ c
    - d. s! j$ Q' n9 h+ y解释的不错
    + n3 P. ]/ ?" z# A6 q: Q  s
    ' v2 r% i# }) I, A5 V7 y6 D递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。; p+ P+ z% `  D, O! R

    * J* K3 w( V4 [% A& E% } 关键要素9 N+ O( Q0 J' r9 D" E
    1. **基线条件(Base Case)**
      A, m( W# x- [   - 递归终止的条件,防止无限循环
    : u% o7 l) h, H- w* a, a) T   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    ! V3 [3 m0 x0 _' M# o
    & `( Z+ Y. s  H- p2. **递归条件(Recursive Case)*** Y# \0 n5 s) ~% q- z( f6 U
       - 将原问题分解为更小的子问题
    5 q8 j3 N4 [2 F   - 例如:n! = n × (n-1)!. L4 @4 _7 T" Y
    + g  j4 h9 {' M' ?' O3 f- u6 d- J
    经典示例:计算阶乘
    ( H4 J* }4 D+ P  N9 k$ C2 upython
    , i' l/ E( {- Y- J2 i* ydef factorial(n):
    9 l% ~2 s  I( [1 t4 |" D7 [+ e7 A    if n == 0:        # 基线条件
    . Q8 z" Y! g! R+ R. L3 d9 W' e# ~( u        return 17 `/ @9 T# k) a" R4 s; B* Q8 G
        else:             # 递归条件
    1 p) e+ i+ T( \: K- o1 }3 u        return n * factorial(n-1)' ]2 Y4 {( {; d% G3 @
    执行过程(以计算 3! 为例):* n- y+ O/ B: q1 k" w* \% r0 S
    factorial(3)
    ( A& @; w' y5 s' t3 * factorial(2); B$ d$ n& e1 `
    3 * (2 * factorial(1))
    # l$ Y5 x$ P8 ?: W: p6 y$ R; m3 * (2 * (1 * factorial(0)))9 }( O* X7 \/ I, d9 u& e
    3 * (2 * (1 * 1)) = 6
    ! U0 v$ e% o+ E) Q6 O, G
    * w' c" _# P! [; w1 Z( o 递归思维要点. f' V: f# ^- n) j
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑* q) o+ }+ _% B1 ~! D2 N- F+ S
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)& W: F1 R( k" t. p9 B# J
    3. **递推过程**:不断向下分解问题(递)  W+ S9 E# G1 T1 G
    4. **回溯过程**:组合子问题结果返回(归)
    3 ^* @- b1 O9 Z1 w1 r: }8 l9 N9 q& @4 B  u4 L
    注意事项
    5 }9 i* L9 E+ S9 l5 G必须要有终止条件
    8 a7 D  c1 @0 {递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    $ F& z1 v# w8 Y8 {% S+ L某些问题用递归更直观(如树遍历),但效率可能不如迭代, }1 S! w# o. Y2 w. ^
    尾递归优化可以提升效率(但Python不支持)1 s: R6 F  z" @; x* d( q0 \
    9 p; b5 [9 Z! B
    递归 vs 迭代
    & r) u. [# l! C8 _+ z|          | 递归                          | 迭代               |) r6 [( C( Z0 f
    |----------|-----------------------------|------------------|8 f5 L" ^/ c9 Q$ X+ F
    | 实现方式    | 函数自调用                        | 循环结构            |
    * r/ d- t+ @! d( U) H9 u2 g, W| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ( f3 [3 X' Z+ A| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    3 ^8 y3 e; I4 v2 H| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |( I; p2 G+ t8 W, T* s7 U

    ! p) {' K1 g! p: p 经典递归应用场景  b8 ~+ C$ U% Z0 R7 a& s
    1. 文件系统遍历(目录树结构)
    $ |8 p( K2 D& b8 J2. 快速排序/归并排序算法; l5 {1 h3 k1 S$ r
    3. 汉诺塔问题! }( p/ a& I- v
    4. 二叉树遍历(前序/中序/后序)5 R& u1 A: h! Q6 Y( |
    5. 生成所有可能的组合(回溯算法)5 l# [1 m; M, n' J" X( g) N! `

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

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    昨天 08:35
  • 签到天数: 3194 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,# ^. K  |( S  I( H( j
    我推理机的核心算法应该是二叉树遍历的变种。0 e6 b$ l7 s, R5 ~% ?" q+ x8 {
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:0 }4 G5 u; Y+ }
    Key Idea of Recursion
    2 w7 ^+ x! z6 r
      {5 I" k  z7 I' \) p- ]' \A recursive function solves a problem by:7 v& g% ?+ Y  f5 [9 n5 m

    # N- p# X: F. I' j    Breaking the problem into smaller instances of the same problem.  m0 [. x! @4 _
    2 J9 L( Y; n1 n* U6 i$ q7 A% A
        Solving the smallest instance directly (base case).
    / A( Z- g/ {, Z# p! E+ N4 G
    ' t0 V: R8 g) R/ v& r' Q  M    Combining the results of smaller instances to solve the larger problem.
    $ d3 t. |7 v: ]$ X' v5 v: j5 F& u! z
    Components of a Recursive Function  b' y' t8 K9 E" b

    + d+ }: e" j! e  J/ w( ^1 y    Base Case:
    3 u& _: K# V1 Y+ y* v, z
    $ N2 Q$ j  g8 t# A( ?+ s+ T        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    ; G+ O: P' Z4 d$ d3 ?9 U
    # l) f* f. A: G& h        It acts as the stopping condition to prevent infinite recursion.
    : r' W# P6 O& `& u
    ; Q, [, z# R( i- w        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    * F, i- U* H5 k5 |0 k8 r: l7 {6 y6 ^+ w/ d" S* l# @9 Q6 ?% l6 b
        Recursive Case:
    ! }. n8 x" Z+ K
    $ I8 v0 q( V% e& d' E1 k" V) o" P* ~        This is where the function calls itself with a smaller or simpler version of the problem.% K6 h! k: H* }( F* g* B
    0 W- J: w5 D/ x6 d
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).2 [) ?1 J) e6 s( X  z" ]' Z

    - T" Z8 N5 W; w5 w) WExample: Factorial Calculation
    9 r# Z, N0 q; i1 h) I! Z; \% o  L- [7 b/ m+ 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:
    2 e$ y8 a2 L9 d# @# T2 k
    - G+ P' ?" y" l9 B& A3 Z9 t    Base case: 0! = 1
      r( ^; `+ H. K9 W' Q5 ]2 }  G* N+ A: P9 B/ O1 ^* ~/ T% E
        Recursive case: n! = n * (n-1)!) E$ A" C# K% q& v% G
    9 m% ~9 E  w3 `
    Here’s how it looks in code (Python):" O6 }! o# h- W7 \
    python
    8 p9 ~/ o$ y; I3 f* u) V0 E
    3 H- f& q6 Y: E- y/ l$ r' m
    6 n4 u' A) d* T( H( R( f( H4 R$ Qdef factorial(n):
    & o, `* c* X9 m$ A    # Base case% @+ t, Z; y8 m: g" Q7 o
        if n == 0:
    * f1 D0 ^4 Q$ o  ]& D- F        return 1
    4 L3 o- }: v9 I    # Recursive case5 p$ k6 x7 |$ O5 [
        else:
    1 b, F' [. D. t        return n * factorial(n - 1)1 f1 n; ]1 D! L! p9 a( N

      z- j3 i+ k' H. f) Z) |, g# Example usage
    # V5 P. r4 u" n2 C& m1 B* r7 r8 P  Bprint(factorial(5))  # Output: 1200 m+ z& L2 l* r

    # V% l% M8 q) n2 E5 m5 HHow Recursion Works
    ' t% K3 x: _) |* s
    4 Q8 j& F- T- r$ r    The function keeps calling itself with smaller inputs until it reaches the base case.
    5 @; Q3 [% ]3 n" b: D, E. p  c0 y5 }$ u$ v, G( Z
        Once the base case is reached, the function starts returning values back up the call stack.
    7 ~# z! @- w! R8 y) D0 M5 O. f' T  M. n1 {/ Q2 @& c
        These returned values are combined to produce the final result.
    5 @# l( {/ ~- d! m2 T7 {( q* C' T8 r
    5 K# q6 j* t3 ?/ X' D& {0 aFor factorial(5):0 P0 }$ _# D! w$ H. g8 ^

    * g( Z1 o. f+ p: m- n- G0 T1 H( Q% Y" i) T
    factorial(5) = 5 * factorial(4)( n' ^' a" T' c; t- @# y
    factorial(4) = 4 * factorial(3)
    % K6 S  c4 F- W; g( r% Gfactorial(3) = 3 * factorial(2)& j  t" E5 d) T
    factorial(2) = 2 * factorial(1)
    ) P/ }# g- I$ L1 p; u9 t0 |2 V6 Jfactorial(1) = 1 * factorial(0)! T6 w% ?- \, H. o6 K- i. P7 s1 ]
    factorial(0) = 1  # Base case* S7 J# T7 j9 [! p3 ]/ _# x' R0 a

    ) o' G# c5 P8 `3 R! f, |Then, the results are combined:% i/ @2 i: g- _1 T

    7 z% C6 N3 {! w3 X
    : l. _7 V! S8 x0 pfactorial(1) = 1 * 1 = 1
    , O& m1 P9 z9 \: Z2 F$ n" {factorial(2) = 2 * 1 = 2
    ! s: ^5 H9 h9 T. I$ V" J% Cfactorial(3) = 3 * 2 = 6+ G# |1 g4 O) o! G
    factorial(4) = 4 * 6 = 24) Y7 e$ ]2 n) t% e4 y
    factorial(5) = 5 * 24 = 120
    ! d2 b1 W7 B3 f/ {8 \9 l7 I/ o3 n+ p! B# p: v# i* d, P' f: {! R
    Advantages of Recursion) }% r" r8 P% t  g& c5 X
    ( m  J( E3 u3 q
        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).
    " w. [4 l! N8 x, x6 \+ n! t& q6 E: f1 {6 s; p$ f
        Readability: Recursive code can be more readable and concise compared to iterative solutions.% C7 I' D) `; P: I
    % B: \2 x* \& X* e+ `- v
    Disadvantages of Recursion
      {. F* z8 f, k% u( `
    , h* [0 d- {  M( c: c! 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.
    0 |. ]+ S1 v$ U& ^+ q+ W2 K( {' @" y3 @- C/ m  J
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    1 V' t: T' }* B# X8 w2 ^
    8 a7 A4 J; }& ~1 a! h9 XWhen to Use Recursion
    7 ~; c0 w+ n8 V9 |7 a% t8 S
    ( c+ n  X1 A& a7 t9 k0 Z    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).5 r" g. y: q' P' u

    3 y  i& {0 k; \" ]    Problems with a clear base case and recursive case." n: c4 h9 c& l+ h
    5 I% _4 t* \, e( _& A0 t- I1 G
    Example: Fibonacci Sequence5 @' M0 y7 Q# E! T) I

      e+ v, A+ h3 ]* IThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    ! c8 P  V; f6 h6 i/ B% d0 I) ?. ?2 ]4 p: N: D) |
        Base case: fib(0) = 0, fib(1) = 1
    7 Y  f$ F) J1 x; V$ |% M8 _* k0 {4 }4 c9 Z9 X/ ~+ i. G
        Recursive case: fib(n) = fib(n-1) + fib(n-2). V+ l3 G2 H; W5 b3 A# R, O, R* C
    ( h6 W8 s4 ]) I
    python2 T! A3 X: w5 M$ a& K5 m

    & K/ a- P/ p# s* ?0 W5 ~$ U8 m/ u6 F& Y8 d
    def fibonacci(n):/ J9 w- i- M! o. a1 m, A
        # Base cases* }9 S7 A1 M9 }% S9 |5 J; j) p
        if n == 0:
    * c. a. i' O$ w" Y; e- y4 ?        return 0
    * K) V, V; J: D/ j  X    elif n == 1:) g+ N9 J, Y: b  _. \1 [; P
            return 1' i3 A* X, m5 H  c' I, R5 |# G
        # Recursive case3 S# f, B% W; p$ C; h$ s
        else:
    . V! g* L% W5 B2 O" i        return fibonacci(n - 1) + fibonacci(n - 2), H0 w/ E& q: [5 G4 g( x

    9 f* b( W) t0 t% D, B# Example usage- B9 P3 F5 i1 V6 f9 Q. Q) o' D
    print(fibonacci(6))  # Output: 8
    4 l" ]+ J+ M' l  T. J
    & r0 y) f% p3 C! _; M9 V1 aTail Recursion$ i  a1 E9 b; @8 v: `' }

    ! h1 M1 {0 m& s3 c) F" @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).
    ! N7 P# @; v7 u9 \) a0 ?( d9 n6 Q# ]3 ]- 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-3-8 08:16 , Processed in 0.064845 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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