设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
      R' Y- U, B- R: ^' g& p2 Q6 [! M8 d# m! x$ Q* ]. y/ W' W
    解释的不错
    + q" W+ q( |) w. H. n6 w( G+ M% i1 s$ J0 a1 b8 a
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    3 T& k# y+ m8 V/ y( _+ \4 y+ s- r8 d
    " c1 O3 b  `' R( D6 e8 k: y 关键要素
    4 o, ?0 l3 q8 o! `: O% ?, _! d1. **基线条件(Base Case)**
    : t3 H3 `! i( H) w6 ?   - 递归终止的条件,防止无限循环1 J0 {# T7 B  n
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 10 p3 p6 T4 N  ?3 Q
    ) M4 W1 J( j6 L, d
    2. **递归条件(Recursive Case)**
    0 ~5 K- K' V# W. }* E# |   - 将原问题分解为更小的子问题
    & R( e2 l$ d% l3 G7 x   - 例如:n! = n × (n-1)!# ^! `% A  k, k( f) @

    & V. ~- v( Z" R# u0 S& I& V 经典示例:计算阶乘, Y6 j/ H1 e5 ?1 G2 J8 l% ]% Z
    python" d, W, I) f9 e
    def factorial(n):
    9 z5 j  x+ [; ~4 Q1 W- R& x/ A8 q    if n == 0:        # 基线条件& S4 N: ~, V: }- j- P  @9 Z& b
            return 1$ J) ^8 |6 ~5 D5 U' y$ `+ @
        else:             # 递归条件1 o0 B3 L) `( ?" F% o" d
            return n * factorial(n-1)- _$ V* @/ `4 L5 c, q( Q2 B
    执行过程(以计算 3! 为例):" f: l! z" K$ @9 g7 l; w/ ?- R
    factorial(3)
    6 m+ ?; q. @9 S) m3 * factorial(2)$ x. T4 u! s; j6 g" E' X
    3 * (2 * factorial(1))7 @& L  A- a+ @7 r( a
    3 * (2 * (1 * factorial(0)))3 B; B$ l" J1 l; {/ o/ X
    3 * (2 * (1 * 1)) = 6
    3 H# s) T+ X7 w+ {6 W* L& N1 U
    . {2 L' Y8 e4 F2 t 递归思维要点
    7 M1 ?+ ]7 m% G# H$ I5 n) D1. **信任递归**:假设子问题已经解决,专注当前层逻辑+ P  ?2 d4 x9 X0 G! d' V5 v. B
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    ; w( F) m* d: ]' j# s& q3. **递推过程**:不断向下分解问题(递)
    & }& M$ V0 x3 l+ V4. **回溯过程**:组合子问题结果返回(归)
    4 V( H/ K+ ~. H, l. [$ B+ T, W6 f/ u# ~. d- y* e' k. Q
    注意事项
    + q9 o9 {4 ?  z. r* `+ W2 Z, u1 z) ~/ q必须要有终止条件
    9 Y; E5 d! L8 L: B: T  t递归深度过大可能导致栈溢出(Python默认递归深度约1000层)! b4 n5 }+ p  K+ K" \! m# t: `
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    * [- G, \0 F1 v% @0 _尾递归优化可以提升效率(但Python不支持)
    ; I2 u# d; I" v( S) l' M! Z- H" E( R
    递归 vs 迭代/ K7 G. _4 s" W9 s& r- y
    |          | 递归                          | 迭代               |
    ) D7 [$ l9 I9 J3 T' U1 S$ H|----------|-----------------------------|------------------|, z' Q8 b% U6 Y8 a
    | 实现方式    | 函数自调用                        | 循环结构            |+ g2 `- e- j. [& h: M7 z" W
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ; g- o! d/ D/ x4 H: x- x" C| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    0 ]; ^. c" I  d, e| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    5 @' \( |0 y* `* u7 a! W! e* p) `, K$ }& e- _  C1 d) H6 C
    经典递归应用场景  B8 F* P: X& }7 s
    1. 文件系统遍历(目录树结构)
    ! i# r$ n' r- S- ?# s2. 快速排序/归并排序算法
    ! _* C: Y7 ?) [. x3 N3. 汉诺塔问题. z, {; U, q/ A& |$ n3 q
    4. 二叉树遍历(前序/中序/后序)' a- p9 t2 T& j; K- @6 O# L
    5. 生成所有可能的组合(回溯算法)
    $ C# d9 e! T$ K6 ]+ F
    % ]" f, Z3 d# L* _试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    1 小时前
  • 签到天数: 3226 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    0 \, p  z4 {( M8 K1 {) D6 }我推理机的核心算法应该是二叉树遍历的变种。
    ' E* V, Q8 P, C' c9 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:7 A) E* G9 _1 v4 m9 S
    Key Idea of Recursion" A' y- E9 w" ^8 X" B

    7 x) ~7 b3 _& A+ M: w+ }% aA recursive function solves a problem by:6 a) ^, F% ^, U( W

    / X; E7 O, {( x0 D3 J- I0 e! o2 V    Breaking the problem into smaller instances of the same problem.
    * x% p  p, W* e; K  G9 O' \6 G4 n! q& ?& U9 V& |' {, x- z8 J$ J
        Solving the smallest instance directly (base case).5 `$ |# T9 x0 M5 S" K; g

    # I7 h# g8 o4 S% S& Z% J" b    Combining the results of smaller instances to solve the larger problem.) o6 L% C3 K" e: J2 }. p; i; T

    . b& L. a# i9 a- EComponents of a Recursive Function
    - D. ]6 Y" @7 A% b2 ]
    4 Y9 M+ W6 c; R1 N2 ^5 z( c    Base Case:
    # H5 G8 f: Y( l. }) W: N9 ~4 O0 F* t4 o  c1 @: \4 [* E& `( |. X. M7 z
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.9 c1 @5 h0 r1 p% \: S
    - c8 O) x$ I0 I0 L( u: O0 x1 A! d# ^
            It acts as the stopping condition to prevent infinite recursion.- r  ^1 k) M; p8 T$ J

    & g, k5 Y! {* W! E$ y  `        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    3 P( n: ^% ]6 e3 K5 S5 z* P5 _% L. z; M; ?3 f
        Recursive Case:
    ( c3 r. M/ O( _+ s% A# O! _" C. K% h, M5 a) F' [4 L
            This is where the function calls itself with a smaller or simpler version of the problem.
    ! v, a4 o# t* U- k
    . g0 R6 }; v; Z0 S  c/ {8 x) e* ]8 C( X        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1)." B. J3 P2 r2 e+ H

    ; n4 I" J; f( |. b3 pExample: Factorial Calculation
    8 @3 W; ^! t1 c# O0 H& j& j9 M3 n( U2 y( W# p6 i4 h$ P5 d  c
    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:5 z  N, w1 [% @7 \
    # h& I* C4 @0 G& A+ }
        Base case: 0! = 1
    ! x4 ?' R, p7 u+ F& x) Z
    , ~' z0 @0 F5 z5 i    Recursive case: n! = n * (n-1)!
    + x: X! O3 D: `% ^
    ; l- H/ \5 \* s  `& uHere’s how it looks in code (Python):: u# c: i2 F0 P. B+ t
    python
    2 [; E& O+ i& H2 P* r& o# v, ]$ q5 c: W
    ( I" A: T" _! X" D. [1 O6 z" Q4 n& F
    def factorial(n):- c/ J' E' x" `) E: p
        # Base case
    - o' x) M% v% K4 S" k6 F3 O. U  ~/ y+ y    if n == 0:
    * _# A' h' d8 `0 x        return 1/ d& k3 `3 a. q" Z9 F: D6 K$ o
        # Recursive case
    1 r$ R- s0 \: H    else:' A# {5 Q/ f6 u2 C8 i
            return n * factorial(n - 1)- y4 ?1 e) F/ }9 P
    ) W7 N( e  i6 R6 R+ x0 y
    # Example usage
    2 [2 x4 c6 b  P$ @( eprint(factorial(5))  # Output: 120& x/ Q4 P  @' T2 R% S/ y" ]
    % d  H, R- I% q& g
    How Recursion Works
    + @) [9 @- i* y! O. d+ ~
    0 `  o. f( y7 x3 ^3 F6 [    The function keeps calling itself with smaller inputs until it reaches the base case.5 P* `$ z3 P/ B
    : V0 j0 z; ~& [0 y6 a
        Once the base case is reached, the function starts returning values back up the call stack.7 a. F2 d/ O, o" H" E

    9 Z) w5 T2 u" i% [    These returned values are combined to produce the final result.
    2 G  |) }, |" X4 Z& F6 o  V4 t( V! T! `8 X
    For factorial(5):
    7 f1 F: O0 m( A4 Q: O- x5 h0 `7 y" B* E" g

    8 A9 T5 ~7 N: @factorial(5) = 5 * factorial(4)5 f- u5 P, u7 [' f1 d
    factorial(4) = 4 * factorial(3)
    ) a6 n1 _. [9 O% k2 J; l9 }1 d; d& P4 qfactorial(3) = 3 * factorial(2)
    ; _' \8 x# H3 Z. O2 Y7 I' Mfactorial(2) = 2 * factorial(1)
    8 d+ s8 ~1 V7 }* U( R: K7 ifactorial(1) = 1 * factorial(0)+ D( R' Y& i8 Q9 M
    factorial(0) = 1  # Base case" P8 t3 Q! k) G- S
    & r% D6 R+ d* I( Y. `0 H1 I* S5 b, O
    Then, the results are combined:, x$ C: V5 h  F; r

    , U2 B) L% l6 P
    " {3 M6 N( }+ t$ o) @+ i' Z. v  yfactorial(1) = 1 * 1 = 13 r* q) ~0 O2 s$ E( t
    factorial(2) = 2 * 1 = 2
    . N# l. k4 ?. c( o3 vfactorial(3) = 3 * 2 = 6* E1 X- }, T3 x) ]
    factorial(4) = 4 * 6 = 24. {0 u# K1 s& U/ P
    factorial(5) = 5 * 24 = 120$ F1 q* @3 I# k: `0 r( z
    6 \0 X9 l7 L$ H  w3 ?
    Advantages of Recursion# \6 Y  t$ G2 i* ]6 j2 B. f

    7 w* }" o! p' i, e- Y    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).) U+ S1 H. ]" u# r2 W: j* V, E% }
    # @( p" D. Q' E, P; U; x+ A$ V
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    3 _& b: Y# m; m* Q8 m/ e) D1 b6 ~7 a* u, v* X
    Disadvantages of Recursion. ~3 r4 ~* w1 _& b& j0 A; z
    % @6 C  F- l" ?, u5 {
        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.- l! w1 s" P0 \. L

    + s, U2 [, L; G1 }7 {  z- t$ A; @    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ! X# Z& V$ D+ \0 u, R- X+ s3 K" K. C1 ^$ u6 t7 W0 D4 W
    When to Use Recursion  G6 ]" `4 s7 V0 B

    9 ?( x- O9 U. y7 b4 j    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    " Z! N7 {/ i% w# L) z, H
    * G# y2 M9 S4 ~    Problems with a clear base case and recursive case.
    ( ~( `3 G. t6 c; G# T8 H. I; C6 P% P  L' |& e% t1 }. k
    Example: Fibonacci Sequence9 I& J6 J4 e" V' ^
    ) @* I7 q, E# f. n, r# G' m
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    + u9 A0 @& \9 V- E+ a1 D
    1 L, H* A  G; [7 I6 V8 t( i    Base case: fib(0) = 0, fib(1) = 1
    9 N2 l$ T0 k- \# P& }# T4 c0 K# }- k) x" p6 L8 r
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    * \/ b$ M; N. f) l. x. G4 G# o8 l  p, c/ N
    python
    , Z7 C  i9 z; [7 _/ g3 m$ a
    ! r5 Q  u' E: U% j1 _2 V5 D: T
    - B, y5 M3 l: a- r% G* Ndef fibonacci(n):' c; ?# n4 _+ e. T5 |  b
        # Base cases& d' i; @, o4 [
        if n == 0:
    9 O% j1 e( _# _7 y3 G7 y        return 0
    . z$ W0 \  X# l' _% B    elif n == 1:
    + H: K8 ?7 ?# U2 W* V9 e+ _        return 1* X# ]% w" K3 {
        # Recursive case/ j7 q, \; u: U8 Q6 g& A, W
        else:
    ) ~2 y- F2 Z' ?  U: @        return fibonacci(n - 1) + fibonacci(n - 2)
    / Z. a# _5 x  c/ p
    , v# G) L! w3 x. R; Y3 O- ?, l# Example usage
    $ U- H4 U1 Z  u  ~. oprint(fibonacci(6))  # Output: 8# r$ m# d- ~8 X
      O' s4 ]  z9 u1 n- U. [
    Tail Recursion
    # K3 S9 L7 Y+ x6 P. j, I2 g3 v8 |. k
    9 r, `, r6 R* J" STail 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).
    * B( e; v. Z5 V4 W$ ?7 r1 j
    1 z9 o- t, G- l1 GIn 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-29 15:44 , Processed in 0.060488 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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