设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    1 d5 u# u6 G4 l1 ]2 f: I# x3 w
    * n, c4 A! e2 x$ U, b7 A7 {/ {解释的不错
    % y1 o1 V/ w) R3 B! v5 s) e) @* B4 y# {. r# j3 q1 S2 Y1 u- k
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    # X; P9 x! r- o( m3 u- G3 r: i
    / `( B+ {" M6 I% G. C4 o! L. _8 b 关键要素' d# f, [  _/ s9 R# R
    1. **基线条件(Base Case)**
    & [1 k* h8 h" J1 F: G/ f' V" m$ k   - 递归终止的条件,防止无限循环! v! ]. X: N# ~  d
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1$ A% R) d$ e- M+ E! I

    6 D& ~/ f0 b0 j0 h% P' `7 L: ^2. **递归条件(Recursive Case)**
    + T4 D8 R, x! J( Q. `- L8 ^   - 将原问题分解为更小的子问题
    ( O5 L( _" O# k0 h; E3 W) ^   - 例如:n! = n × (n-1)!
    ) r! G. N3 P( \! V7 `- o: r
    2 t  u, i' J5 d, C' U 经典示例:计算阶乘
    2 ^( B: B( S' A- K. I$ u9 Upython
    ) G& R& ~. u" Y2 H5 `! \def factorial(n):, T# N- c! T( p  B( o
        if n == 0:        # 基线条件
    / S5 [, k  i5 w% E; j        return 1
    2 J! t4 Z8 W8 L+ E2 p/ M0 _* X7 Q( U4 g    else:             # 递归条件4 j) a& h/ [% o7 U9 n
            return n * factorial(n-1)
    + j; p3 w7 t  O* h) i- M8 ^' R0 Y执行过程(以计算 3! 为例):) l* r6 |. }" C
    factorial(3)! D' n& \0 G9 ^
    3 * factorial(2)
    0 |7 G% ^5 Y$ X; B  U, a% b3 * (2 * factorial(1))
    $ e- L2 {3 {0 D' U: C3 * (2 * (1 * factorial(0)))
    ! @& I! V0 n# q& X+ A* t3 * (2 * (1 * 1)) = 6% B1 z! m- v4 P( y  N
    . H5 [; B* l1 [
    递归思维要点
    $ p, H7 v5 ?& ?5 W% F1. **信任递归**:假设子问题已经解决,专注当前层逻辑6 x8 R+ u( j/ ~/ ]
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    + l$ P' [: u# h* |3. **递推过程**:不断向下分解问题(递)
    2 \$ T, e% ?& X3 _4. **回溯过程**:组合子问题结果返回(归)
    6 ]. c# @7 R. C. n: q, n5 C
    # ]0 Z2 I! d% m4 J& f! d 注意事项
    ' J8 y; |( ]8 z/ Y0 g5 J: d必须要有终止条件: a4 L& b% J) j, F+ k" c* T" M6 N0 o
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)3 v' X5 _- ]4 H5 F6 {
    某些问题用递归更直观(如树遍历),但效率可能不如迭代' K3 ^  w+ F+ w
    尾递归优化可以提升效率(但Python不支持)# s2 b6 K; A& }* O; H. C: {! _

    : g6 n* s6 u/ U 递归 vs 迭代
    5 c2 u" N* L1 r|          | 递归                          | 迭代               |
    8 Y* u" |5 C& L5 ]|----------|-----------------------------|------------------|
    1 W$ d8 U) K4 X| 实现方式    | 函数自调用                        | 循环结构            |
    8 b, ^2 h* r/ Y$ [; W* ~& O| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ; A- C9 y) o2 ?$ B| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |& a0 ]1 Y* n, h5 e. ]
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |$ [% t4 G- q. \: W& Z5 K8 y
    . `, U9 X6 Y( {; U, t* h9 Z
    经典递归应用场景% M8 Z9 g; w2 M0 u. r5 {
    1. 文件系统遍历(目录树结构)9 {  D5 l+ H) Z/ k
    2. 快速排序/归并排序算法
    9 S. `5 ?, F! G$ t3. 汉诺塔问题" A9 f0 B# Y  V* F
    4. 二叉树遍历(前序/中序/后序)
    + @: K$ x0 w( @2 l# M5. 生成所有可能的组合(回溯算法)1 U: u$ ~) d9 n. v6 w" ^
    / Y% J5 N% P2 l/ M% @- t4 i! x
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    22 分钟前
  • 签到天数: 3163 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    3 A: T/ M$ b+ A4 y  s0 [我推理机的核心算法应该是二叉树遍历的变种。
    & D9 m, k4 y* ]另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:/ N7 U. W, O/ S3 c# H
    Key Idea of Recursion$ o4 b- G3 M4 X4 ^
    2 _! N0 r3 U3 V9 D/ @
    A recursive function solves a problem by:
    5 V/ S' Y2 P2 u; x# F; L5 x) i* M
    " o) k; L) G) E- K    Breaking the problem into smaller instances of the same problem." n$ f9 l% F+ F  f' _$ X% S2 H0 P

    ( j) B/ q5 j7 \& r# a    Solving the smallest instance directly (base case).7 Q' j$ |7 X' _$ V- e
    % O- M. ~2 O/ b' a$ |) Y
        Combining the results of smaller instances to solve the larger problem.
    5 u" B5 [$ [) H; i' I7 Y; ?1 D+ T* y/ V- h
    Components of a Recursive Function
    ; S, W, c% Q% F; l( J: ?; N1 l; V! w4 R( {# S9 K
        Base Case:1 a0 B$ ^) \/ `6 R

    $ K$ z. B0 y6 U+ o        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.( k3 A4 S, C1 S7 v1 o
    " o6 U. K; z) o5 K
            It acts as the stopping condition to prevent infinite recursion.
    , c8 E! M4 [+ N( D7 N" z; e  m0 I) a- _6 p9 V# q6 @8 H* x: F
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.) y& _/ {! y" g( q

    / {- _8 A6 {, b" k    Recursive Case:
      p2 k9 n/ }2 b! c
    9 c- ~( ~! {& U5 P/ T% d6 E        This is where the function calls itself with a smaller or simpler version of the problem.  \8 x7 k. Z; B$ U* Q
    3 n' o( c- E' P
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    4 N1 ^7 E7 n7 L7 R1 f2 ]! k7 l# ^1 T$ l, V3 a2 \: b5 G
    Example: Factorial Calculation
    2 w) X1 v6 I, D! d" V  [/ j
    5 r0 N* p+ j) ~- x3 a7 LThe 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:# S! G/ H2 W( I/ ]
    2 g3 B" ]; |; Y/ k- q8 {
        Base case: 0! = 1
    - S6 d# k% ]' h0 {  y) F4 T$ K5 r0 k
        Recursive case: n! = n * (n-1)!! M( {# H! T1 S) _

    + G; Z( b8 A. \$ L: E6 N8 ~% DHere’s how it looks in code (Python):
    6 i/ T3 `" o" s( M/ z; \python/ s8 F  |4 U: H. l. w3 ?
    9 ~4 k( {5 I9 e2 i; |  c

    ! H2 E% O9 P  E4 r, r5 P1 Ldef factorial(n):0 f9 X4 K: b4 _" F% f
        # Base case* r6 Q% a; A/ [7 X
        if n == 0:* m9 Z+ X. H: ^4 r4 A% c. s" ?* g
            return 1
    / W; o& u' U6 N- m; Y0 g4 x) d. X    # Recursive case
    . ^; s9 y% Z% G$ o  D2 G' d3 {    else:
    - E& o- M9 z% E5 R* f4 w        return n * factorial(n - 1)
    * N. v, G1 E0 Y, @, o$ g  Q  v! R: W/ n2 A5 m9 q# }- e
    # Example usage6 I6 z& {% e' t8 V6 J9 v
    print(factorial(5))  # Output: 120
    7 u( A; g! Z& {! F. d. x7 b; d
    ) }. u' i* K; F1 x4 s6 OHow Recursion Works7 D. U$ o$ U; t: T

    0 a+ l9 B7 `8 ?: T    The function keeps calling itself with smaller inputs until it reaches the base case.' F1 B+ P6 {! z9 N- q
    ! h) M9 L& w( W4 |
        Once the base case is reached, the function starts returning values back up the call stack., u9 ^* ^4 W6 R- N' D

    - R. B) R. Q4 W    These returned values are combined to produce the final result.( q" c7 Z' X7 D( O

    3 ?! ^$ x" F. q& i" d( iFor factorial(5):
    , Z, b! J6 d  h9 ?- F
    * V$ H6 e) L7 q3 R2 t
    & ~$ ^/ v/ X% ]4 \. _4 R' ^factorial(5) = 5 * factorial(4)0 l1 W. B- R; c
    factorial(4) = 4 * factorial(3)
    * ]6 b% M3 ?2 tfactorial(3) = 3 * factorial(2)" l5 z, N3 S+ Y% Y& F
    factorial(2) = 2 * factorial(1)) p+ [0 s' T# ?$ b5 O: u
    factorial(1) = 1 * factorial(0)
    # W/ b$ M( O, ~& B! hfactorial(0) = 1  # Base case) g* b4 z( P3 K, z4 S

    4 ^2 [0 K3 n  fThen, the results are combined:/ x+ F! _+ q; O8 q* @" R

      d  s( a0 Q4 Z% e8 m
    3 g- T2 j% K5 ?factorial(1) = 1 * 1 = 1
    ! u5 _! X8 I, J! bfactorial(2) = 2 * 1 = 22 b0 K, ?1 t/ p* Z9 M
    factorial(3) = 3 * 2 = 6% |5 s1 t) Y. Y: Q# ^% d8 L
    factorial(4) = 4 * 6 = 24
    & v9 ^4 m: x2 qfactorial(5) = 5 * 24 = 120
      i7 P8 M$ W, g5 [. k2 b$ \: h; {$ ?0 L: Q4 I, S7 d5 H& f
    Advantages of Recursion
    5 ?* u& ]6 |3 f
    6 |; ~' f! ~1 a: A9 M2 B% g    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).$ S+ ~& i5 o2 B# @9 Y

    # t: m7 x& S6 f$ U! F    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    / i6 I) Z6 d3 k3 u) ~/ ~3 u/ @: _/ @/ V
    Disadvantages of Recursion
    0 h& |3 |) \. d% N! j: x: ~0 [6 c( U/ |$ p! {
        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.
    ! I# G4 T& C, N7 u- |
    * @: M5 j8 U* A" B6 T    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).+ `4 Y8 r9 u) \. }2 ]- K0 F  T
    , X3 k3 ?1 |# g0 d. [7 s
    When to Use Recursion
    ) s! [- x4 w# `3 |3 E3 I" J7 ], {6 o0 B' \: Y* ]* j/ H/ |; m+ F# L8 }
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    + h& z6 x6 w; k) d4 _* @0 O& G' r. u( W" \
        Problems with a clear base case and recursive case.
    8 t' J2 u" N: I  c, z, z5 }5 ~. u4 A
    Example: Fibonacci Sequence" Q" A$ u2 P1 w$ c3 s

    2 R1 ?6 O+ X8 T( L# cThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:, t  l3 o3 a! I; w( J& Y" p

    ) `7 ?/ f. r1 V    Base case: fib(0) = 0, fib(1) = 1# s* x+ s0 ]; o" X+ k
    % B& j( N: O" `+ }. f
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    / l" Z$ v- S/ y, u/ T7 M
    2 \  T0 ?1 L1 G# \, P, ^python6 u- v  M  Z# m4 K

    " e" N% r9 R5 Y% ^+ o+ c( y8 K* J; L4 g- `" }% C
    def fibonacci(n):
    " O- F7 q& |  |, @3 H, H    # Base cases
    " f+ M0 o& s0 q& n    if n == 0:
    , P. v0 y' N- i5 {        return 0
    & W" k- _3 Z2 r) h$ `    elif n == 1:
    . L" V) b/ @6 y) d2 E        return 1
    0 {/ v  s* R/ q  z6 R8 d6 O    # Recursive case0 q3 \  u" P% g9 z' J- D3 l% j. T6 {$ u! x
        else:
    / T, M; p1 I8 q% n        return fibonacci(n - 1) + fibonacci(n - 2)
    0 U" ^& y5 F4 U5 C  z5 {) h- B. y" U/ [4 l# K
    # Example usage. ~" ]7 j5 z8 _
    print(fibonacci(6))  # Output: 81 c# j& h9 @" \0 L$ R# j

    5 Y' {7 _5 B; [1 ?& N: ]6 zTail Recursion
    $ T* M; M, }  u
    - ^8 x& R6 a6 |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).
    ! q4 l& P6 M2 W7 v
      o5 j. d* c( q+ G3 U$ NIn 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-2-4 06:42 , Processed in 0.061879 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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