设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ; I# M+ q6 U! ~% N' n
    % l1 W# O! F3 X8 c$ v1 s解释的不错
      N1 M0 R- s0 g6 p$ g# y1 w6 p0 O7 l8 k  T; L% i
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    & |/ c* t+ e, S: [" X& h" O, @6 [2 K, z0 J; A
    关键要素7 f) q- `! n/ Q. B/ }0 {
    1. **基线条件(Base Case)**
    1 |* }+ A# L% {" ]   - 递归终止的条件,防止无限循环' \. y0 @& {" i) d5 V
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1$ @+ h) b: L6 w  F; ]) f

    ' v# U! c7 b* \$ ?! G6 H% o2. **递归条件(Recursive Case)**
    3 J# d# D8 j* G9 `; Y9 V   - 将原问题分解为更小的子问题
    % y3 Y# ]8 q3 w8 j   - 例如:n! = n × (n-1)!
    ( i, M( g  q0 Q
    2 H1 `7 r) D: Q 经典示例:计算阶乘
    . I, U2 ]( H# E$ n6 P2 X8 fpython
    3 V2 F+ u; `9 e0 w' ^5 Ndef factorial(n):4 Z! u3 i: D# d& E
        if n == 0:        # 基线条件
    1 `4 L" R# O8 H6 w0 l1 t        return 1( M1 d% ]" B5 Q; j8 w# h
        else:             # 递归条件
    + z( {) s$ H* B6 I2 ?1 `5 J; r        return n * factorial(n-1)5 x% Z+ R0 v, \' f5 }$ M. {9 z0 u* B
    执行过程(以计算 3! 为例):/ ]" P8 {9 I! b! i6 _0 J5 H
    factorial(3)
    * `# I- |) _1 m  t* j3 * factorial(2)
    3 s# S. P. \% C- j1 i3 * (2 * factorial(1))
    6 j0 @4 N; J/ p  `' A4 a3 * (2 * (1 * factorial(0)))# N/ o0 c1 I5 ^; b4 R: B
    3 * (2 * (1 * 1)) = 6
    ) u: Q0 O7 w' f! \$ X: @
    9 z) r* X1 T) U3 M 递归思维要点, r  ?7 t6 X+ ?8 z3 r6 P" ?" _8 \$ }
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑' N- ?2 T0 Z$ T2 |0 {
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)- S! K* B: t  P' b5 O% u
    3. **递推过程**:不断向下分解问题(递)
    6 V/ W7 j0 |3 x3 L4 U$ |4. **回溯过程**:组合子问题结果返回(归)3 \: u7 s2 c5 ]" Q; F- ]

    $ Y: w3 X% x8 m: A8 m2 c0 S 注意事项. G$ R9 L! Q% o. S) n, v
    必须要有终止条件$ u) F2 t8 j8 m
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)& @3 s- _1 F7 Y: C
    某些问题用递归更直观(如树遍历),但效率可能不如迭代8 s7 H$ Q% W) b& L" f+ j' s0 P. C- ~
    尾递归优化可以提升效率(但Python不支持)& u7 Z/ w& v  l3 J7 P' w  e( O
    1 G& V: D& v; @5 H
    递归 vs 迭代
    9 g- H6 b9 j5 U|          | 递归                          | 迭代               |, W$ m* `! p4 R$ N9 R7 F
    |----------|-----------------------------|------------------|
    ' A; |* W: R8 f! U$ q| 实现方式    | 函数自调用                        | 循环结构            |( g* L6 K& J* E3 F
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    3 S* E$ F: T5 R0 A| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    9 M6 I; z* ~4 D| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    3 C* z. u4 \! F; w0 K9 {5 J9 E) g5 U; u' D' a3 N
    经典递归应用场景- d- l! |& }0 W* K7 j
    1. 文件系统遍历(目录树结构), n8 ?+ D& o4 Z$ N1 ~! L  X7 V7 r
    2. 快速排序/归并排序算法( R6 W* Z: C! Y5 z  G& T
    3. 汉诺塔问题3 j9 n: x: L6 l  o' b7 p; G
    4. 二叉树遍历(前序/中序/后序)
    8 C# F: ~* }) R6 G: L5. 生成所有可能的组合(回溯算法)
    ' O9 |7 J: m, `8 z% F" y9 P/ u- U6 y' }
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    ! @$ t) Q- G, S我推理机的核心算法应该是二叉树遍历的变种。
    & z3 Q" K' ^% 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:" s& ~" i7 K' j
    Key Idea of Recursion% }% e( n! m0 N, _) C: ?. }

    0 ?! M+ s# e. d( c; ZA recursive function solves a problem by:8 \" B. ~9 a6 E4 h3 o1 h  A
      S: D& L5 l* T3 R8 U( j
        Breaking the problem into smaller instances of the same problem.
    * ^  s1 v. t! x. m5 K3 v, I6 e% W! d5 C" M. T. Z) ~: N7 w" A- X% f, E- j; U; N
        Solving the smallest instance directly (base case).' C: F7 q* |6 [! g

    # b, `: o- i* l2 o" L    Combining the results of smaller instances to solve the larger problem.3 }6 x2 f) ^. `

    6 i* f7 S3 c3 q9 HComponents of a Recursive Function
    " R( Q  n, w8 \9 A, e
    % _- t& d7 g1 @/ E) g3 f    Base Case:, g% T9 u- L5 u/ o
    1 f) `0 m3 q6 Q0 \% `. L- M& g) y
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion./ N/ l5 U4 G5 `2 b7 \( F' |" N
    : `# `# Y  ^) C$ Q
            It acts as the stopping condition to prevent infinite recursion." P( P5 r8 [5 g, v+ R3 y. v' H
    ; B) @/ f, Q1 O
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1." F/ |/ q+ U) `

    3 \1 l, j! w5 ?  l; W    Recursive Case:2 [, H# {: E6 K, I! h7 D( X! Y* j

    * f& ~" Z0 F+ D- V        This is where the function calls itself with a smaller or simpler version of the problem.
    2 D. }6 M# B1 d6 J
    3 d5 ]  n1 P  e* H        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).* q( J) h9 v; E6 ]

    4 v: @; d( g, L5 w; w0 |* U" |; {% D* XExample: Factorial Calculation
    2 O8 a5 d0 P: ]' P# Q* }) H$ U0 h) z  C2 X
    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:
    : V( k9 \$ w) @) E- N: ~6 B3 W% h1 v8 C1 K- g
        Base case: 0! = 1
    , o+ m5 B, t: }# ^8 j" n  O# D3 J. a% p! ^+ y
        Recursive case: n! = n * (n-1)!
    ) F# l* }2 [* f( E$ s1 R$ U8 t" w4 }7 `# D/ `' h  Z' X" y& s
    Here’s how it looks in code (Python):( n( a% {; P! T$ \6 t0 ^" t" h
    python3 f% `* c9 g1 k4 X# L1 R
    / ~! _0 j" L6 k6 h

    ' x" f# m6 l9 H; r' l4 [- B! P2 zdef factorial(n):
    2 }$ _) e/ R( C/ U5 v    # Base case4 {! i+ B$ x* B# k7 c
        if n == 0:! @3 T3 q5 ?  r% j! e
            return 10 d5 R0 l0 y3 i4 k
        # Recursive case
    ' J1 K! y' L7 g% O) \) Q( P    else:
    ) y- X: Q, W1 I3 p  k5 c        return n * factorial(n - 1)
    7 j3 `/ ^9 B0 C( V3 \3 C. E2 c% }
    2 S& p  c( ]$ m5 N( U# Example usage6 R  S$ B7 e7 @. d. q
    print(factorial(5))  # Output: 120
    ! |( J7 _; w2 z! Y+ \& A
    ' X8 g& L8 z  S9 IHow Recursion Works6 N0 K7 L% E9 u% }; r# J) y
    / W+ _6 v0 P6 F6 M! X. x  @
        The function keeps calling itself with smaller inputs until it reaches the base case.
    ; v* a* o: ~6 _) B
    5 A1 N! k4 _9 e' f0 _    Once the base case is reached, the function starts returning values back up the call stack.
    # {' J8 d& _7 [9 _; _& \
    8 J. }4 O+ E; {- v. [1 x    These returned values are combined to produce the final result.
    ; J  R; b$ V4 l/ B& @. Q. P$ `% R- X7 H/ F% v6 ^
    For factorial(5):& K8 ?* K* ~) m3 F8 _  z

    " e1 h& }! B) m$ u, e$ v( r5 b; V/ Y% W
    factorial(5) = 5 * factorial(4)* ?, \8 W* Y* r  G
    factorial(4) = 4 * factorial(3)
    & ?5 e5 Y" B. A4 ?1 Ufactorial(3) = 3 * factorial(2)
    " [* v- d- \( E1 }3 Rfactorial(2) = 2 * factorial(1)
    # Q2 P6 n  E8 q% dfactorial(1) = 1 * factorial(0)1 K, b# {3 F3 M: g, S' Z: n
    factorial(0) = 1  # Base case$ Q9 U; c* \, p6 s% a
    1 Z- x- Q! L$ R  R
    Then, the results are combined:7 `5 r* f9 \/ O; ~
    * |: d5 A6 V& S4 ?
    4 y% o. ?/ G$ K& f0 r/ d
    factorial(1) = 1 * 1 = 15 u4 j1 U- Q* I& \
    factorial(2) = 2 * 1 = 2
    * x# d, _1 M' Z& j( l& qfactorial(3) = 3 * 2 = 6
    7 G& i3 q5 K0 s9 Z; ~$ I) J8 F- kfactorial(4) = 4 * 6 = 245 C) Q! r8 f2 O1 ^$ ^
    factorial(5) = 5 * 24 = 120; K& ]% L- \3 i2 l4 Q+ U

    9 K) ]! E# i  r2 J! BAdvantages of Recursion; l( L( f+ D1 {

    : {3 c9 _. c- D1 U    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 w1 N; Y  U" a9 I9 _( x8 |3 H$ j  r! Y# j3 x
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    5 ~+ o0 B: A" |* x4 L- V7 @
    " H; B0 W- u, q- H; eDisadvantages of Recursion
    - y- N4 N) i; y4 r2 s4 T- `. w0 c" I0 T$ 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* x9 ]  g1 e$ S! J0 [0 \: f" q& q" _; @2 [. r5 s
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    7 k0 a$ `3 U  o7 v7 m$ _1 p% x6 ^3 h  [% H$ K- m1 ^0 c) v
    When to Use Recursion4 ^1 ~8 v: a! }, Z% E
    2 Y+ }; W  a) c  Y
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    . b+ c' M% p/ T: ~# T' T' h
    : o! I- L2 M; P2 a6 a8 T    Problems with a clear base case and recursive case.
    & `- e/ w" z" [6 t; B+ a1 {- R4 U  t# v
    , B0 }0 q3 B& B2 pExample: Fibonacci Sequence
    2 w! h, |0 _& U3 L: I' y5 |
    ! k9 X. y( f7 {+ F# k/ NThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:7 |9 G0 ?! H# c$ K

    1 j7 S% S7 P+ k* }% R    Base case: fib(0) = 0, fib(1) = 1
    ' Q. r8 H. d* e; Y& H* G
    8 I7 M/ |* u7 _+ G    Recursive case: fib(n) = fib(n-1) + fib(n-2)- i$ f- C8 ~$ u' l5 L! o* Z
    % U: [# S+ A  p# ]1 q+ W
    python
    : Y2 s* O7 k+ J- {5 _
    ; m, _- d" w( @8 R1 I/ l) ^! b! \2 I- k$ M
    ) T) a- x+ t. d# d0 K. L, e8 ddef fibonacci(n):
    * _0 ^2 u$ t: b) y* w& x3 W    # Base cases5 w0 z, ~+ O9 D8 s5 W. n
        if n == 0:  y2 x8 T2 z* e6 p& }
            return 09 L; x6 O1 c. r' p- Z
        elif n == 1:. f: b2 ^: _- b( x, L/ V" q! R
            return 1
    6 F; K: v8 I. k% U7 c* O    # Recursive case! F) |! R0 F0 H6 z& R
        else:
    2 Y8 Y5 C" T! m        return fibonacci(n - 1) + fibonacci(n - 2)
    " ^6 `" g6 G5 v1 a3 L, G1 t. j
    8 W2 @7 _% S8 s. `9 B4 e& h7 Y# Example usage1 M5 P4 g" _9 O' W+ c9 j
    print(fibonacci(6))  # Output: 84 R% |2 u  g8 X; w

    + }: k/ H: v. o8 j+ @! mTail Recursion
    + P8 W  Y" D! f& r3 T) ]/ b
    ' Y) t7 b; W6 N1 f+ R2 N' gTail 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 Z/ |9 j5 W9 C4 F2 i7 v
    - q* k! d2 L1 I5 D  O: K! Z5 ]5 w% ~
    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-7-13 14:04 , Processed in 0.057911 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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