设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    , d7 I  I2 e9 V& l& i2 r+ N% F  b8 B  i. f( p  y
    解释的不错
    7 p2 G2 L/ y6 C# X8 m4 t, E: s3 Z! T; }
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。5 M2 U+ D6 C$ G7 t6 c! J2 ]
    9 G; i& }' @4 |9 c# A
    关键要素/ \0 k  E7 U5 a) A3 D' L
    1. **基线条件(Base Case)**
    - n$ L. }$ H5 z: T( q: Y: [   - 递归终止的条件,防止无限循环
    ( B) h$ o) Y5 E$ _   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 13 L9 j) L8 }) \& g3 D6 b3 s
    3 o( j6 ~: N; B6 E5 L" @
    2. **递归条件(Recursive Case)**0 t! Q  c; T6 d! W9 |/ }0 F7 ]" i
       - 将原问题分解为更小的子问题
    & b9 G8 W9 I9 `5 j   - 例如:n! = n × (n-1)!! G$ r, ~% C. E

    / F. a# v& J0 ]$ f 经典示例:计算阶乘
    % k. S3 ]; ]' u6 U# R4 T, a/ e& Wpython
    : Y( X4 F5 R! `) A9 z2 S# P5 Gdef factorial(n):# Q/ f1 u" F( p0 I
        if n == 0:        # 基线条件5 ^& O. h$ N# F; a
            return 1
    , [2 D3 L) X5 L% Z/ W5 }* l    else:             # 递归条件2 N; ]; A( Y& }, s' \1 W  |8 [; E
            return n * factorial(n-1)
    3 X. a" w( F) [! T执行过程(以计算 3! 为例):8 z, g$ i% `. g0 Z8 U4 B
    factorial(3)/ L( k; v* ^& [! @6 o: ~9 n# x
    3 * factorial(2)8 n; G6 q  V9 a' m
    3 * (2 * factorial(1)), `! l( H) X* |3 e0 F8 X) Z
    3 * (2 * (1 * factorial(0)))& P, {$ z' S9 K5 k
    3 * (2 * (1 * 1)) = 6
    * K7 l/ j& ?5 W3 T, k" J) z# v& f& J9 p& h, B9 l$ g
    递归思维要点
    % R9 n; R6 t2 ?- |# s5 a1. **信任递归**:假设子问题已经解决,专注当前层逻辑. c' a; f: U, s" d9 O
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    ( V7 b8 ]3 @* {8 Y/ l3. **递推过程**:不断向下分解问题(递)
    , a7 R: c( P  M; z% g4. **回溯过程**:组合子问题结果返回(归), q0 T9 R+ x$ M  B9 {2 X/ e& Q

    ( ]) j0 g/ D$ h; r& P- Z% W 注意事项- A3 B% p5 R( ?# [$ X) C
    必须要有终止条件, |0 Y2 H) q8 e' h8 j4 D
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    ! ?8 |- h8 [: G9 j/ w; U某些问题用递归更直观(如树遍历),但效率可能不如迭代$ S# ^6 u: w5 M" b& y8 t, f
    尾递归优化可以提升效率(但Python不支持)
      W9 V# K8 O/ l2 s1 C1 ^7 N6 c* S/ z( x  K8 n1 \% u7 _
    递归 vs 迭代" V$ V7 ]. c. M! s" M
    |          | 递归                          | 迭代               |+ }8 T# t6 s( K
    |----------|-----------------------------|------------------|7 h- E: R' ]$ e$ G
    | 实现方式    | 函数自调用                        | 循环结构            |8 W0 \" u* d: l) @: d5 ~4 n& z2 a
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ( }, l, u2 R: Z; K5 G+ C* y| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    & D" ~& [0 X2 d! j6 O0 u9 }+ v7 U4 r| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |! Y( ]. j, c: z4 O; a

    7 _4 L- X' T" N& d 经典递归应用场景
    ( b4 F, Y# z8 i& R* l* p6 K. b1. 文件系统遍历(目录树结构)! ?9 P& i! U) ~1 v
    2. 快速排序/归并排序算法
    5 J9 F. b. o5 `1 D3 X; z/ Q3. 汉诺塔问题
    9 ~# p! y# b! e) q3 t5 [, e4. 二叉树遍历(前序/中序/后序)
    9 U; y- _2 d/ z5. 生成所有可能的组合(回溯算法)
    1 Y: l: w: F1 t' m3 N( t
    - x2 I- X, i# l1 x+ w/ }# \试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    难过
    昨天 08:02
  • 签到天数: 3171 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,6 [4 @" H8 B. h3 e# U. ]+ E
    我推理机的核心算法应该是二叉树遍历的变种。0 f9 Z, @% V' A+ Y5 s6 G3 ^2 [4 K
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:* A4 p. \" _( Z/ ?: O9 M
    Key Idea of Recursion$ L( ]8 ~8 }* D' J! d- M9 _' n
    , J0 |$ d( _. F) l
    A recursive function solves a problem by:
    2 d( _/ |/ u! U1 W3 k: A2 b8 D4 m
        Breaking the problem into smaller instances of the same problem.
    # w: `9 c6 X2 R. c% n5 C
    + V% r8 S  k* z    Solving the smallest instance directly (base case).
    9 D$ G; F9 P7 `6 D: n3 @2 b) j; S7 g4 `" k, D1 \2 t
        Combining the results of smaller instances to solve the larger problem.
    , m+ o. ]0 s& a& F; `( l6 h# u9 u6 u5 ~. ]3 p5 t4 B
    Components of a Recursive Function
    , T! ]# R+ i( z# J8 N1 ?" c$ X, P3 i1 O- ?
        Base Case:, {) n+ ]  D% k

    : ^8 [) P7 m$ h4 Q        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    . n5 q8 z$ r8 C& j# q( |! N7 ~. G' _+ c0 e9 K) a" O( c) Y3 T
            It acts as the stopping condition to prevent infinite recursion.
    7 j/ H6 b6 w$ `0 ~% O: [; i) J: i2 D" t9 H
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    0 U3 p4 d2 a1 a3 t5 C' A
    1 C: b, q+ x3 a1 B    Recursive Case:  J# o7 Q- A6 b% `1 X

    0 T* `- N7 {( u8 v/ c: {# @        This is where the function calls itself with a smaller or simpler version of the problem.
    ! }' v. X( r: H1 h
    ) o' _( H1 N' X2 x' Z        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    # k4 Q& U4 e0 d7 |; e- Z# x1 j' r; o; c4 ]. X% q: w
    Example: Factorial Calculation  N7 E9 d9 A" c( r

    , F6 G2 D5 w8 }" G: ^: JThe 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:3 A5 h8 |, n: ]( z8 I
    & c# L) ^  s- ]7 j" c$ p* i) e0 {
        Base case: 0! = 1
    7 {8 u' X. |+ {. F8 J. O- C+ Z- e5 \- V6 {: ~* u& ^
        Recursive case: n! = n * (n-1)!5 s! a! {2 O6 s/ G- R+ G! z
    2 d' v4 i' M1 B3 w+ r, M, v& w1 Y0 ?
    Here’s how it looks in code (Python):
    $ X* q5 U8 n0 H" S; ^python6 n) m( W2 ~1 x4 z  I
    ' I" S6 w  m/ c2 `" e) H
    # H  u- g- [' [$ A  b
    def factorial(n):7 z2 N- `0 m) U: c
        # Base case
    ) N8 [  K1 }* Y8 i( k, ~' J    if n == 0:! i1 ^1 i  d/ g- B7 D
            return 1
    7 b1 o- @! [$ B! c* [& d1 ?    # Recursive case( w. f0 B5 r, Z- k! g
        else:
    * b3 \6 _% U5 N        return n * factorial(n - 1)# A/ S+ S; m$ Y( f

    + B1 b$ G; X" v% q9 Z6 t6 l: U# Example usage. R4 J) o" R/ p) \6 d2 L7 D: n
    print(factorial(5))  # Output: 1207 b. Y6 r, r/ b

    . `5 X, k6 I7 oHow Recursion Works3 C3 l8 c/ R' y) ^) C

    * ^' `5 X3 g) y6 U* K    The function keeps calling itself with smaller inputs until it reaches the base case.
    / @& q  r! m- T
    ( v/ ?; O# J4 C# l! K    Once the base case is reached, the function starts returning values back up the call stack.. ^2 a% O& z) Y3 q1 V, E
    ( s0 d* e. ]2 T. G: B. t
        These returned values are combined to produce the final result.) C9 Z/ k5 d- l4 t; R0 U/ Z
    , X8 g* M3 S3 S. h
    For factorial(5):
    1 R( r, W5 U' {7 s9 ^( W
    ; `9 w* f6 e# i" s4 O/ ~; S: T8 j$ M- I- B( a2 f
    factorial(5) = 5 * factorial(4)% x" ]6 z! }5 ]3 b: ~5 D
    factorial(4) = 4 * factorial(3)
    - M7 g* [- h; ^, j3 z3 {factorial(3) = 3 * factorial(2)
    " E8 H3 R9 @4 V! k8 J0 ?factorial(2) = 2 * factorial(1)
    : C6 \" `7 V& C4 v8 q6 E( z7 g- H" `1 b  Ifactorial(1) = 1 * factorial(0)
    1 T# ^& K' v: Q7 m+ ~factorial(0) = 1  # Base case
    : k3 r+ @; |9 M  d( M
    ( F0 m& f; l2 |) `2 ~9 r; l4 uThen, the results are combined:, z$ o0 ?" L- w% j/ z, H; o
    ; P" s/ ?$ ~. I) d0 p( S9 ~7 Q8 s/ O5 Q

    ) f3 q8 l# C1 x  Jfactorial(1) = 1 * 1 = 1
    " H/ ]3 g$ r+ _2 g* d. z  Vfactorial(2) = 2 * 1 = 2
    * i5 P* f3 m: wfactorial(3) = 3 * 2 = 6
    - t  U7 [* O! \) Y: n. e! e# o6 nfactorial(4) = 4 * 6 = 24
    ' {6 A6 Q, f2 f) r1 P. U5 Cfactorial(5) = 5 * 24 = 1201 [  @  s% s8 K9 [% _
    ( f7 H4 Q- a. q" A
    Advantages of Recursion* j5 Z9 J) Z+ C3 F% c
    $ ^* E5 A$ N1 v+ M
        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).$ a0 ^. X, U5 W! N# y3 F" W# {

    2 q4 m: f" Y9 E5 {    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    # m6 R$ Y0 S! k7 Y
    % n* F8 ]+ l; h( i9 a  u4 a  }Disadvantages of Recursion
    3 P" `: W% p0 C# p' G! t' L5 g
      G3 n$ r7 q; w  R3 q- W& y    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.
      C6 o1 p! P9 K; }' L4 e, V. q, M  {/ Q
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    9 V% i6 S( N9 R- W0 N
    2 F. [% D/ k3 g% c4 w7 VWhen to Use Recursion5 s) m' C2 ?* w; j7 f% J5 I

    . j! z9 o6 x) G& ^$ {, ^9 y    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    , i7 s) l  F8 L5 o1 q- Z3 Y. `/ m9 E. |0 `
        Problems with a clear base case and recursive case.
    + V3 c% y$ [' s2 S. M+ Z, ^' \3 q( y5 A2 i4 ^4 d" L
    Example: Fibonacci Sequence
    % m" g+ ?" f' R' A
    8 H9 f# t' Q1 T0 ?4 _The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    . H: o" a& s7 r! ~( n3 \& d* R2 D# l) K2 s. w6 o* \
        Base case: fib(0) = 0, fib(1) = 1' {" t5 v  M) s  @! l

    5 j3 B6 y1 m0 A0 U! |+ g) P  {    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    : x( [6 I  d- @+ x/ H) n/ w3 C3 ~5 M" P
    python
      q+ a2 Z) k" v$ [
    $ p! K4 M) z. D* t3 n% d, ^1 d' n$ V- Q# p& b0 n$ d
    def fibonacci(n):% m6 j" U1 ~& q3 k, h7 D
        # Base cases0 N' v  }, ^/ C
        if n == 0:3 q: H! ?8 P& n8 V9 _9 B9 ]+ [
            return 0
    2 i3 ~- ?2 w2 l( o# ^9 p4 ^2 A    elif n == 1:
    ; g& W3 S- r. l5 Z' \: ]+ P        return 1
    # y9 ?9 f: L/ N5 \7 B! v- \, b    # Recursive case
    * c; b( Z) k, c2 ]5 }8 i    else:
    7 B% V6 X, A0 ^& X1 M4 G- n% b        return fibonacci(n - 1) + fibonacci(n - 2)
    # D( V, w8 D: b* |7 M2 W8 Q+ ?9 i4 ^
    + j' R  _6 J6 v- M9 R# Example usage) P' T/ T' A6 a  O' Z9 h
    print(fibonacci(6))  # Output: 8
    - r1 Y9 V  f; @8 e; C, W
    % o( M1 {7 Z# x" {% V% VTail Recursion
    ! i( u; {/ V$ o# J7 V$ d$ H, Z4 B* p- _! N$ q
    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).
    : u2 k9 U* b: I) s8 J- y, G+ U& t9 ^2 h) y% }+ Q2 l
    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, 2026-2-13 04:59 , Processed in 0.057884 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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