设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    ) e  Q3 t  H# N& J/ c# R
    ! ^- W: E. t2 V5 R. V解释的不错. E# d1 e  H2 O3 y
    3 l/ w6 G& |3 U4 R2 t9 E! z
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。' ^: D$ e$ b, ~
    " g& k) d) e4 b6 b. {) v" ?, N
    关键要素
    + s4 y/ V& B+ m5 s1. **基线条件(Base Case)**! ^1 Y$ d6 y- L+ f6 T* w6 w
       - 递归终止的条件,防止无限循环
    8 `$ {0 u, W) a1 C6 I7 g5 e   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 18 W6 ^2 E0 u$ T" ?; K" y, i* P

    - O- h. w4 O* F$ l* A+ [2 D2. **递归条件(Recursive Case)**5 F* v- n+ _/ T# q& T
       - 将原问题分解为更小的子问题
    % z( ]3 M4 V4 ]; Q" K. c$ \   - 例如:n! = n × (n-1)!
    9 I' m2 g! m0 K2 S7 ^: P0 S# j4 |3 ?0 ~3 Z3 O( j
    经典示例:计算阶乘
    4 y1 C0 ^( s' ^, ]python
    # p: e, h3 U' C' N* F+ n  J+ Ndef factorial(n):
    . @, S$ i$ a% V1 @# }    if n == 0:        # 基线条件3 R. F+ M$ _7 ^/ {
            return 1
    : q' @2 Q% q+ p& s: b    else:             # 递归条件7 s9 J$ O# g. a/ z8 x  ~
            return n * factorial(n-1)5 O6 X: h! j, [6 Z
    执行过程(以计算 3! 为例):/ b$ V: k7 V- q3 U7 x- X
    factorial(3)
    8 }" F6 {, z' J; ?3 * factorial(2)
    9 t  g& P6 m( d/ [) q7 Q! u3 * (2 * factorial(1)); M: R9 b0 q2 z/ J8 ]  S4 _: D
    3 * (2 * (1 * factorial(0)))3 R  |( c% G+ j+ @
    3 * (2 * (1 * 1)) = 69 p8 z5 k; w* l' t- I

    % N) h8 _# C0 O 递归思维要点
    - N/ @3 H( \, j% J# }- S1. **信任递归**:假设子问题已经解决,专注当前层逻辑( y( e& h7 G- w' `
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)9 P" T5 B1 t$ v7 ?. W) G7 C$ ^2 u) g
    3. **递推过程**:不断向下分解问题(递)
    9 d  s' T9 U2 n3 H! m4. **回溯过程**:组合子问题结果返回(归)+ w: V" R+ v6 `5 e7 l

    4 U9 n3 [6 p: [- f0 I! q 注意事项
    ) Y/ }0 P; t4 O' K必须要有终止条件
    , ^2 z. c# z$ o递归深度过大可能导致栈溢出(Python默认递归深度约1000层)  O6 R9 L/ D( `/ c- g
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    # k" m( H0 s; @( A尾递归优化可以提升效率(但Python不支持); ~1 K5 i- R, q( I& `4 ^

    5 F" ^1 H6 [! B3 s3 T& s4 Z 递归 vs 迭代
    $ C+ [; F4 r6 C/ L& G|          | 递归                          | 迭代               |& t7 d* g) q7 @" l1 [- k
    |----------|-----------------------------|------------------|
    ; \6 k4 }& X/ V( U* g, D& v| 实现方式    | 函数自调用                        | 循环结构            |# ]! s" }- S8 R: @" I  S; M
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    % @" z+ D5 m1 T9 h: b. ~0 ^& K| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |) O2 N- L, E4 d3 ]
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |! A* c( X# p+ n1 d" r

    - M. z" `! D6 z 经典递归应用场景6 r6 f1 n' t1 C! K. F
    1. 文件系统遍历(目录树结构)
    6 W3 C2 s1 I- e' R2. 快速排序/归并排序算法+ X& _, C  N, Z/ u+ v& i) w
    3. 汉诺塔问题5 _* l+ N6 Z  S& x
    4. 二叉树遍历(前序/中序/后序)- ^1 Z1 u; ~1 [" w( t
    5. 生成所有可能的组合(回溯算法)1 {/ c( [5 F' y/ @: `& P
    ! X9 |% l% n* d5 E- o5 a2 i
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    5 小时前
  • 签到天数: 3113 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    4 `4 b( w/ @' A, f% v6 s7 v/ H我推理机的核心算法应该是二叉树遍历的变种。
    1 `4 _- E3 f/ D4 n7 ?' u另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:' X3 @- N6 \+ B. u
    Key Idea of Recursion
    2 u  {/ t  i+ ?
    1 [0 x7 g- J) v* A3 L% {' _A recursive function solves a problem by:; ]( u! Y$ L. W- F' ?
    : u7 r( `; O, K  T$ r# k- U) Y
        Breaking the problem into smaller instances of the same problem.
    * J- Y) i3 F8 u9 }! h! x9 X& N
    6 ?' y1 F$ r) S) E0 p3 [    Solving the smallest instance directly (base case).* ?' Y9 K$ R& B5 H9 {5 M3 [
    : f6 O0 ]/ T5 v
        Combining the results of smaller instances to solve the larger problem.. ^) [; U  z7 k% X* `: x4 ?

    # s6 i' g9 O% Z$ C7 r  t6 I; M7 A( ^Components of a Recursive Function
    # v. C  g6 B+ x3 f
    5 i9 l: F  o5 Q    Base Case:
    ' k1 H7 P/ r5 i3 F$ [' c
    4 P2 d$ e2 ]2 U' t* U9 [        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    + ~4 a( @( u1 R( f3 f- Z$ c; ?7 m  z0 B0 {3 G8 x
            It acts as the stopping condition to prevent infinite recursion.. [9 a, n, e6 |6 a

    3 e& u( k- T3 u4 [& p' O        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.' ~1 D; g& [$ N2 p- [
    ; z( G6 T9 p/ i) U; K% q! Q
        Recursive Case:! k, M( B- j6 y

    . r: R% V$ C3 y2 u        This is where the function calls itself with a smaller or simpler version of the problem.1 S3 z( Q7 ^% T6 {/ y

    5 B8 D/ E$ n2 `7 T6 S' O        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    6 S% M" {" d% h$ d) Q% w3 @0 o3 I/ t, M' w; F9 W) u! a4 H* i( A
    Example: Factorial Calculation0 D, Y5 ]0 x3 _6 J

    % O1 i: b* l1 U( M" P  N7 j: H& fThe 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:  }$ K, }9 j* E

    : b4 l6 O. x# g/ x/ M* m    Base case: 0! = 1
    ) V& {* a! z4 H
    - j% C2 e  Z* y# e! m& B, u4 n* s    Recursive case: n! = n * (n-1)!) s  o1 h% W, z, U8 p. @5 m

    % @- T- l6 Q- y- e1 LHere’s how it looks in code (Python):
    7 q" p. `% W/ Hpython
    ' s% ]$ I1 O6 K# j. E! l* C4 i( \: }# n6 X6 P4 v* [. q
      E3 x0 ^: Q3 D3 Y
    def factorial(n):
    , z2 U+ K( x. g. h    # Base case! x& E; t1 E( q* \0 P
        if n == 0:
    ! v8 X  w5 z6 r        return 1+ [3 R' _; y/ o: G8 W2 z: o
        # Recursive case
    & }! D2 r8 ^+ j2 z    else:
    3 }- j( d- _1 J! F* m. \        return n * factorial(n - 1)
    9 K& T6 [; B. a4 z* f) a- w$ u2 q3 |$ P$ p6 {( U1 B: o8 ^5 P$ M
    # Example usage6 Z1 q  O. `7 W- c- [
    print(factorial(5))  # Output: 120
    ) P+ g- r( A( u( K6 K) _+ H! K9 @9 T- \
    How Recursion Works, O3 U& H1 e6 [( P; P6 k
    ' M. [3 D* E( A
        The function keeps calling itself with smaller inputs until it reaches the base case.
    5 h5 [8 v, K; K
    ; ^7 c2 q0 N/ O1 \0 U2 u/ d7 k# \    Once the base case is reached, the function starts returning values back up the call stack.0 a4 L- b9 R  [4 w! r8 D# x

    ; d* d& H7 V8 W, m    These returned values are combined to produce the final result.
    ' ?6 l' u* e: w6 D  F& e( y+ t3 j9 Z! l" X0 T8 z9 f# ^9 \0 W' |' T
    For factorial(5):
    # v0 G+ i4 X3 J  w7 P4 I& p  E# _: h; J
    $ D( n" d6 x' s) E
    factorial(5) = 5 * factorial(4)
    " T' m9 {$ B1 \7 _1 ^- Rfactorial(4) = 4 * factorial(3)
    % g3 f5 O9 Q8 o; Wfactorial(3) = 3 * factorial(2)+ l+ m8 r: S  d6 x
    factorial(2) = 2 * factorial(1)
    3 K' |* L( G8 q  S+ Rfactorial(1) = 1 * factorial(0)
    ( p! k! k, q8 Hfactorial(0) = 1  # Base case
    ' K& K* c; P( H  v0 G* G
    7 J" z; ^3 @; G/ O0 AThen, the results are combined:
      M6 o! e% P, a: h5 [$ N/ S! ?, d+ e% p: J

    5 A* [! y, z/ R( kfactorial(1) = 1 * 1 = 1! \& ]4 T; x* g% `( S
    factorial(2) = 2 * 1 = 23 I1 |7 P, B# [% U3 ?* r  z/ q: `
    factorial(3) = 3 * 2 = 66 z" ]; Z4 \6 v  e8 ~& r8 n  t
    factorial(4) = 4 * 6 = 24
    ' n' f1 X) w3 v4 ]/ v4 F/ }( xfactorial(5) = 5 * 24 = 1203 o( Z( v; I6 u/ S4 V& T

    6 g0 O/ h2 p# _Advantages of Recursion; d3 i8 r$ i* x: u0 ~1 }$ s9 u  g5 \5 X

    / b2 W+ U; e; T/ z, E  k# f, 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).' V$ Z0 _9 q: Z  V
    " Y; \6 \$ f0 J! ^0 g
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    . E4 |& v( ]0 |& q6 G0 t
    2 k# U& M* }' \+ h& C1 R. v3 q# m  ~Disadvantages of Recursion5 y' J( B9 `; u

    + i$ u7 i. {9 @& ~; k* O" K" F+ 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.0 e( ?- c5 B$ P" K0 p2 E* w

    2 @6 }4 \8 D* M- |    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    8 a8 v( e' ~$ J; g. x* G* e) I6 Q6 J3 e1 ^# N1 i& z# V% |
    When to Use Recursion
    2 k0 t7 \% w; X$ t3 Y) d* A' P; m2 v  L1 k# i
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).  O3 @4 c  I7 Q( I8 b# k

    1 ^1 F  y3 g; a; }" M    Problems with a clear base case and recursive case.! o/ I( y+ J) |9 a  O; N; ]. m" w# k  X
    ' i+ Y# x: G9 Z+ |' G5 {  e  S
    Example: Fibonacci Sequence
    + a" G$ |* B3 d% {
    # c0 ?& s5 ~5 V! r" NThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:7 P2 @' [5 I. s4 O/ k7 _

    / A: y6 S6 x/ N2 y+ B" c    Base case: fib(0) = 0, fib(1) = 1
    6 g; j( K, d. w! \2 v0 b
    9 e" ]. b. Y' L+ _1 I; q    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    + V" f: l# K* ^$ \' F2 y; C' z2 z9 d/ R+ g9 t, E, ^; E
    python
    ' |7 b$ X( J6 ]9 }. ~1 S0 x! U
    1 R0 `8 |$ k5 ]
    9 @) \- X+ F2 {5 E/ S2 s- Gdef fibonacci(n):. O7 p% r; `" V- L
        # Base cases3 c& V5 o% z% P" Z- t, m; ^6 O
        if n == 0:
    ' F2 f6 [& }8 i* e% u        return 0! j$ D! M% R+ j  C& {
        elif n == 1:5 Z6 w% K- C9 C" ~
            return 1" w' E7 l' p9 ], x
        # Recursive case4 @; v3 u# ~2 L/ G7 J
        else:
    % e1 X5 b6 B- K1 \8 M4 j        return fibonacci(n - 1) + fibonacci(n - 2)
    , b! ^) {" m* x; B8 {1 |5 {/ D) M1 a5 ]" J3 n4 z6 @2 g# G, W
    # Example usage- q9 B; q3 N7 K% O. r1 o9 G9 [
    print(fibonacci(6))  # Output: 86 Q8 o8 N4 q8 n/ R! Y
    3 N2 n4 u! j% ]) A) P  u% w
    Tail Recursion: g/ G: n; R2 h. _& v( N
    - [0 A; ~- i- r2 m% q) f
    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).5 {: p, L4 k/ Y1 J4 q; i) V. I

    2 o1 T1 S7 s1 U( u- \5 E& Z3 W1 uIn 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-12-9 12:25 , Processed in 0.035561 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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