设为首页收藏本站

爱吱声

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

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

[复制链接]
  • TA的每日心情
    开心
    2015-11-30 11:11
  • 签到天数: 2 天

    [LV.1]炼气

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    7 p- G3 ~$ @0 J  y/ x% I6 R7 v
    ' B, C0 ~' X* w8 T  ]$ X1 m解释的不错
    3 B( b5 d: S& O# V# h& @
      R* f( P; o/ I7 p0 B& @递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。9 }2 @* G) G' x: r

    1 ]- R8 z$ o) Y# }; f% `! _2 \ 关键要素  _1 P: n' |) y7 }$ \
    1. **基线条件(Base Case)**
    ) c8 _9 X' g9 _9 `   - 递归终止的条件,防止无限循环
    # K- D2 d8 `% o   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1, X# @, F- M* z5 w

      b1 P) b  r/ e& q$ V# [5 A2. **递归条件(Recursive Case)**
    ) f! E  z' U3 B1 v% K   - 将原问题分解为更小的子问题
    % K( x) y1 ^- |2 Z1 `- Z3 v   - 例如:n! = n × (n-1)!( l# x" D0 J/ @  ?

      x0 N& R% b) p" j9 M2 S9 ~3 ^" Q 经典示例:计算阶乘8 r9 `+ w9 t: ^
    python
    ( s; U* W- L# C& {% e8 U2 b9 c* cdef factorial(n):
    % z5 b' j. b" F. I0 I2 ~    if n == 0:        # 基线条件# y1 s6 O% M( I2 e. s1 s) w: M% \
            return 1
    2 U" i* B  K" n2 Z% r3 r    else:             # 递归条件
    ; e* Z0 X9 E) ?& T/ \        return n * factorial(n-1)
    % w. |- ]  B$ \+ L2 U' V% T执行过程(以计算 3! 为例):$ E# r8 a8 y1 i! [6 V" ~' @
    factorial(3)
    * @5 m3 F  b5 L8 \+ |) `3 * factorial(2)0 h5 x5 d1 h# Z5 ?  f
    3 * (2 * factorial(1))8 j& O1 n7 M& G% k2 F1 _  L. f2 k
    3 * (2 * (1 * factorial(0)))
    / j! P9 U. J5 _3 I' f1 Q1 M8 T3 * (2 * (1 * 1)) = 6
    6 l, x0 X& s$ {( B" N1 q$ g/ N) k. x: B) p
    递归思维要点8 o9 D# l' C1 E7 B  W8 \9 P, r
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    : Z) ^! t" v! m- |2. **栈结构**:每次调用都会创建新的栈帧(内存空间)% f" m+ N7 x& t. s
    3. **递推过程**:不断向下分解问题(递)( L7 e' i* _5 A* n
    4. **回溯过程**:组合子问题结果返回(归)
    , z4 ~; Z6 e& \1 k# V/ H. B6 g5 C9 L/ g$ h2 A1 ~
    注意事项& y, |1 S9 L1 p+ P/ L7 H9 O
    必须要有终止条件& H, [4 d1 @$ q# R9 Y
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)$ T/ |$ g& b/ h) z+ N# D
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    + h3 b% Y2 ?+ ]! ]5 c4 t  C尾递归优化可以提升效率(但Python不支持)
    % ]; D" S8 S' v6 x
    $ t! }6 Z/ l9 | 递归 vs 迭代$ J6 D* M1 w0 @2 ?% _& `0 z: Z& D
    |          | 递归                          | 迭代               |
    7 R* c5 q! k3 A0 s|----------|-----------------------------|------------------|3 A# u- k- T8 v" L  B
    | 实现方式    | 函数自调用                        | 循环结构            |
    + n  F4 V1 j6 W4 @, ^8 k| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    1 }- B2 w" N: y4 L& a| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |5 z2 y& x- Y. g7 V1 u8 ~! K% j
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    5 V& @) j8 r0 K" K* V( r$ u4 A  |$ X; r+ k0 ~
    经典递归应用场景
    8 L  n0 d9 x$ G" T. M. Y1. 文件系统遍历(目录树结构)
    . z+ h6 j3 ^7 G2. 快速排序/归并排序算法
    & W6 I' p8 }9 R2 I% Y) d3 l* h3. 汉诺塔问题0 H/ D% w% p& o7 D# T1 V
    4. 二叉树遍历(前序/中序/后序)
    4 ?& j1 X3 i* _% m5. 生成所有可能的组合(回溯算法)$ M* C) b( A- J$ T$ q

    ' j$ D: `" ?1 i* {3 u$ j8 C+ p试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    难过
    11 小时前
  • 签到天数: 2879 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    ) {+ p! f4 h; y3 U. G8 K1 u我推理机的核心算法应该是二叉树遍历的变种。- t: J; m; J6 ^+ V8 w: @$ o+ ^
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    1 Z: j6 m: U4 C4 RKey Idea of Recursion7 o! a0 o! M) r1 A
    - V6 _4 u- c( k3 C- l# z% V# y
    A recursive function solves a problem by:% k1 Q1 Z) E3 L5 v. G6 K

    8 J4 P/ C+ K1 ]2 p    Breaking the problem into smaller instances of the same problem.
    6 F; i2 F: f2 T5 ^7 b5 t
    ) |4 {! Z; z1 E# m* n% Q6 m9 D3 p    Solving the smallest instance directly (base case).* g/ f2 T+ \% q& F& H% R; x, ^
    - f3 a; T0 J! W/ k5 u
        Combining the results of smaller instances to solve the larger problem.% a7 r4 P+ {: `  {' t1 v2 C8 n

    ' b, K) T: e. k- {. x  OComponents of a Recursive Function
    $ i) s" N# o0 l' s0 T- ?0 {2 i1 G
    ; r( U) ]+ F) ]$ n8 M    Base Case:2 {8 T: O1 }0 q0 \! i/ e

    & z- z3 E8 a7 ^+ P# v) s9 m6 Z6 ]) t        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    4 T5 q  B! Q  j5 s/ |9 p& p
    : y& T! n! Y, W        It acts as the stopping condition to prevent infinite recursion.
    7 z. z8 d) V# D# S9 O- i) J
    ; w1 M5 X' h& v+ C0 q1 h        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.5 ~# z5 d7 Q  s9 q, l. z, l
    - G% M" q  G. U3 d& c7 E1 ]
        Recursive Case:) Z$ p: y1 R+ q2 s2 ?1 Q, c( U
    ( u( w4 j+ s1 o' ]4 g. D
            This is where the function calls itself with a smaller or simpler version of the problem.- ]$ {  Q1 X2 J' D: L
    8 n  |7 v- V+ J3 m* a. \& u
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).  }, X9 |3 e4 f- c

    7 s! p/ Z/ w. I) u/ ^! }0 AExample: Factorial Calculation0 E( e$ v! u( h: r) ?

    + v. c4 G' b' Q; W0 K8 G( F+ mThe 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:
    ' _* x5 e- q; P, H! v8 I. [2 Q( X3 F& k  |; g# c! q' f8 }
        Base case: 0! = 1
    6 F& L5 j: I. _( @7 S" ^8 `  N# x. S' U6 p
        Recursive case: n! = n * (n-1)!
    8 N0 [4 U! L5 U2 d7 t* a
    ! ?( a, @$ q; D7 o, x) m- EHere’s how it looks in code (Python):
    . e# @4 E( d% ?python
    8 {' Y' x% H" M5 x
    ( n  Q3 U5 [0 ?9 _1 I( {/ c1 c& u; y4 j/ A3 t& V+ I0 U
    def factorial(n):2 {8 n7 p' D1 V( k1 Z
        # Base case
    ; c) `& n* J0 e    if n == 0:" _! v, B1 r% ?( {( k
            return 1
    0 d9 W5 s9 N" H, J, A' d    # Recursive case/ O, S( e  R, U5 J7 B8 k
        else:% E2 V. h2 s3 }% [3 _& _" i( ^
            return n * factorial(n - 1). N% C) ^, F/ _" _( y
    . \+ H+ _5 Y# a  V! M1 e
    # Example usage
    $ j4 D/ Q6 [# i: l% }print(factorial(5))  # Output: 120' C/ u* c# ]! y. ~- h" f2 y
    ) S9 V% C( D9 z) ~) J, U( o9 |
    How Recursion Works: E  [$ ~! i2 C( Y

      o6 U. [* [8 y0 j$ u) M    The function keeps calling itself with smaller inputs until it reaches the base case.0 m& N7 I6 h, T
    / }1 C: Q5 {* H3 U. {/ G
        Once the base case is reached, the function starts returning values back up the call stack.* @! b+ F! R- W" O9 Z& W
    $ H  Q: U( x- Z# G9 R
        These returned values are combined to produce the final result.
      J& v  w3 x4 k% l) u4 w3 |6 P# p3 {& u. G
    For factorial(5):
    ) K- }, s! c, t, d+ g# ]: Z
    7 S* q% s% U! ]+ M" j' E2 d- E* {2 t6 a! O0 y  d9 z5 V
    factorial(5) = 5 * factorial(4)
    9 s# ]' W5 @) ?. J7 s$ Qfactorial(4) = 4 * factorial(3)" V1 ^- V/ Q5 B0 X0 y4 j% j
    factorial(3) = 3 * factorial(2)
    ( {; k8 Z7 ]7 P/ O; ^% K0 l3 lfactorial(2) = 2 * factorial(1): K' @2 e/ X; _2 m6 y
    factorial(1) = 1 * factorial(0)5 L( o" T' f- Y5 }5 y
    factorial(0) = 1  # Base case. j# z& N' P* r* X, o5 m( C: ?, A

    / J4 I# M  a/ W) I7 oThen, the results are combined:
    5 T; V$ Z; s0 ~: b7 h
    # m& x/ `" x1 u, j9 L; }& g- ~3 Q8 L8 F5 l
    factorial(1) = 1 * 1 = 1
    " w  y0 U( V- y* ~+ o9 [' _) U# Qfactorial(2) = 2 * 1 = 2; }  B: e2 j: R* ?
    factorial(3) = 3 * 2 = 61 p; D+ Y4 e3 X- S3 d
    factorial(4) = 4 * 6 = 24
    , H4 W3 c. ~' i; b+ t, ^factorial(5) = 5 * 24 = 120
    + c6 z9 W/ S* f& T3 S& U# I7 y7 Y# a9 p2 ?, s
    Advantages of Recursion7 e+ M  ]0 h) ^" ~$ K# J0 P
    3 i4 Y5 T: A# W3 A
        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).
    * R8 Y3 R! `/ P
    9 c" @- ]% I# q6 }. g# d! m/ F    Readability: Recursive code can be more readable and concise compared to iterative solutions.7 r( k( u/ }- |) H

    * M  l5 a) W, {- Z) V, ~Disadvantages of Recursion, u0 b; h, r# q  E
    3 A3 K+ h  d  b* [. q8 ]; h
        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.
    4 v8 C* ^1 g8 M( p& o5 P7 F% }$ k
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).5 h( e5 ]- q9 S& N, G! C& s
    . {) p% ^  k8 x: E- v/ g! ~
    When to Use Recursion$ {5 J2 v# H" o! p
    , j& j; Q" n: \+ @. D/ A+ X* A
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ; y4 Z9 y9 Q' T3 G/ F8 v, o  u1 g) Q3 t/ q
        Problems with a clear base case and recursive case.
    3 g/ F- O- Z/ R5 U* T& I2 n
      @# n  Y# P7 H5 l; CExample: Fibonacci Sequence* r4 r$ w/ y4 f, ^

      a% k: L$ J1 n  K# Z# h+ G* |The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    # P% V4 F2 L  w# O0 t# R& F2 @; ]4 p$ d$ g; L% n
        Base case: fib(0) = 0, fib(1) = 1# X3 I9 O7 M1 e: B- S5 F
    2 I8 f& ^( Y( V0 G  H: V0 M
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    1 @! y4 k/ J1 N4 p! l; F/ t* \1 i& j' v9 s0 p% V, c6 Q
    python
    8 U! d8 _/ F" |8 j
    . U$ W" W7 Q$ O
    6 Y7 n. y7 n& [2 E7 Zdef fibonacci(n):
    & I' E0 A, T. d3 s+ e) W( s5 B    # Base cases
    4 O6 c4 b8 W4 Z3 L& ~    if n == 0:
    + O* W6 ^( ~- I. H' c        return 0$ m; R% N( O  q1 N
        elif n == 1:; r9 H/ G- R4 f! v; U
            return 1
    ! N4 M8 H7 m8 Z, w    # Recursive case& C' w: l9 }2 _+ t2 I5 D
        else:& k$ x  B$ R2 j: V
            return fibonacci(n - 1) + fibonacci(n - 2)
    : `/ r" z4 g# q$ Y/ c4 h3 A! [0 Y: w0 {+ X# P9 b3 }7 e; d6 a
    # Example usage
    2 R  O4 F  K' }" i" ?print(fibonacci(6))  # Output: 8
    4 ^: v# p$ B  ~  c# Y6 B# |7 @2 u" t! G  \8 ?' o0 K5 ~3 \
    Tail Recursion
    6 b1 n% }  o" r# d4 _" q* X
    2 o) m1 C: z( C, H& p+ ~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).: @: C; q" H8 B
    2 ^. l: E4 X+ F! D8 H1 ~0 Y, H
    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, 2025-4-2 16:18 , Processed in 0.037590 second(s), 22 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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