设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 8 f  r- s' `) n
    2 X' {3 O& _* i! U) Y9 V
    解释的不错
    ! h! ^/ j6 P1 u
    2 d5 Q( k1 _& I; P递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。/ t+ @" b/ z2 H* k

    ! `6 p. S* e$ H9 D 关键要素
    - [3 |! k) l/ N$ Z6 R" R1. **基线条件(Base Case)**
    . m$ }+ q1 r* k3 d$ E2 X   - 递归终止的条件,防止无限循环1 P9 L. S- J6 B; \
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    " O$ z% S  z* Z1 ]7 v$ j0 h: O7 Z. N
    2. **递归条件(Recursive Case)**
    * w. L6 Y! m4 P9 c3 c2 W   - 将原问题分解为更小的子问题
    & L2 {+ a/ T* C: i: P   - 例如:n! = n × (n-1)!
    4 {# V9 B: }( B3 {* ~& O! s# W0 X
    2 W, X0 @; ?$ r' d7 ^; p. { 经典示例:计算阶乘9 D- h0 v" W, X1 ~
    python
    3 s" N7 [) G8 C$ h6 h# pdef factorial(n):. C; Y. @. j, z6 G% w; F" T
        if n == 0:        # 基线条件
    + s' i" U1 Y# M        return 1
    3 u. r* ?2 Z" S, e2 h1 t    else:             # 递归条件
    6 _8 Y$ m0 a) Y. A        return n * factorial(n-1)& h0 w2 T# V0 W: f
    执行过程(以计算 3! 为例):
    ; I$ Q& P5 ?* w0 p$ J( [" ffactorial(3)
      |1 k3 J* T3 Y9 D3 * factorial(2)8 b1 C: v# B* ]" i* n, z
    3 * (2 * factorial(1))
    , _! _) `1 f( I8 p& Z3 * (2 * (1 * factorial(0)))  Q7 f, G) M8 s) w' b% t; t. g7 X. v
    3 * (2 * (1 * 1)) = 6
    4 N5 k9 s; V: W( j
    $ L. U; D7 [* @& R 递归思维要点9 v! j- P. s& k- Y% e% `! s- I
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑3 q% G0 u/ T3 \- F% H4 k- p* Y
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    ) n7 H' ^' p# K9 x5 e3. **递推过程**:不断向下分解问题(递)
    1 `6 n2 Z: m. [% W) S4. **回溯过程**:组合子问题结果返回(归)
    $ Q$ q4 b, C1 J4 j
    2 H5 P. j. ~+ h# X 注意事项7 B# I' d5 n& p) K
    必须要有终止条件6 g' s( O9 {. x8 Z9 N9 ?" i& R- H) W7 W
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层); F+ L4 W; a  G5 I: q5 f
    某些问题用递归更直观(如树遍历),但效率可能不如迭代% Q: S; p; J) @; A! U4 K: `+ K* d8 P% Y
    尾递归优化可以提升效率(但Python不支持)
    # @4 j9 |# |0 e; `9 y5 c' g
    # x! _- Z, i1 D$ n, R5 i 递归 vs 迭代
    6 o1 e  b" K+ F3 \|          | 递归                          | 迭代               |
    3 P1 H7 j% d% P" e0 \|----------|-----------------------------|------------------|
    0 v& g* m. f7 M# C. m| 实现方式    | 函数自调用                        | 循环结构            |- T5 _; Z# E% ^* a' e; O: X
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |0 Q1 _+ q' X# d( a8 g2 }8 v" g6 D3 |3 H
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    5 k8 i' c1 b4 T& a| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    6 j/ ]; w0 p# F- n. p& {+ x; q' \% r+ |$ M* J  h9 N
    经典递归应用场景
    / L) l* `6 X% b7 a2 @1. 文件系统遍历(目录树结构)6 K4 B: f) Y3 E! [- b  l4 d# ]# z
    2. 快速排序/归并排序算法
    % K7 o+ `- `/ H7 m1 w6 ]6 a3. 汉诺塔问题
    6 P3 K8 l, C. p! u4. 二叉树遍历(前序/中序/后序)1 I. B) c7 `) o: B5 H5 d+ X
    5. 生成所有可能的组合(回溯算法)
    % a/ y. J$ ]9 u5 |
    # F3 Z1 P) f6 g$ C试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    昨天 07:21
  • 签到天数: 3224 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,/ E; o" I  J4 ~7 D
    我推理机的核心算法应该是二叉树遍历的变种。
    ' O1 l3 H6 M3 ^" c5 @, @- E, U% O! z另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    ; K3 T0 k6 C6 A$ F; z: `Key Idea of Recursion$ y2 u/ R2 J4 D
    " ^; a: r4 `$ S( J
    A recursive function solves a problem by:" y/ [5 i2 W7 t/ z  G7 l

    $ c$ K% N. b# `- Q: l2 L5 r- P    Breaking the problem into smaller instances of the same problem.' d; O, b, \  |" I7 z
    9 s2 ?) t# V6 @) R! e$ A
        Solving the smallest instance directly (base case).
    4 s3 L  r6 z7 F! @, m3 a! ]! z4 p4 p; D7 [0 O! s6 D
        Combining the results of smaller instances to solve the larger problem.1 x5 S) t8 g$ Y' ~; Q" c$ v

    8 }, V( g. G! d5 E+ X! q  IComponents of a Recursive Function0 I! O( `4 R1 v9 I, o1 H' {+ W
    * X" k" q* d  A' d2 v1 f: [" O
        Base Case:
    # W/ T& `; W% A) T8 |
    9 g% P9 s- H- Y- y        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.7 n+ @4 L& k+ ?
    ! |/ V+ U; ^" v7 s/ ?) p8 x8 c
            It acts as the stopping condition to prevent infinite recursion.& Z/ C  x5 X1 S' p

    8 D5 z' E: u9 w# c        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    % ^, _2 r; y: S9 ~3 ?% x! Y9 L$ ~, {% O, Q$ g
        Recursive Case:* g# A1 p+ i9 a+ C, u3 L
    3 S1 W% V' d& i$ T
            This is where the function calls itself with a smaller or simpler version of the problem.
    * P- k' t' G6 k( n( Y" m7 G) D: G4 q2 i
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    % `( B& }6 ]8 ]2 u3 ]0 M1 V4 L
    % K3 T4 }3 \3 L9 |& P5 {Example: Factorial Calculation4 }2 R$ |# B3 g& m$ [1 j+ i
    5 n8 C7 s- P% l6 {1 L; L
    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:/ M0 f4 Y" J  L( k3 m. D* N
    1 N/ V# o3 j2 Z, q4 G
        Base case: 0! = 1
    4 `% y7 c/ V8 u& d
      w" y/ c- V& H" r# ~4 \' @    Recursive case: n! = n * (n-1)!
    ; O+ Q0 h) S  T9 ?+ Q. ?: d6 ^$ w* s0 j4 x2 Z0 n9 W$ E0 X- p
    Here’s how it looks in code (Python):
    / k+ p9 l' E0 G; z, wpython
    ) N: Q5 D# l$ I# [# L3 [
    , {- T  T# x* H9 ]4 Z4 ?& J; K: `1 e. p; W" t' U
    def factorial(n):/ S/ {1 z+ [- I$ l$ n
        # Base case5 ~% q8 n7 ]8 K1 C, V
        if n == 0:
    6 X; P0 R" F+ l% Y: j        return 1
    ) h% a) V/ J( n2 _    # Recursive case
    # x9 u4 e+ F3 i* T0 x    else:
    6 r+ G& Y* _- v2 b        return n * factorial(n - 1)
    2 x7 u" t' P" x1 M$ j& l2 e) A2 q4 ]% P9 K0 y! a
    # Example usage- s  b* r. Y& u; Y" x
    print(factorial(5))  # Output: 120
    6 |& y8 M$ V2 s( k+ L5 s- k! F0 n. k& ]# l4 u' b
    How Recursion Works! e. j& |$ k& J

    ' |0 M3 X" a: j; J    The function keeps calling itself with smaller inputs until it reaches the base case.2 t) K: S$ [# K- B( c" }  K+ U

    , g3 I" I8 H. I- N    Once the base case is reached, the function starts returning values back up the call stack.# @5 R- L8 l' h; `3 p+ v+ ~
    3 w' d9 V  K/ Z. k5 M: O5 U
        These returned values are combined to produce the final result.% i/ {' \  }$ g1 H, i- B7 f* B$ v

    1 e; d8 N; I# `/ Z, ?3 [4 \% \For factorial(5):
    " P7 @& ]' t: E0 [2 G+ P. ?6 E2 j1 ]2 @$ R  A* ~, q, ]
    . D' q/ |: k. Z2 L
    factorial(5) = 5 * factorial(4)# ]! ]0 ]) ]- K* {& t# t
    factorial(4) = 4 * factorial(3)* Z6 t: Z- M8 U% r; R* ?0 y
    factorial(3) = 3 * factorial(2), _- e2 `( B9 `. D2 ?2 c5 t; S8 B6 D
    factorial(2) = 2 * factorial(1)4 q' g7 Q' ~7 _+ j; h
    factorial(1) = 1 * factorial(0)
    & m. b# I0 W; W3 j8 f6 U7 ~factorial(0) = 1  # Base case: m( k4 k" }  s# e7 l

    # F1 n, I( {/ }2 w) BThen, the results are combined:
    " h) _, X- X" |( @6 `/ s% N& a$ N' `0 ~4 b+ i# ?! V

    . J  v2 P( @9 x; s/ zfactorial(1) = 1 * 1 = 1
    $ }1 ~9 ]4 h+ }9 S9 B, ^  ffactorial(2) = 2 * 1 = 2
    - [! }# Y+ }* R5 b' L& _  afactorial(3) = 3 * 2 = 6# V; r: b* K3 o+ s) o
    factorial(4) = 4 * 6 = 246 u7 v! S, {1 _" Y7 u! @; L
    factorial(5) = 5 * 24 = 120
    % U) Y6 A( h9 O+ Q  r, j4 A, D% K* p8 w1 p7 k+ t( X8 Y7 J+ G
    Advantages of Recursion
    5 }0 x+ ?" B& J  n
    ( X- B1 |0 {, L. ]; Y% v    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).
    , Z& P1 a. q7 |$ b) X" r
    4 @% M8 T) j/ Z! @, C1 f, q    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    ( {+ \' N, M2 ~9 Y/ W+ U' A( \; k- l' Y
    Disadvantages of Recursion
    # g5 E" E8 ?% L& }9 e0 V6 B3 f/ o  b( ~
        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.
    : w$ q5 |! ~( w. e/ m+ \' w: H& J
    $ d) P$ t  a! p! ~" q    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ) U2 M8 r7 j  I1 j, X6 H- u. t
    When to Use Recursion
    ! Q+ Y3 F. y* a+ z
    2 d) X' K! n! U: V9 }    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).  d7 g( ?+ K$ W7 a5 e8 k% G

    " @8 L9 l& L" j3 q, ]/ k    Problems with a clear base case and recursive case.
    ( z0 o) `! x3 L; R( J. Y2 h. }. h+ g* A9 E/ i. g) i1 d
    Example: Fibonacci Sequence) c/ p9 L  }2 ^" q7 d- r4 L
    - J2 x% w3 r. F9 x% w
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:% V/ Y0 ?6 n0 \  I! K# m6 Q
    " F: c. j- A! Q: m' u- N
        Base case: fib(0) = 0, fib(1) = 1( S, C% p% r5 l( ~* g
      D: e5 l" U* W. f( |
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ; z" Y5 c4 A4 a/ O+ ^* u6 y
    ( y; \% ^. b. `9 Xpython
    % `2 p6 v4 o7 P) v8 U
    - z5 y  d' x! f& M, o; j& S; }- `/ W5 m0 g
    def fibonacci(n):
    ) V- B  ?# Y, W    # Base cases
    ' ^- Z' b% ?6 I    if n == 0:/ |4 L1 E7 x/ m; {( L  Y
            return 03 r* S% p' U: e8 j4 z9 |3 c& `
        elif n == 1:
    % P- j! Y- ?/ D& j- O( S        return 19 e4 i* t9 {; \- {0 y
        # Recursive case
    / t4 C8 \; Z! q    else:
    0 g* d6 f9 |: T. H        return fibonacci(n - 1) + fibonacci(n - 2)
    / g: D9 d: x, o  h8 g/ j7 @7 p) K* [8 u: W
    # Example usage0 H  F5 \5 P" d( r
    print(fibonacci(6))  # Output: 8
    ' E/ U0 e' [' `2 f3 Z, _
    $ B7 f8 f! d# w' ]3 fTail Recursion
    . u. A  u6 \+ ^2 ?6 E; X' H
    % C) j( ]  h7 M: ~1 u$ I) O; FTail 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).4 |8 H  U+ l; O. e# h& D5 `, [

    5 t+ Z. S$ V5 c; 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-4-26 17:24 , Processed in 0.068030 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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