设为首页收藏本站

爱吱声

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

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

[复制链接]
  • TA的每日心情
    开心
    2015-11-30 11:11
  • 签到天数: 2 天

    [LV.1]炼气

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    0 p2 s: Q# C9 L+ r1 D6 }0 n# @
    % @+ ?  Z6 B; C7 h2 a6 H解释的不错
    / G1 \' }+ `) g( I1 T2 z- m3 ^5 K! U. }. l! t) X* g
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。/ i0 m' }" h: `* V6 O5 q) D
    ) v' r; W. b# u+ I
    关键要素
    : _& D6 K9 N$ |# z4 u; S1. **基线条件(Base Case)**
    6 b' V% j) ?: u# z. q1 R0 t) ?   - 递归终止的条件,防止无限循环1 S) ]5 T+ S+ t
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    : \. Z" Z, `1 f9 i8 R, j* V& O: d; z% Q0 W& N
    2. **递归条件(Recursive Case)**: g2 [& {6 O3 d
       - 将原问题分解为更小的子问题
    0 B' v  ]  S) ^/ a+ y9 ?9 N   - 例如:n! = n × (n-1)!
    # s7 `+ C0 A/ V8 i$ h( X, v+ j+ C1 l( d' r# o; g
    经典示例:计算阶乘* a  Q4 b7 W9 c4 N7 o
    python! u6 f+ F$ [) r6 j
    def factorial(n):
    ! P* I& T: c" h& b    if n == 0:        # 基线条件
    ( L& R, w- `' H1 M9 t. D" O$ ^        return 1* J8 M/ m- H6 x; H3 V2 m- ]% V
        else:             # 递归条件
    . n- V% A; T6 y7 A( q5 x        return n * factorial(n-1)# ?/ y  c6 e' G) L& `' {1 P1 t
    执行过程(以计算 3! 为例):3 X& E# m" I* x* l7 e* ^
    factorial(3)2 x- F; f3 _4 K/ K% }
    3 * factorial(2)
    9 Q$ L: o% }4 `5 X# l3 ~* F3 * (2 * factorial(1))
    : r# S* H& e7 q3 * (2 * (1 * factorial(0)))% a( j4 [% y& j, L% P$ Y& p
    3 * (2 * (1 * 1)) = 6& y  J/ O1 F" P+ h, O' a1 l
    8 J+ ~% A, o+ P. r  c8 ~0 V
    递归思维要点6 `9 L! P. Y8 \3 U
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    - ?" S1 A5 K! J" S; [; o6 K1 u2. **栈结构**:每次调用都会创建新的栈帧(内存空间)3 \  H# M2 K/ H% q& ], T/ n- b
    3. **递推过程**:不断向下分解问题(递)0 w* H/ @# @3 f3 ]
    4. **回溯过程**:组合子问题结果返回(归)' A. T+ {/ c) U' ~

    2 m$ B; n# N4 k 注意事项" Y9 V, Q( b$ p8 ]* y" ~& n
    必须要有终止条件
    - L! l* y5 V( `0 R9 E: [递归深度过大可能导致栈溢出(Python默认递归深度约1000层). V5 m7 q* w: T5 C) u4 X, V+ m
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    ; M2 Z1 R7 K  A- ~8 @8 @尾递归优化可以提升效率(但Python不支持)
    ! p5 A  {! P. T$ h4 S; A
    . T9 ~- X/ E8 O 递归 vs 迭代8 `1 r& g; ^7 R! y' D/ c
    |          | 递归                          | 迭代               |
    + B& ]! z, l5 \. g% V|----------|-----------------------------|------------------|
    & j; t7 Y; }8 I- ~$ z. N4 || 实现方式    | 函数自调用                        | 循环结构            |( n7 E( U; W7 |; {, \* o
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |/ F7 l+ J) X! U& K8 @/ W( I- W* w
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    * M# T# K1 F% ]7 C: A| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |" b9 v. l) V5 i  ?7 N8 Y- _

    ; F, [  J% w0 Y 经典递归应用场景6 J, t+ b& c! \2 A! C# }4 k& {
    1. 文件系统遍历(目录树结构)
    # ?5 X7 N% R& Q  Q: h. q2. 快速排序/归并排序算法- X6 m6 M6 ?; {* V) \! S9 h8 Q( l
    3. 汉诺塔问题
    ' j% H" M* J0 t8 f8 T* w+ g4. 二叉树遍历(前序/中序/后序)
    8 f1 q$ M' Q7 {5. 生成所有可能的组合(回溯算法)
      \/ c2 Z1 H, c! n; U9 u% c: v3 _$ w  z9 z6 n
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    开心
    昨天 04:10
  • 签到天数: 2877 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    1 g" k5 J+ S9 l7 z' m# A" G我推理机的核心算法应该是二叉树遍历的变种。) j" w- P2 n4 C9 V
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:9 g4 S' [; ]# C# X( G1 E! L4 i2 x* N
    Key Idea of Recursion
    ' l. s4 a% s  I% A$ a9 z2 Q! v: s- u! v! K( v9 X( W' h. G# q
    A recursive function solves a problem by:0 T" h' Z( S0 Y1 ?. X

    ( Q* }9 c) K6 B- H( [- w+ T7 U. f    Breaking the problem into smaller instances of the same problem.
    3 ]% d- J# T- i- `! D5 [# @+ r4 p+ U& k/ X6 i" f6 R2 b) h
        Solving the smallest instance directly (base case).
    ( `  F# H' s, G& L" q) I
    9 y  Z3 P2 b9 B$ J8 d    Combining the results of smaller instances to solve the larger problem.% ?& N5 Q: Z- Y

    8 l, E, t+ j' v8 mComponents of a Recursive Function
    * m) e  F  U6 b
    ( l) o# {$ }/ G5 ~; ?* ^    Base Case:
    # k% ^, ^$ r. a: ?) H; y' Y
    $ X4 P8 u% R, T: D! U2 P        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.: L  ~5 @0 M2 c' ^7 u% [* y3 n

    ) k+ Z, l; x9 [4 u0 \+ a; a        It acts as the stopping condition to prevent infinite recursion.7 u% L6 P5 d8 S4 R9 F1 O% m
    , {, ^$ L1 s5 a/ l3 [5 S* b
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.6 ^: @! l& z* ]5 i# o, W& d
    4 `; R8 W( D! v2 |
        Recursive Case:2 J% o7 l: \" a6 p1 G7 q: f

    / k% h! R1 m- Z( A  k+ O' e) h4 V        This is where the function calls itself with a smaller or simpler version of the problem.
      a8 }+ C7 S( H+ {& e: K1 Q) a3 @$ t& n# i- z
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    3 J' |  Q& E5 \1 w  Y( `( a9 E! j6 k. M
    Example: Factorial Calculation
    " [+ G$ \. Y7 m* A7 |0 e5 Y" \( K0 `% J! y0 [; j/ }2 P6 T0 ?
    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:- U1 N; P( r; `: i/ z4 A

    5 F) t, }" K0 m+ G" G) }$ t; |    Base case: 0! = 1
    : i2 p' C3 _% D) g; `* B; G# g7 o+ [9 ~
        Recursive case: n! = n * (n-1)!) [4 q- h, a0 n/ p( n
    + f! ]( d2 ]2 P7 l0 J! K/ A. F
    Here’s how it looks in code (Python):% b  C6 {: z0 s* _6 s. H
    python
    $ R+ M6 J' v( S) {. Q6 v- X$ S8 r  j4 C: D: O
    / s& F9 A- c8 d8 s% ]" v+ Z
    def factorial(n):
    3 u1 P3 S! J% G) W7 K/ X    # Base case
    + \" F2 ?8 {% h+ q3 ]  `- C* c    if n == 0:0 ]1 V+ ?% }& y* K& O# v2 b1 @
            return 1% w& Y' {% g2 v
        # Recursive case
    9 v; w, q) U) B8 w& X    else:: |8 i0 z  T2 G7 H8 z
            return n * factorial(n - 1)
    " h  g0 |( B# C  J, u. I" r( k4 B/ C4 `% o5 r- ]; {
    # Example usage6 s* t2 `0 Y1 Y/ u+ Y2 `
    print(factorial(5))  # Output: 1207 R% `0 x! g5 A/ c+ D1 R
      l, ?0 B& ?9 n* L9 K* U
    How Recursion Works4 o$ i- K% g, Y# u

    2 ~/ f' s* o/ _. }9 W3 a: {  i9 ]) d    The function keeps calling itself with smaller inputs until it reaches the base case.
    + U: u9 W% b/ g, f0 a  V* E; i! {; T$ b2 K+ e$ ~$ Z, T/ y
        Once the base case is reached, the function starts returning values back up the call stack./ W4 {3 ^/ F9 ~3 M2 s( A) G9 D6 d
    3 Q2 s$ Y4 p! A  i2 L+ a. W. h
        These returned values are combined to produce the final result.4 L( O' E+ r* |6 f- T% P

    4 \! T  Q" K; C; ]For factorial(5):6 _' y! [. w. i- q

    ) [7 v( \5 {: c3 w
    ! M6 v! ?, S- c+ C( D4 qfactorial(5) = 5 * factorial(4)5 `* x9 u9 H4 t: h( T4 l9 a' A( H4 u  h
    factorial(4) = 4 * factorial(3)
    , ~" I2 l2 Q2 c* ^factorial(3) = 3 * factorial(2)" j) ^6 i0 X& J* f7 _1 I. U
    factorial(2) = 2 * factorial(1). i' o2 Z% G; |0 a  M: J  Y  W
    factorial(1) = 1 * factorial(0), }  K1 H" n) S; i! j4 k! R
    factorial(0) = 1  # Base case
    8 }! @% W; P5 B; ?* ]( p& {3 r
    / H+ u; b, ~0 Y1 [6 V2 r( mThen, the results are combined:- ~8 S; }8 h1 z

    , v6 d' ~& m6 Y; ~7 u/ U; e
    / H% v% ^: u- |3 M% Y8 @factorial(1) = 1 * 1 = 1' H# y% F* C- }1 o. Y1 `
    factorial(2) = 2 * 1 = 2
    , f+ W1 c# Q- g! i' N; ~: Ifactorial(3) = 3 * 2 = 6
    # U5 Y. e- L( u1 j+ h. c/ zfactorial(4) = 4 * 6 = 24
    : W: ~( W% b$ Z% sfactorial(5) = 5 * 24 = 120
    ( M3 A9 e+ H2 I& v% Z
      v" j* L1 U# B  T: \Advantages of Recursion) K0 \/ B7 W1 f# |8 v

    ; U: Q6 R, g1 k6 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).
    0 m9 d0 ]) V2 x3 L' ?
    9 M* ]. |7 ]+ h1 m+ q" ~( q! h+ j    Readability: Recursive code can be more readable and concise compared to iterative solutions., d( B/ o3 i/ V
    # T; Y2 H& s4 j+ f8 X
    Disadvantages of Recursion
    7 s$ D! t5 \9 w/ k( B4 C6 K, h
    5 a8 d  ]( ~6 B. b1 z+ P6 q8 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.
    7 H& Q& G3 c: [/ U% W! h8 A. \/ \, \
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    & M! g4 B# w2 I1 y& `
    ! \$ Y( T: a# l, b- w$ z2 LWhen to Use Recursion' U: K# }! r- z7 T

    4 |4 a4 t3 H4 m* A0 Q    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ' }; I/ n3 f7 D( w: q: ^) r9 _1 W2 O3 |1 p
        Problems with a clear base case and recursive case.
    , N+ S7 w/ S/ c* {" g0 i  A
    1 X7 S% C$ N$ c* T! QExample: Fibonacci Sequence! v; ?; i: Z+ x8 x; m# \
    $ s  Z" H9 c! N! T" v' c
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    : F9 Y! ]% z- S9 [, a: m0 m( Z6 l0 S" M. l/ k% [6 P
        Base case: fib(0) = 0, fib(1) = 1$ w8 Z! o) \/ S; S. ^( u

    $ O5 m) m4 t5 X% b    Recursive case: fib(n) = fib(n-1) + fib(n-2)  c0 E. o* O/ _1 \7 D
    9 `, r6 I5 g  h0 |/ {
    python3 K/ n6 V" W2 `5 C; ~
    ! |2 |+ S* v4 G+ E5 g4 H) R- E+ k
    2 ]  P8 y( y; d- J) m
    def fibonacci(n):
    1 Z) R5 b2 Q+ }9 m, P, p. x, N1 ]    # Base cases( r, j1 [  w; ?. Z* J
        if n == 0:' Q6 F. y) t$ [+ _0 k
            return 0- J, G) j5 P, A- H! R
        elif n == 1:3 r: P& G. U( c2 B
            return 1
    " _( s' W: N0 m6 X; F    # Recursive case
    2 [6 K3 U9 R! u8 o  W' F' z    else:
    8 n+ f; E) P8 r0 S0 ^; }  M) }: `7 |        return fibonacci(n - 1) + fibonacci(n - 2)- w8 n- y0 B1 K  ], f+ J! P4 D

    9 U" g( i+ V) c0 I8 L; T# Example usage
    8 N  ?0 s7 l3 ?( D) Y' f. Tprint(fibonacci(6))  # Output: 8# s0 d" ~! f9 Z2 r' i0 Q
    1 {1 m: V5 C$ T$ i! x7 }- g9 U
    Tail Recursion
    ! x' o/ t% i( J' s, B
    2 x) |; f6 n: D, E% Z( p; d/ B) ETail 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).( i( V% P, |% i

    , B: j8 _  h* }" g2 e( w7 XIn 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-4-1 00:57 , Processed in 0.035207 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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