设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 3 m4 n  I- `3 `, x) r: x' a( L" ^
    0 r$ b- W2 r; u) }% A+ a9 z
    解释的不错
    & [  r, f4 v- [% w& h" z) D! U: M6 Z
    , {# V( T" T% q5 i9 r. D3 a! N递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。" V+ @+ g* T8 A6 Z" K2 X2 N
    0 Y5 E* w9 C1 u# w* w
    关键要素- h/ P! X: Q9 t7 @5 r
    1. **基线条件(Base Case)**
    ; `% S1 b* t& W& q  e$ _8 [% w   - 递归终止的条件,防止无限循环( E8 `/ T4 e* Y4 P5 f0 l
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 13 U' ^# i- f1 i; o4 M
    3 j6 ]6 f* q4 g) O0 P. l' k" b
    2. **递归条件(Recursive Case)**
    3 U) O5 g  [4 z- R" ~9 a1 r   - 将原问题分解为更小的子问题' y% @  m; }7 j* B% D
       - 例如:n! = n × (n-1)!
    7 ^4 M, U' m+ \/ c) z& r
    4 S& G  w5 I7 Q  Y) S 经典示例:计算阶乘# L* R% y7 U0 I6 t0 {
    python* U; i4 {2 C  L' N
    def factorial(n):) r7 ~) i" N6 ]7 j
        if n == 0:        # 基线条件
    ; S* S0 P& t! ?4 H        return 1
    . b* @, D. Z1 a) X( T( w3 t- m    else:             # 递归条件6 [8 `7 Z# E* Y. d% Y+ A
            return n * factorial(n-1)
    ' m" o2 u4 p2 h/ }执行过程(以计算 3! 为例):3 X2 ^8 k' Y+ j9 y. Z6 V& f4 O! ]; U6 R
    factorial(3)
    / i0 s7 Z% S9 h4 d3 * factorial(2)
    2 Y# L1 F9 r8 v  n) P( G' F3 * (2 * factorial(1))/ h# P" b- G, a9 M) Q* @( [7 ?
    3 * (2 * (1 * factorial(0)))* s: g8 x6 S, ^8 T
    3 * (2 * (1 * 1)) = 6. h  E1 G) `8 W( f; W; X* S
    2 ?0 ?$ L2 ^$ n6 {) J; {2 A5 k
    递归思维要点
    ) q  b/ L( f1 O9 V5 Z# s1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ' v1 M7 ^4 O3 K! p6 d% b2. **栈结构**:每次调用都会创建新的栈帧(内存空间): m& }+ _% D% [
    3. **递推过程**:不断向下分解问题(递)% f8 L* k' i, V  v+ j5 V/ q
    4. **回溯过程**:组合子问题结果返回(归)
    : b! B% c% @- y) u$ M9 c0 g9 z/ ^+ {; G- b
    注意事项  L3 u" G: \4 z/ G
    必须要有终止条件% _9 G6 v8 j, W' b
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)1 u0 T/ h4 B  m9 D8 r
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    1 i! R8 ]8 X* q6 T+ F  h尾递归优化可以提升效率(但Python不支持)9 h7 _2 i& [+ w3 D) O# \

    * K; n. G0 O. ]2 m' O3 Q& S5 y 递归 vs 迭代
    5 \- J! B8 M1 |' G% j7 Z: W|          | 递归                          | 迭代               |
    9 [% H$ n2 m% \. d) S5 p|----------|-----------------------------|------------------|
    3 s  Q3 K4 T. F9 r7 G9 f/ {| 实现方式    | 函数自调用                        | 循环结构            |1 d. w% `+ [0 D* r# t' G2 D
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    2 s# m" e# \4 F! d| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    . V* Y' @: u! o" E| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    / [+ j" R' {) e  j/ Q8 W+ R' l4 r8 s+ Q, N  Q* }2 Q; r
    经典递归应用场景
    3 w7 Y! _7 W6 w$ ]# ~2 `  C1. 文件系统遍历(目录树结构)% _, K; ~* e$ X
    2. 快速排序/归并排序算法& \6 A" O  N( a! {2 `) E1 T1 w
    3. 汉诺塔问题' `8 `, E  m9 m
    4. 二叉树遍历(前序/中序/后序)% N- ~/ x. P" c6 j3 Q
    5. 生成所有可能的组合(回溯算法)
    + \/ q/ r" `3 D. P3 C8 i4 |: T2 b5 d; C6 V& ^& M
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    前天 08:28
  • 签到天数: 3123 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    7 M$ I4 A* ^! v2 H" c8 o我推理机的核心算法应该是二叉树遍历的变种。1 ]" P" q- t( t  ]3 y8 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:
    ; l- h' K! [3 y1 R. G! c% j. R/ sKey Idea of Recursion. V6 B, f# D$ y3 u, N* ?

    9 ~7 g0 j# J. ^6 w. A4 {A recursive function solves a problem by:
    ) k, Y9 H. [  Q# S$ W  \/ B9 ?6 _# ~3 X# T& W# p- f0 C
        Breaking the problem into smaller instances of the same problem.0 x2 y" ^; Q5 A* S  L4 a( |

    % n* E+ J; p3 O* V    Solving the smallest instance directly (base case).0 d8 d" b7 L! ^$ e6 }

    " P; |1 p# r$ G  N    Combining the results of smaller instances to solve the larger problem.
    ( b+ ]8 u# e( S8 Q( p0 V
    - O) [6 U" b4 _6 kComponents of a Recursive Function
    # a( o- }* T& G4 Y, ?  K6 X/ v7 n7 I
    8 k  l7 Y. v) E  X. D    Base Case:
      z! @" u# P( x! D% b7 u/ t# A" k5 ?8 E0 ]& ^) Z. r/ O$ Z
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion." X% q' D/ ?, w; K* @
    2 ?" g* m; Q& s9 ]
            It acts as the stopping condition to prevent infinite recursion.1 T7 t7 @; X) u/ ?% U

    # f+ U* m, Q% x        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    - `: x7 t( y8 ]2 D" Z( I
    ' [; T* y/ D* Q* q" j( V# p  X    Recursive Case:
    2 `, W& O  C; J) k
    , A; [/ V& s3 M' W! {' B5 Z! z        This is where the function calls itself with a smaller or simpler version of the problem.
    - R  R2 y4 E) Q; t% E* R  u
    : g* B- H; p6 r$ S& i( v) i        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    / w6 |) S4 B* x# ?% q! U, L0 R' ~5 @: D" g
    Example: Factorial Calculation' P0 y' B$ r4 c' M) ~% j+ C
    3 I& H" j% U& w- f
    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:& j- ?$ p; P0 R1 ?" o5 J9 r7 x/ I
      _$ Q6 Q* P' f9 h* @7 J
        Base case: 0! = 1
    % ^2 f' k8 I: o0 W5 C5 S
    5 U4 z* C4 l3 F/ B, G    Recursive case: n! = n * (n-1)!6 E2 a- ~3 F% V, k; ]  h. J

    4 H* `0 D% a: t  G2 ]Here’s how it looks in code (Python):# y3 V0 |  v; z% n& `
    python
    6 e- G) H% `$ X% E3 U+ h# Z( f4 g+ x& Z. Q- y1 A

    0 S1 {7 K1 s( ]. h2 h" odef factorial(n):
    % _5 p, F5 I; @+ r3 D    # Base case
    , v7 U% ]. U" g4 ?1 H    if n == 0:
      L- U( d; F; r% ?        return 11 v5 D. F( `5 Z  i4 Y
        # Recursive case
    9 F( Q: p, _( z0 I! j6 b& j    else:: N( i/ Z3 n* w2 y# h
            return n * factorial(n - 1)+ v" E; M+ i3 l. V6 K
    % }0 g% V1 E! X
    # Example usage
    1 @3 k, Y& R; n- Iprint(factorial(5))  # Output: 120
    * o: x3 x5 M* h: G5 `, D' H
    % Q! F7 W8 u; R$ p( n* W9 v4 }: FHow Recursion Works
    6 t8 s0 q" z# K2 g3 h( i
    0 B( x& m5 q. m! }    The function keeps calling itself with smaller inputs until it reaches the base case.
      ]# Y6 k& K7 W$ {# ^1 R9 u. h4 i% F) O- x
        Once the base case is reached, the function starts returning values back up the call stack.
    / u7 X8 c; m" w& O
    . N: A+ e$ u! ^: s: y: T: X( w    These returned values are combined to produce the final result.
    ) f+ S& K6 ~( R2 l% D$ l3 G/ N# y8 c( k# _
    For factorial(5):
    # n. k" I% z( b, i7 w! X! F7 m; x+ ^7 L: ?3 h* w# ]
    % Q- z. H/ m, T. |
    factorial(5) = 5 * factorial(4)
    ! `! }$ w, m; D4 |9 Efactorial(4) = 4 * factorial(3)
    5 T* _/ x, m6 W/ K, T5 ]9 rfactorial(3) = 3 * factorial(2)
    # [: ?5 n' c2 \. r1 q# h0 @factorial(2) = 2 * factorial(1); q, D" o+ r- t
    factorial(1) = 1 * factorial(0)8 z: ^& C( a% M: G' V* [
    factorial(0) = 1  # Base case$ I0 {  S  q  E  e, ?0 L( H

    ' Q$ ?5 _5 u) XThen, the results are combined:
    1 ~  ?; s2 _8 W5 b1 m0 z+ l# v! t$ {6 C- N7 _7 Y, U8 _4 M3 G$ |" c

    # R; o" ^  V/ t. k6 Ifactorial(1) = 1 * 1 = 13 t2 P5 @% o& c/ F; n' [5 ~2 H: R
    factorial(2) = 2 * 1 = 2, `* }! k5 E0 G) B# j% H
    factorial(3) = 3 * 2 = 6) [' C+ M5 p: {  R
    factorial(4) = 4 * 6 = 24
    ' ^- ~) S! K7 @' Z8 x0 Sfactorial(5) = 5 * 24 = 1202 W" x9 M0 M4 h, t
    1 t7 M. l8 J6 J* c3 u
    Advantages of Recursion: F" |; ^0 g3 h  S6 L
    - ^4 n3 K+ F4 ^3 f
        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).8 a. q; l( _/ i% O/ ]

    # S) \! O3 d& y+ z' e/ L    Readability: Recursive code can be more readable and concise compared to iterative solutions.: P; L2 T( S. ], T

    # \- ]+ {" h4 ?, H: _- q( S5 ~* |8 N! BDisadvantages of Recursion
    ) |+ Z; }7 M4 K+ n: V2 W1 T3 i
    ( Y; A# I; G9 _/ k" t& k    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.
    8 Q  I3 B4 x+ O1 O! T! `5 n& Z% Y. f0 K( f! M( i' |
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).* w3 [, T( H) H' c
    0 j- i  l9 r- N* u- \5 ~
    When to Use Recursion
    4 \& A& w0 D: T9 @5 J. q7 _* L; u' G+ f0 o
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ! D( b  n' p; I6 @% R, u; M
    $ R( s# k7 N9 z8 F  h: k" Y3 F, {    Problems with a clear base case and recursive case.
    : n+ J# v& ?, r5 X9 O! V2 I$ f' M/ T1 o# V) }# @- f
    Example: Fibonacci Sequence3 g% |% q: j. J" b) f& F. z

    $ t1 t  @' e+ ?The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:# l$ b3 r* |8 _4 X
    ( m  ?, l9 e$ K2 S5 D, t2 O* Y
        Base case: fib(0) = 0, fib(1) = 1
    / m- l  @+ q* C6 v! ]8 K  w0 i& M; u* Z" x7 @: c4 U0 F
        Recursive case: fib(n) = fib(n-1) + fib(n-2)1 M* Z" [/ s  w) _1 }
    ) g3 T) I  \- S& [
    python6 \& U* |8 ^' d: M, L
    " C, V. u" u7 g5 B$ }# m
    . {3 _. t& r4 J0 f7 I5 _
    def fibonacci(n):0 a. C2 Q( d  @* S6 U' i, T, c
        # Base cases# p5 H0 R6 d" y) u$ R
        if n == 0:
    + o+ a1 j4 V  R. ]3 _7 \        return 01 ?* k* }! I# `0 F7 P5 U0 [
        elif n == 1:2 J+ Y4 r' b( ~" G, @
            return 1
    2 d5 U7 `+ j0 B# A! r/ f1 t    # Recursive case1 Y+ |- }; U* i$ @
        else:/ c$ D) _& k0 Z: T8 J
            return fibonacci(n - 1) + fibonacci(n - 2)
      K8 k- d# l, Q, H3 Y. \4 k( b7 L& M: _( ^
    # Example usage
    % C* m) D) `( V; @/ uprint(fibonacci(6))  # Output: 8
    5 t/ ^) P/ P) K0 ?8 q) q
    * I# R6 m- ~6 q9 W+ sTail Recursion
    ( u5 a+ G* o. u1 Z% p% F5 H' \. a- _+ W( {
    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).2 L6 w/ ]0 U5 ~$ e

    / R5 ]; V+ X. Z' IIn 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-22 07:38 , Processed in 0.031981 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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