设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ; f* _. E0 q5 Y5 c+ ]; N
    1 K8 @6 X4 K* O6 ]7 j4 D解释的不错
    6 Z2 E7 N2 }/ G' ?+ o
    1 C9 M2 L% m: C8 y9 ~7 \+ N( @+ v递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。: U6 ~. p7 g5 B; }  Y' k9 J

    + R% j& l% t8 t! N 关键要素
    : X+ F7 |8 {; j6 H$ o1. **基线条件(Base Case)**
    % t6 I- f; ]# x% q* h9 W) E3 p   - 递归终止的条件,防止无限循环
    8 e7 d3 K# C! M+ \0 V" u8 ^   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1/ E7 F6 b2 ^. }5 o' Z: b. T
    + G+ f4 y- m1 F; _3 r6 B
    2. **递归条件(Recursive Case)**. A$ G+ H) ~: W
       - 将原问题分解为更小的子问题
    ( h4 u6 h2 Z4 U- X/ ]! R/ u" C   - 例如:n! = n × (n-1)!
    * q+ l( T2 P3 Z; c% W  ^/ c( S1 j
    经典示例:计算阶乘& Q5 _' R$ A7 Z: Y( q
    python: k# }8 p% `7 E- |& \. v
    def factorial(n):
    4 w3 i% [- n- J$ a& F: l5 }    if n == 0:        # 基线条件3 a+ B0 N- L! Y4 ^& l  O# e& w
            return 1. q, o! y. b, _" G7 W) ]  p
        else:             # 递归条件
      b7 L& L4 C: y6 v% z* S' \5 F        return n * factorial(n-1)( l. p0 I9 f% z6 Y* O! d
    执行过程(以计算 3! 为例):) ]# n. t: Y3 I+ j
    factorial(3)7 Z7 V6 j* n2 D6 d7 a( k3 {
    3 * factorial(2)- E2 s; e6 O3 K7 \
    3 * (2 * factorial(1))7 i9 e0 G2 c4 E* j3 [
    3 * (2 * (1 * factorial(0)))' v+ ?2 g7 `9 k5 z" @
    3 * (2 * (1 * 1)) = 6
    5 Q8 E( S+ C% M: A8 o3 Z2 t8 b( X; v1 ~) I2 j& j; X
    递归思维要点1 e1 z4 B6 R6 @* ^( H2 k: c, L: O- {
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑4 d, [5 v/ _( ]4 ^  T5 W
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)9 H" E) B6 I4 L
    3. **递推过程**:不断向下分解问题(递)
    9 s  T3 k+ z+ [3 f4 E3 U4. **回溯过程**:组合子问题结果返回(归)
    / W8 g. |+ @' j- u  R1 K
    8 l( B9 N: I7 f5 {9 C. c 注意事项
    5 }% Y6 F) G3 B2 [& k2 i) R; G0 F必须要有终止条件0 f8 Z1 q* t" J, u+ g
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    " W3 Y7 c* z/ e9 U某些问题用递归更直观(如树遍历),但效率可能不如迭代
    - o  R$ `% B0 k0 o7 s+ E尾递归优化可以提升效率(但Python不支持)) D$ U$ c- ^$ z1 z

    * R  p; d# B7 x! L( S# O. J$ g 递归 vs 迭代
    ! v3 Y1 ]$ }5 z9 x  Q$ A|          | 递归                          | 迭代               |6 |  o& a# T0 l
    |----------|-----------------------------|------------------|' V. ], h  [+ Z+ ~
    | 实现方式    | 函数自调用                        | 循环结构            |
    . w* w; X( N+ V3 c- _5 h3 F' m| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    & H. @( ?; L0 \' l| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    5 v! x% B- h8 `' n| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    9 L! t4 v# L! l: U
    5 u' g& A7 z6 ~: k" C3 c 经典递归应用场景- p* |' K) h, P% _6 G! I
    1. 文件系统遍历(目录树结构)5 I; Q/ Z* J; X  O
    2. 快速排序/归并排序算法
    " J( @7 j2 g! D: A1 \3. 汉诺塔问题: ]/ J9 F. w) |$ S: d
    4. 二叉树遍历(前序/中序/后序)4 Q$ X1 A, V7 V
    5. 生成所有可能的组合(回溯算法)
    ) U1 c$ `& Z1 e
    " l0 q5 t7 v; Z5 |- C, [1 a- ~# u* D  \试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    昨天 06:43
  • 签到天数: 3101 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    - q% J: Z" @5 s/ j9 \6 j我推理机的核心算法应该是二叉树遍历的变种。
    7 X: b4 d- C9 c1 _+ b/ q另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    4 w3 }. \; a5 m9 zKey Idea of Recursion, s: D1 e4 c8 j4 A  s3 q3 `

    4 D( j1 j( N6 U. _$ cA recursive function solves a problem by:1 C! }7 t6 `; x) i, }

    9 o5 n9 |5 Z1 Z0 B! Z" I6 M6 I    Breaking the problem into smaller instances of the same problem.
    0 ~$ a' h$ E0 R& H! [7 b+ M$ d* A; Y" z7 ?% U. T5 B
        Solving the smallest instance directly (base case).
    6 y+ I! ]+ L! B2 I+ L& ~( M$ m- N7 X- f2 ]
        Combining the results of smaller instances to solve the larger problem.4 a& k  a: B- O# G, w2 C
    # u5 v3 V$ w5 X
    Components of a Recursive Function
    2 y  W& `! B) H  H3 g" D- c, }/ h1 ]) u+ I5 W1 G9 v% Y
        Base Case:2 z& t0 B3 {  |$ A4 s: d4 f# }
    0 [; D9 k# C/ {- M
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.3 M7 v" ^. n' x
    4 }) `9 a' \' M! C
            It acts as the stopping condition to prevent infinite recursion.6 S" S# [+ t5 A' W

    1 U9 p7 h( Q$ L! Z        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.5 K1 z5 Z6 X! f& w
    ! A, d4 J7 |# t2 r- Z# k3 v( M: m
        Recursive Case:1 Z: h! c6 f( d# s! q& g  B. V/ S

    ( L5 H8 n3 j  ^( H* q' x        This is where the function calls itself with a smaller or simpler version of the problem.! a0 }9 z7 ^; W6 E0 v8 ?! O
    ' k; _' T# r2 L. @4 W
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    5 |. N+ K- w1 A+ C8 B* }5 y, R( a6 v" Y" P4 ?
    Example: Factorial Calculation1 Y" E2 M7 ?, b7 b  M) p
    : p' S# ^7 N; \4 b: 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:" g( l: T& E) U; p; Y$ H
    ( x9 K4 }* Y4 i/ i; a2 ?, a
        Base case: 0! = 1
    4 w7 v: F) m# q' C  k; S0 e, }  v! n# K
        Recursive case: n! = n * (n-1)!
    / v* L; q* G0 Y$ x: q! V0 l4 A
    7 R4 O* V  S6 w" o# O" Z) EHere’s how it looks in code (Python):3 w& z' u" M# j/ K
    python
    # ^- t! N# z5 Y8 z( a5 D0 f$ T* [: Y  Q. q6 O6 V( B
    / m6 {" s0 L0 N" j$ u
    def factorial(n):& H" d( J- C! x
        # Base case
    & R: V: A$ \8 K1 d5 S& l- H1 B    if n == 0:
    * M) {: w7 @  Q4 Y! p. f7 A# X        return 1% w% W' i- |: Q6 z, a, c; J' {
        # Recursive case
    ) w# B( x7 F$ |    else:, V3 q  o( a! r  b' h( U3 s
            return n * factorial(n - 1)
    ( I# P$ @; w  u) I' |& Y
    ( P8 I7 ~2 u8 b% h' G# Example usage) p& _/ f! b2 W$ {
    print(factorial(5))  # Output: 120
    0 x5 F( b9 b! H  C5 D- A1 E1 H$ b
    + M: J- b/ ?3 u+ PHow Recursion Works
    9 d- Z3 n+ l4 |( e
    ! z1 k, f9 \5 [8 v4 Y9 w6 p    The function keeps calling itself with smaller inputs until it reaches the base case.
    * V1 C2 v9 B$ h  T% G1 v3 ~! T2 W3 P5 Z3 [6 I/ z
        Once the base case is reached, the function starts returning values back up the call stack.1 F  X- k" K! U

    . A4 t/ B. C- \, I& @7 C* q6 ^    These returned values are combined to produce the final result.
    ! t, T1 d) M8 x& |* m' x) Q/ Q" j' x
    For factorial(5):
    7 P( L5 k" c7 s$ V$ l
    : B! c; x# K6 \2 A4 v9 u  m; v  \1 n. H! k
    factorial(5) = 5 * factorial(4)8 U6 P6 i/ [! b- R+ t$ N9 b
    factorial(4) = 4 * factorial(3). X+ Q4 z7 v0 g1 `5 A
    factorial(3) = 3 * factorial(2)+ S8 x2 H7 Z' D
    factorial(2) = 2 * factorial(1)* Y4 x) F7 o* Y' f* |/ V
    factorial(1) = 1 * factorial(0)
    * L  v% N0 m# S) Ifactorial(0) = 1  # Base case
    8 ~" r, |1 k7 ?0 C4 D% l2 `$ S4 x, W8 }/ W5 O
    Then, the results are combined:
    , K0 \/ X6 A' w( ]! t: {8 W, |7 B# t8 y0 X* Y
    : q( V$ [, H: k! P
    factorial(1) = 1 * 1 = 1
    0 A, i$ |7 v6 @) H8 i1 Mfactorial(2) = 2 * 1 = 2: w% C. ~3 h" n8 _% `3 ^, [- R) [
    factorial(3) = 3 * 2 = 67 y& i0 y# i8 @7 h, D% M
    factorial(4) = 4 * 6 = 24/ C7 w! V* B) k1 K
    factorial(5) = 5 * 24 = 120
    5 w) R4 U! i& c8 m8 [& @
    ) ]. @9 Z; G7 \; X8 w' V9 HAdvantages of Recursion! s# @/ J; \& a3 @  w
      P' ^  [' V* T' s3 t, e' Z
        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).; ?. S2 P- M9 s5 J1 J$ G) A) o+ @

    4 h8 \6 e: Z8 n1 p2 X2 O2 `* L1 ?    Readability: Recursive code can be more readable and concise compared to iterative solutions.( m& b: F6 C4 F' u/ i4 V* o

    $ @: o2 g* l) B' x) gDisadvantages of Recursion" _& \' T: v. c1 {) d7 d
    0 G3 U: m5 u2 b# v/ ]5 I
        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.
    1 ^/ j( ^$ ^/ M5 B2 B
    5 C9 H* z* A" T& V- p8 r    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ( {0 f5 y0 a  j6 w3 w" {# C/ @% ]$ n; U4 x& `+ n8 X$ t
    When to Use Recursion! b6 [9 p9 V/ ?/ B0 l$ v# H* \

    4 U& Z2 v7 F' P9 V4 o  {    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).' Y. L, r# y0 [! D' v' B
    ) c) q( N" V/ ~, M
        Problems with a clear base case and recursive case.5 E1 m* {( _/ I
    : [, ^3 e! z8 j4 o+ w5 f' h
    Example: Fibonacci Sequence
    - z& j3 s$ o0 V  v+ ?: o6 E/ O3 N' h& x1 I. A1 K1 v6 d
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:, g% [( T- `$ Z' x
    " v, t  [$ b& g2 b+ W
        Base case: fib(0) = 0, fib(1) = 14 c. c2 i: k3 ]8 o; ~
    6 S  ~+ ^- K; }+ H
        Recursive case: fib(n) = fib(n-1) + fib(n-2)8 J. e( d( r$ S& A9 @+ p

    7 p2 G; v% ~' |+ T) S( b# A) opython
    " p& h: b2 \# c. t3 k7 F: U0 n% y; j( x" V

    3 h3 O' n1 x; Edef fibonacci(n):
    2 q0 l5 F! R0 X& T    # Base cases
    : c8 v& k0 A: o% F4 H7 I9 p    if n == 0:
    ) ?6 K% G' T1 S' R" Y        return 0
    8 l5 K) L" Z! N3 G) L6 G+ u    elif n == 1:! x& H0 {# _8 g# L$ a3 ^6 K
            return 1/ D0 t' a# H6 T" A$ M( `: I7 M+ C
        # Recursive case; D6 Y3 N. p, O5 S# D/ o9 f
        else:
    : ?5 i: a0 K" e& ^( Q: d, @        return fibonacci(n - 1) + fibonacci(n - 2)  |" V5 }) G1 }6 [# E& M

      j) J8 p+ b) j5 t* V) Y# Example usage
    * ^: p0 \, c3 a2 g. l: Lprint(fibonacci(6))  # Output: 8
    2 D3 F5 a8 A8 k4 |2 Z; L9 v: T/ g/ g' }0 f7 V
    Tail Recursion
    : W. m4 f- H2 Q7 \% o, H# g6 W4 ?, {5 m6 c% o9 O
    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).
    0 j' P' ?/ f6 d: q; N; k' M3 v. f) D$ a  d6 ]" e7 X# U0 X
    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-11-25 17:46 , Processed in 0.070525 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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