设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 ' c) f$ r6 Z" V" l2 y
    / [- \  G8 F7 z4 B. @
    解释的不错
    3 R" O/ u* l/ C; K$ v, o; n
    ( k8 u& J9 g5 p; L2 j递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    0 \' A" x: B% {* B6 J1 [" x' t/ f  K: q/ G7 Z4 |5 n
    关键要素
    - a1 k( k" Y" `8 T1. **基线条件(Base Case)**' w8 L' z$ F' r
       - 递归终止的条件,防止无限循环
    / P5 ?$ G' s' x" R- ]   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 11 B! W2 X; p" p2 v* k4 N% U3 u6 @
    1 i9 z2 n+ v8 H
    2. **递归条件(Recursive Case)**
    1 k% d! ~$ c9 H+ u% d7 z" R7 k   - 将原问题分解为更小的子问题, {0 w! W2 e5 {
       - 例如:n! = n × (n-1)!. Z  d1 I/ P, D1 w

    2 y* Y6 o5 s% j: R; V 经典示例:计算阶乘
    ! a, E: n/ b4 m5 j6 t/ m( D% G1 Zpython$ b; J) T# i- X+ ~$ s5 G' R
    def factorial(n):; a! n5 E4 D8 j! t" Z/ I% h, e' Z. \
        if n == 0:        # 基线条件0 B" ]: E! P7 ?4 J- S" \( P
            return 1) @7 W, A/ _" t2 |; q/ f0 ]
        else:             # 递归条件; Y7 ?+ O3 G& e! [1 I
            return n * factorial(n-1)
    ! {) h% R+ o# d# e7 B执行过程(以计算 3! 为例):
    : X. M, R% k; Z! r- {factorial(3)' g$ x% B8 e- V1 E5 }) g1 W* D2 @
    3 * factorial(2); o. o/ m0 j* N, `1 ?9 i8 P% C/ r
    3 * (2 * factorial(1))) a7 k# P% W/ \, J. a( O
    3 * (2 * (1 * factorial(0)))
    - z: L( p& z+ t# M. s1 ~3 * (2 * (1 * 1)) = 6" ~7 M: ~8 V* d

    " |& e# M' F1 J7 } 递归思维要点% h; V3 C& i/ Q% F. H% ]
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    8 ]# B5 O+ d! \  @8 |6 t3 J2 l2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    , ?4 ~7 T! i1 B% V2 v3. **递推过程**:不断向下分解问题(递)
    8 [2 h* V1 H" r% B% o" J& }. P4. **回溯过程**:组合子问题结果返回(归)! N  z0 r2 B$ G# W4 X) ]# h
    ; Z. m% U9 R' o, H" d: D
    注意事项8 y  ~! i# \( k% q% c* U
    必须要有终止条件' M/ i! c8 s& B
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)1 N2 a6 v5 n$ ?
    某些问题用递归更直观(如树遍历),但效率可能不如迭代9 K% G8 @; X6 M  E* B
    尾递归优化可以提升效率(但Python不支持)8 |6 u$ {& w8 H. i* i; }0 S% [

    * H% p: S( S: M. G 递归 vs 迭代9 X" C3 e; ?& h* d- b+ t; M
    |          | 递归                          | 迭代               |
    4 u" y5 o# Q% x. s; q" D|----------|-----------------------------|------------------|
    " H) ~& g/ s$ U+ X) Z, y, f| 实现方式    | 函数自调用                        | 循环结构            |1 P* `8 Q: n  p& N
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |6 Y9 x1 ~/ w# W+ S
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    0 e; r: c9 C# O. }2 S| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |. B+ N* _+ C+ i# z) h5 s

    1 p$ {9 }. a  Z& f( A# @& j; u 经典递归应用场景
    + W9 g; g) ^2 v) Y0 L1. 文件系统遍历(目录树结构)  w" I) {/ o, D, l/ c: z
    2. 快速排序/归并排序算法( q( M+ X' k: n; U6 O
    3. 汉诺塔问题
    ) u# B0 x: C7 D, s- S) \# H5 t, v/ o4. 二叉树遍历(前序/中序/后序)6 a  ~) B0 i1 d. F7 V& I7 D) `: }2 k
    5. 生成所有可能的组合(回溯算法)( N6 Z9 W  J3 a4 [8 L' e: `
    & k5 ~2 p. U2 {! Z- c) {
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    擦汗
    昨天 14:35
  • 签到天数: 3132 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,9 r7 \' H: P8 q5 K4 k
    我推理机的核心算法应该是二叉树遍历的变种。6 `8 [( C- q6 o7 F1 d+ R
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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$ \) _# v6 s/ h+ x! H# ?! yKey Idea of Recursion
    , ?/ z1 r: u1 @1 s1 x9 W! P1 Z. g0 t+ Y  B
    A recursive function solves a problem by:: z( P* k/ Q$ k- b: A, k

    : X" ]5 N5 P$ F; K4 d: [    Breaking the problem into smaller instances of the same problem.+ y1 X' l1 _' y4 E3 v
    1 @$ T& T( m) q# o+ y+ ~) U# C
        Solving the smallest instance directly (base case).
    - ~* l/ ^# y5 k" C: L4 G& T3 z9 [$ J- u1 ^5 T$ c6 m- J
        Combining the results of smaller instances to solve the larger problem.
    " {7 D( |* C; o2 E: J7 {1 `" a  E3 ]  i' a3 T
    Components of a Recursive Function
    8 p" |' }% L6 `2 ?. }# r1 e2 o1 Q
    - j$ m& a" X+ m8 J- `    Base Case:5 t1 B$ O5 k1 v+ B( U+ A# H
    ; C! t8 Q2 |; U! G' Z6 @. E( o
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    3 u. W& ]. V/ S& U$ P
    ' n, R& ~6 T1 I        It acts as the stopping condition to prevent infinite recursion.8 w% ?' _4 @7 J% ?3 g' V7 P( b

    8 B* _# _8 g: u$ t% S8 v7 a, D        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.0 n& o7 @1 }5 c) Z

    " P9 C1 A2 Z8 j. T% V- ^    Recursive Case:5 j9 b  j) ]* n

    6 H+ B" |& Y5 |4 v        This is where the function calls itself with a smaller or simpler version of the problem.3 W8 P# m3 Z1 \# h

    : r3 K  x. |! X) G  a; J1 Q        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).3 W% ?$ ?* r1 Q6 d, l2 r3 d
    ( A* ?" H+ u0 r* X# g6 A9 }' c
    Example: Factorial Calculation
    $ d% P, K, N) T! {  _. j8 @& H
    ' e, B4 @: ?! @9 YThe 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+ }; n- p/ \
    : W% h% v6 M% o) u: O2 ]2 i    Base case: 0! = 1* l( n! V" h+ `: m6 @4 Y

    2 t8 _! B0 q- Y& H3 u# A7 O3 C    Recursive case: n! = n * (n-1)!
    $ H% O: ~1 z# V  \5 N4 v: q& M1 }% h5 j" q6 n; {
    Here’s how it looks in code (Python):( w, r' o0 e6 p  V! ]
    python0 H# ]) I/ p3 _, ~& I, s( N
    " [3 V: a( d0 g' Y
    / C% Z* G1 E/ j; H% P
    def factorial(n):/ z" R0 @: s; b2 @# E+ B3 H* |
        # Base case3 e/ e" i5 ~$ P  R
        if n == 0:
    ) z9 I* b; ]% Y        return 10 N1 g  |, V7 t2 X6 {
        # Recursive case8 N9 ~) @" w/ p
        else:
      @3 @9 k! Q' Y! H, d        return n * factorial(n - 1)6 N! @3 k6 E9 i5 Y9 z

    1 X  M- W- D- `0 [6 s7 d2 W' t# Example usage' d- i* `. a/ T; g3 @* e/ V
    print(factorial(5))  # Output: 120$ w: ?# W& h2 W- r7 c- b, R) u
    4 [5 D2 [/ t* W, ^
    How Recursion Works
    + I3 I1 P3 p- i2 e2 D
    1 t- W, U$ t- c& I! i# |    The function keeps calling itself with smaller inputs until it reaches the base case.
    . K5 J' O0 J4 P0 r: p4 B7 o$ ^( P% y- O$ k" r4 d
        Once the base case is reached, the function starts returning values back up the call stack.
    + f  Q; H; o; z" C4 `- j9 e( G
    ; |; y/ L- q; V5 D1 q0 z3 S; U    These returned values are combined to produce the final result.
    : h7 @* {0 q5 P2 J, f$ x
    # \0 R. M  h/ i; r/ j' j3 z( \For factorial(5):
    7 j/ Q2 j' v% [: U! C' ~7 A+ j
    * W0 o# F, A2 U- I5 T2 r/ H
    6 r# y0 ?; m, o0 }3 u5 Bfactorial(5) = 5 * factorial(4)
    $ Q1 t7 y, _& [9 R% I' i, d4 Wfactorial(4) = 4 * factorial(3)7 a8 @" P  ~" [7 x1 @# ~
    factorial(3) = 3 * factorial(2)
    ( p( @5 c7 ^# Kfactorial(2) = 2 * factorial(1)
    2 J# h) s' R0 s6 y  V; J6 Xfactorial(1) = 1 * factorial(0)- d9 \0 F. k+ i7 U/ n5 v3 ?
    factorial(0) = 1  # Base case' U3 j  X% ?: ?" F( f* l

    4 K) F( ~- g' q2 @" NThen, the results are combined:. ?& O/ O! y4 q6 W. [+ M

    2 R" z# z( M' E7 |' \
    $ A' p, _) g4 [factorial(1) = 1 * 1 = 1
    0 {4 q$ h8 e+ i5 m, w+ ^factorial(2) = 2 * 1 = 2
    & J5 h5 C8 C7 K# Y( ifactorial(3) = 3 * 2 = 6" ^& J) ^: g( [1 `- y( `
    factorial(4) = 4 * 6 = 24, \' c6 S0 I; S5 X: m/ D
    factorial(5) = 5 * 24 = 120
      o( Z$ [8 |& q8 }; H0 d2 ]; T5 e
    Advantages of Recursion+ `6 N# h1 _7 M/ ]+ S% P8 K

    + P8 n4 G* o6 B# f- I) ~* 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).1 C5 V* i7 D, {- a! x' [+ x8 G

    . d2 p# _- k2 u: O    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    7 Z1 |  B' Z5 ~- V8 r
    : K. I% e; r  M1 O5 ^Disadvantages of Recursion3 h" V. t7 g) \/ l! M; M
    1 J  K, ]. ]- T& N( r0 L6 L: }5 ]
        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.
    7 o- N) [) k7 F; P! U! }9 R. `  x8 Y- l" G8 y% k7 A
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ; d- O, p5 Y* L9 l1 N$ }) ^8 a. E/ @5 m
    When to Use Recursion
    7 ]# |6 O6 _+ [! \# C' U( U
    + d* C( ]  S! _3 v    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).% m5 K* K0 v7 N
    & _  u% L/ K) n/ T1 u$ |
        Problems with a clear base case and recursive case.# }" h+ z: A0 X- P5 o  X! H! r

    / V' w' S! B8 C9 [% \8 ]  l  S8 KExample: Fibonacci Sequence; L* M7 D$ }) J( k( {& @5 I

    ( C- I& R5 [2 d# s! U* f$ |The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:. G, T. Y3 ~8 A. |  ~
    ) \3 i( n7 u8 n7 N  D( |' Q
        Base case: fib(0) = 0, fib(1) = 1. p" [7 q6 \2 {& o' C9 o" N2 K3 f
    & ?! w2 H4 c$ g" A
        Recursive case: fib(n) = fib(n-1) + fib(n-2)8 ?2 q: P3 \* t) ^+ V
    : Q; |3 b) T# c0 h
    python
    * _% O0 l! ^+ }$ U. ?0 N
    ; R9 R- [, i7 D7 R* N+ P/ s5 o4 H7 T3 U! N5 @' a
    def fibonacci(n):' h+ p9 p% v; P, P
        # Base cases
    ; V6 Y, ]1 _" H& w' j    if n == 0:4 D6 J* M/ f7 b+ g) C: A4 ]& \" X" h
            return 01 q/ g9 z0 A; ?. m( `, m
        elif n == 1:
    / R, r6 d+ b* ?2 S8 |        return 1/ l8 e0 N4 t; Y" h  t# Q4 n* F
        # Recursive case
    2 Z4 b( ]! t- ]3 z6 r    else:
    + r  ~& A3 O4 n6 K7 p        return fibonacci(n - 1) + fibonacci(n - 2); H+ u/ ^1 U: ?$ [* }/ J0 P7 ~2 o

    1 D8 ]+ |3 Z# i* x. O4 M9 d# Example usage
    " E. z' a# a$ a$ z8 p; H4 d$ X- cprint(fibonacci(6))  # Output: 8
    / f. t( ?' I! z- z& o" ^" f, D+ Z$ I- v# z9 X. d2 {
    Tail Recursion+ L5 X; t. G' Z

    # D& I) K0 z- r4 HTail 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).6 y  F- g5 s7 _& B

    3 q* p- g9 c+ K' W$ g0 S* U  cIn 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-1 02:04 , Processed in 0.034462 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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