设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 ! Q0 h: _, \, `" |# n0 [+ f

    1 q* h: {, d/ p- e解释的不错0 A" Z+ V( t1 U2 @/ V0 Y+ R+ N

    0 J$ l, G4 b& D8 ~9 m递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。% L4 f% I5 _* x

    0 O: t' l. L+ I% C$ T 关键要素' v: |+ ]9 ?: T8 V8 K% p% q
    1. **基线条件(Base Case)**
    ! k' i, K2 f& Z' a- j- z- ]   - 递归终止的条件,防止无限循环
    1 w( T$ l! l5 f" C+ C4 ?" X   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 11 ?% h  q6 O1 _7 o3 |/ b( o0 ?
    ) H1 x' t5 ^& Q1 W
    2. **递归条件(Recursive Case)**8 Q6 f% ]' E" |# A5 e# C
       - 将原问题分解为更小的子问题5 w! J" c4 n% L2 Z% q/ x5 t
       - 例如:n! = n × (n-1)!
      e1 [' m0 H: k8 K3 u; J( z+ n) q& z
    / R. ~8 z4 _/ G# @  B( g" B 经典示例:计算阶乘
    ! v' B9 K1 |! _# hpython. h/ F# I* c; b7 V2 a# K& Q
    def factorial(n):" ?- L4 g% m0 T4 s4 l9 M* k, X
        if n == 0:        # 基线条件& s: r0 j5 R/ g5 `7 p
            return 1& _% k- e( g" P
        else:             # 递归条件4 \2 y7 \; T( \) P( l/ u
            return n * factorial(n-1)
    & l8 i. [, b$ y' f2 W' j执行过程(以计算 3! 为例):
    , Y, a/ H1 s1 Yfactorial(3)
    8 O% T/ B  a/ c3 \3 i5 [: t3 * factorial(2)
    6 W0 @) q* i2 R# [* t! S1 d, B/ x3 * (2 * factorial(1))
    * k; ~( T. _- z% C# a) R% |8 }+ ~# l3 * (2 * (1 * factorial(0)))
    ) ]# S; L+ J' x8 e  h0 {( F3 P/ L( a3 * (2 * (1 * 1)) = 6$ |: G- s, G& y6 j

    % Q" i4 D. S( j0 ^1 k 递归思维要点
    . h! f. k' T8 t) T# d; l* a1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    + C* v3 X' g3 t2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    4 A$ l7 q( W$ ?5 _" t3. **递推过程**:不断向下分解问题(递)6 e2 g$ ~- U9 C' G1 |) N6 [" l3 W7 O
    4. **回溯过程**:组合子问题结果返回(归). c7 u, |5 }5 z1 ^8 J
    2 t* ^' v# u5 W  M% \) S$ `( x
    注意事项
    3 Z: @- W( L. P- P必须要有终止条件
    4 ]! X7 z* K! C4 W1 N3 e递归深度过大可能导致栈溢出(Python默认递归深度约1000层); Y$ i) g" s0 [: p: v: o
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    6 Z* I5 {& h) u尾递归优化可以提升效率(但Python不支持)
    4 W' _, L: [$ P' l( d+ C; x4 K0 N, [+ o) f; x- g+ ^) C
    递归 vs 迭代  B2 l( k% k1 j) M- @& l
    |          | 递归                          | 迭代               |
    4 s8 k4 \3 w* Q3 b/ q% k  N# d|----------|-----------------------------|------------------|
      v6 K: z# ^5 y8 m  a* x6 P- h| 实现方式    | 函数自调用                        | 循环结构            |
    $ W8 n( V" R6 [6 l# w| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |2 {: a% R( U; \6 Q; t
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |8 C3 s) k0 q) g2 v
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    ) \8 S% F5 G8 {4 S$ H+ _1 [$ E' f% w4 Z4 q: h4 T) P: n
    经典递归应用场景# s8 v; L+ h4 ?( k8 J
    1. 文件系统遍历(目录树结构)% s- P" H& L" |. [8 F
    2. 快速排序/归并排序算法
    2 ^/ f# j1 e  x$ v3. 汉诺塔问题
    # @3 t# Q. {! O- a4 A. `) l4. 二叉树遍历(前序/中序/后序)
    9 Y$ b1 D9 t; [& p5. 生成所有可能的组合(回溯算法)  z6 O  K; K2 e5 N- k/ v

    / m! C! A, W3 H0 o: P; x3 x5 j% z$ S: u试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    郁闷
    2 小时前
  • 签到天数: 3152 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,1 D7 {( t2 I' G4 L" q6 O" [$ m1 H
    我推理机的核心算法应该是二叉树遍历的变种。2 S# C8 v) y9 h. N+ u4 A
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    $ n: `7 g- l3 {Key Idea of Recursion# V  `2 C% l, J. Q  C( o
      A9 O6 R, k  G7 F; i* _
    A recursive function solves a problem by:
    6 S' _1 ?/ e1 P
    & F  c% u9 ?) |# T0 x- |$ u8 u    Breaking the problem into smaller instances of the same problem.  b+ Z! p) H& p# z

    + c9 ^. S9 W6 B' t; F( d    Solving the smallest instance directly (base case).
    % ?! ?' q8 k0 |% E! ?
      y* M7 h/ g6 e2 p% X5 R    Combining the results of smaller instances to solve the larger problem.
    : G) |! ]& Y0 N# E2 Z0 t4 G% c% l% C6 x1 \$ i$ d
    Components of a Recursive Function8 s) d( \" S8 ^1 u- x! C" Q( W

    ( a- ?3 H0 U6 f6 }    Base Case:
    * [! |4 i( H6 N6 L: b# a% w
    ! d, _) `0 n$ a0 d  X) g        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    + N/ Z8 g6 A- v2 R4 a/ m' w3 E/ ?8 V+ r( @
            It acts as the stopping condition to prevent infinite recursion.3 F5 R. b' n" n! B
    6 Q; R  q8 ?6 p  ]
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.# G7 B  f& L( k& u9 Q; g

    ) r& ^6 a/ N* v- X( o1 [8 ?- u    Recursive Case:
    ' S/ M$ ^0 r! n" U6 `- u
    5 o) W3 _: F& }( e( s        This is where the function calls itself with a smaller or simpler version of the problem.: G; |# A5 H) Q( G
    : W# p% N# u9 D/ A  K( s4 o9 U! g
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).) K* `1 P6 F3 x
    , J  ~5 s$ B/ i( H* n
    Example: Factorial Calculation* u4 L% ]- e+ G
    4 Z* N- V: c. f# |( C
    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:
    9 `" |( W* \. h+ X
    ! S: k1 X! X/ [0 q    Base case: 0! = 1
    8 \2 _+ A7 K) Q; }9 J( _, l6 B1 j7 G( r' @$ q+ n# o: N7 D
        Recursive case: n! = n * (n-1)!
    / G" n. _, i" `( y$ X9 a/ B8 ?" `" Z, I! A9 u
    Here’s how it looks in code (Python):8 r9 a3 ?4 z% V' b% z& ?; J
    python6 E% ~' ~9 l6 V# [; K
      L4 s. Y  O3 C! i. Y: V! [$ i
    2 u8 }0 m# |, [5 _9 X
    def factorial(n):
    1 ^7 @8 T, k! D, \! @, {/ z( ?    # Base case
    * _4 R/ v; T7 F# Q$ O$ [+ {    if n == 0:
    - s# g9 \9 O; U* h        return 1
    : C: v* ~* f) j* [    # Recursive case
    , e  H1 {6 f. f, J0 ]0 s; `* H    else:
    0 g! T, Y) Z$ b; y- l) k        return n * factorial(n - 1), {! z5 c: R8 m8 Q+ n- k- x
    ) }( x( p& Y4 a, R! Y  k
    # Example usage) W9 j9 [! b0 z5 v' m  `
    print(factorial(5))  # Output: 120, ^2 H' H0 [6 e; h( Y( l0 A

    - \2 ]9 s4 `6 _, w6 N: lHow Recursion Works9 q% s7 @1 G& S' N

    % o. t( L. x, k7 X% n    The function keeps calling itself with smaller inputs until it reaches the base case.# @) J( l5 R, Q2 \! i) _8 s
    & F% \1 h: H+ G
        Once the base case is reached, the function starts returning values back up the call stack.
      @9 I- J( ]8 O0 x" X, {& C& c/ ~- b9 l, I
        These returned values are combined to produce the final result.+ ~$ d- M  `# `6 l6 e6 h

    0 n$ p' ?( e! W. b* a8 u7 HFor factorial(5):! g% e; U. Z9 X- Q/ V

    0 h8 b: {7 m! a1 u) Z& Y
    ! I  {) V6 @, [, H* B) ]8 I5 Afactorial(5) = 5 * factorial(4)+ J5 x: [+ {7 C. R. ^
    factorial(4) = 4 * factorial(3)
    " d% v) i. L+ x& ffactorial(3) = 3 * factorial(2)8 i. v: P: ~2 c/ b- Y6 I
    factorial(2) = 2 * factorial(1)+ U9 c" ]) V. \' C# |1 H
    factorial(1) = 1 * factorial(0)3 M4 _6 I; E. t1 q+ m* Z$ q; W
    factorial(0) = 1  # Base case( M9 [$ K1 C( f2 f. ?4 M2 d
    & W% q( J3 V, J
    Then, the results are combined:
    , a6 v# }0 D8 R! T/ {, O8 Y9 u5 r. P4 c

    6 x8 W: i; m5 V+ |/ E1 Xfactorial(1) = 1 * 1 = 1
    2 ?) a, q3 B5 ofactorial(2) = 2 * 1 = 2
    9 i5 ?. x1 g/ Sfactorial(3) = 3 * 2 = 6
    # h/ d! ^0 k3 Y3 ]' k" [factorial(4) = 4 * 6 = 24
    ' Q! o, o# n- V) ^+ w% f. kfactorial(5) = 5 * 24 = 120: n$ Z) p- W& A. C  z9 M' H
    6 g7 _6 Y7 u9 l
    Advantages of Recursion
    9 r8 D7 x7 N/ a; ^4 O" T: x5 }. j; B& F% k; u4 |
        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).8 i: n7 F5 t& z/ A: |# ^

    " _$ P. g. Y* L. R* L    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    7 J9 @8 c1 j# A( N0 J+ H3 h2 p) I$ P4 }* X' C& i
    Disadvantages of Recursion
    4 a& f/ f, q2 Z- y: {5 g/ m4 D3 o0 x+ k& ^# Y. e
        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.
    ' M$ Y  Z) l* T* J% g1 x4 \+ x6 S$ O" a& E0 S8 p* z( G3 b
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    7 M  E7 @$ Z! s5 s7 D6 y& @  W% w" w; T- z
    When to Use Recursion0 x$ ~/ w# K9 \! I, f4 a2 V" W
    / ~: s! v4 s4 |
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    , _6 B" k* c( D( P$ `5 t; w1 h/ `, j) E# x5 V# B$ k3 h' U
        Problems with a clear base case and recursive case.
    ) P: u4 g' q6 P/ Z$ v. A2 ]6 c9 u
    5 K$ p/ w% u( J( wExample: Fibonacci Sequence8 t. [* Y" j; g6 w; b( u0 F

    1 H2 B; i3 R$ x( FThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    , e* g6 j/ p; M' F- O: B9 m* |$ D: u/ f5 H  h9 J6 p* T
        Base case: fib(0) = 0, fib(1) = 1
    : @) `3 b4 \" Y6 Y6 q; q8 j% I  n8 M  ~% F3 b
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    " M/ d( u0 ]! [* E8 H! U" O1 P& }, V2 F+ S4 v9 J& j
    python
    4 {, f) V: u8 v/ ~* `+ @3 H) ~5 }0 f, s2 Z

    # _2 ]5 F% ]1 c% \def fibonacci(n):
    , ^% K& g. o! N- K' T9 t: s    # Base cases
    " a4 o. r) {5 X. [0 M    if n == 0:
    2 d, `( K: c6 j: i- q0 e9 ^9 {1 g! y        return 0( H, I+ D5 T& P
        elif n == 1:, u# U" T+ B" y9 H
            return 1
    . x  ~$ M: c5 V% f, h6 f    # Recursive case/ A$ q2 R( V6 r: o3 K5 \
        else:
    : O# C; q" E# B% @5 u! ^        return fibonacci(n - 1) + fibonacci(n - 2)
    $ X, h  U! `- {8 J4 I
    8 g2 {: B% i2 I, z7 F2 D+ Q# Example usage
    , \* Z# |# l. mprint(fibonacci(6))  # Output: 8
    0 ?0 G/ R" K5 I' R
    " R+ i. w( o1 ^$ @6 O) Z9 HTail Recursion. n& |. U4 T) T

    ; J/ {8 m. V! f' PTail 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).
    . I, Y% Q9 Q# |6 H  N* S2 T$ q0 q$ B% n2 W3 G/ E# u3 R! y
    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-23 10:19 , Processed in 0.065786 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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