设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    + p4 v; t# j4 V7 N! W
    7 H/ m/ p  _3 {  y解释的不错8 X+ U8 F3 O! u  L8 G

    2 z% E5 Y. d/ u& v3 c, K) L6 N递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。  b, T* V5 _  C1 k( F
    8 U5 o# g7 l, e) R1 x
    关键要素2 D! |! L/ G7 c" ]
    1. **基线条件(Base Case)**; b! n' B8 e8 u% q" ?# \
       - 递归终止的条件,防止无限循环$ M0 z' h: r0 J
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 11 e1 @7 M/ P& x% P! g7 V

    7 M4 \9 l; l% ^2. **递归条件(Recursive Case)**9 P- n% _+ u0 r% S$ _8 e
       - 将原问题分解为更小的子问题
    7 q6 u. y0 i8 |( n9 `   - 例如:n! = n × (n-1)!
    / m& U8 g* X4 ]
    4 Z3 t/ u3 ~2 {% D! l6 _  _ 经典示例:计算阶乘
      Z  y' `7 P3 \% R. A5 P3 _9 Y' Bpython
    3 c' H* s; n$ {, m0 Y* X# @def factorial(n):
      k  Q+ l" e5 S+ J2 d: R8 Z    if n == 0:        # 基线条件3 Y5 _7 a/ |2 y$ I. m/ L! O7 _# B0 N
            return 1
    $ ?( j( {  E" [, w    else:             # 递归条件; T5 ^" X( q% F$ R) T
            return n * factorial(n-1)
    ! R8 Z) S& M% m' Y执行过程(以计算 3! 为例):. H, S5 K# W, v
    factorial(3)
    ! Q8 O5 G) A; @( D! _3 * factorial(2)+ t: d5 Y# ~3 N6 A" Y, K: U, h
    3 * (2 * factorial(1))
    0 r  {. H) K  o3 * (2 * (1 * factorial(0)))
    . w9 z8 E- J8 S3 * (2 * (1 * 1)) = 6
    9 C( R! v1 g8 b% ^: @5 G  Q- @8 j0 R' c6 r* C
    递归思维要点1 ~# J: ?- u" N( [7 g- U: M
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    0 W. r  C! V7 O6 O2. **栈结构**:每次调用都会创建新的栈帧(内存空间). b! u1 N; r6 p6 @
    3. **递推过程**:不断向下分解问题(递)6 F& p! w; w; G$ ?4 t  L4 j( r
    4. **回溯过程**:组合子问题结果返回(归)
    & ~, i! v5 S4 {9 b4 I: a8 w- K- u& b% H( m8 o. ?' G3 r
    注意事项. \( M4 a6 |+ `# f8 s% o& k6 R+ }
    必须要有终止条件$ J0 ~5 i0 E& y8 {% m7 [4 R" U
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层), @& y2 O8 S: L6 I; U; I# ?
    某些问题用递归更直观(如树遍历),但效率可能不如迭代. A) ~- I* @/ ]) v- G7 D; A7 v" J
    尾递归优化可以提升效率(但Python不支持)
    ! j+ W$ d' E4 z5 Q  P3 R" D* ]& u, [( P$ w% v& [
    递归 vs 迭代5 m0 j- s/ C+ ^" I0 w/ u" W6 \
    |          | 递归                          | 迭代               |
    ; E  e$ i6 l" Q* L2 n/ Y" D|----------|-----------------------------|------------------|
    . K; {* S$ s6 j& v) ~  B8 o| 实现方式    | 函数自调用                        | 循环结构            |
    8 e+ b- K# q/ T$ q. q' Q: L7 o" i| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ! J8 y) H2 v: U2 R| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |! Y$ d$ _$ g6 b; D3 F0 b; C5 m8 ^* W
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    & p# G5 z. x2 N7 @) P6 E$ ~; L8 Z* D! P, `6 P* x0 z" R# T; f" |
    经典递归应用场景- {( m6 y: X$ s; _4 M& K5 Q0 D
    1. 文件系统遍历(目录树结构)
    $ j( h: {7 v3 ~8 K2. 快速排序/归并排序算法' O8 _+ r& {, z5 l
    3. 汉诺塔问题
    ! r: a) C& l- [# `6 d* M: F4. 二叉树遍历(前序/中序/后序)
    ' H3 A: l9 k* t. N6 z5. 生成所有可能的组合(回溯算法)
    3 {3 ?( S' Y/ c9 j/ p1 j; g9 K, w" q! R7 k- ]* {
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    开心
    昨天 07:38
  • 签到天数: 3159 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,. ~6 {8 r/ @. i5 I% J: Q7 @
    我推理机的核心算法应该是二叉树遍历的变种。. L( O9 r# H5 \7 F# O8 O
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    " }0 Z/ c9 _% |0 N$ lKey Idea of Recursion
    1 T* U' q( m& K5 u
      j; l0 {6 n  J7 Y  w. N- a. o% W: XA recursive function solves a problem by:* L# B$ W$ E) S) P: s' |1 L

    / h( x7 D; t3 g1 o$ x! ~' b, o    Breaking the problem into smaller instances of the same problem.
    % l% \5 l# q7 M; _
    0 T& P% l; N3 i5 V    Solving the smallest instance directly (base case).& W) r) Z& e* J3 V( H+ F( N

    * e0 S$ r1 g" C    Combining the results of smaller instances to solve the larger problem.
    - |: b# r- X: ]/ _
    ! [) X5 G/ U/ K0 Z. m$ DComponents of a Recursive Function) t" Q5 Z8 h/ I) }& N% M: P
    / E3 `% w7 D0 n% p  H; R/ G
        Base Case:$ o. n) N: ~% q% q: q0 j

    ! M- Q0 D6 y1 D. Y, l        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
      E" D6 G- l+ O. G3 B* ^
    ! U, @  ^0 r+ H# d        It acts as the stopping condition to prevent infinite recursion.3 W1 I# P* @. X4 I
    " H' f; [" W! k3 m4 B
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    + c& B2 u2 z' U' ?$ W
    5 W: G; ?6 c; P' d1 N1 R1 a' F1 y* W    Recursive Case:
    2 }! O. A0 H* ]# I6 ]0 U6 \1 K
    9 k6 E' Q# F# R9 \9 ]        This is where the function calls itself with a smaller or simpler version of the problem.. G. s( g+ Y% Z( l5 x) T
    $ ]3 z5 V9 |# \& ]
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).* k! ~3 E( L! Z: N  ^) g& I
    2 \0 L1 @4 s' S& b! Z' _5 I
    Example: Factorial Calculation
    + x  Q) I1 P* {6 R$ `! ]
    & E& _) e5 x% U% y  C" C, LThe 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:! B2 h/ S" S: J% ~2 y, L  t) \
    4 {$ V4 C* `, h
        Base case: 0! = 12 l( e' v& ?6 X) P( V: n

    , }' ~' w& e7 H4 V5 A; k; F# F    Recursive case: n! = n * (n-1)!
    3 X1 \1 B* S6 M+ j1 v0 Q! @) c
    9 y* O' J5 N( L$ q- v! _Here’s how it looks in code (Python):
    * M" O' N9 A6 E) ^4 \: C- K& l4 v$ P+ fpython8 [' N  `6 H5 s# J! M8 ^
    1 l# x, z# {7 |' L: E% v

    , {. z& T/ y( |% {' L9 m# Cdef factorial(n):
    7 U1 a  [6 }1 Q" I2 Y    # Base case2 A1 ], R( w) J/ H, ?
        if n == 0:, {, x1 V1 q3 A2 d( Y
            return 1
    0 S4 N$ l! h% |& M5 U6 l1 y1 ?    # Recursive case
    ; O: J; `9 z# p  P5 J5 i    else:. f# q. f. l8 ^: H4 E: u
            return n * factorial(n - 1)
    * R  H8 u! l1 {: G; m1 U* t( g; w: }4 y  t, G
    # Example usage
    2 n% z5 @* o8 @( w" Xprint(factorial(5))  # Output: 120
    8 H& f- P( ]. n5 k4 {6 j# x. _  \: b8 N
    How Recursion Works
    " M$ G9 J, V' U7 H" T
    $ ^% O) S$ W$ O$ w5 i% A' T    The function keeps calling itself with smaller inputs until it reaches the base case.
    & ^. L' }' q& F% ~
    ) m2 S  ^* g4 k' v3 L, h    Once the base case is reached, the function starts returning values back up the call stack.
    . e+ T* F9 Y- _% q
    2 N. B$ }# l& J    These returned values are combined to produce the final result.
    ! B& r# {. X0 b% C! Z) P1 ^2 f9 S4 ~: J$ T5 D
    For factorial(5):" t& r; X) q6 V, ?0 K( V

    5 D6 J5 B1 B8 n, l2 a9 f% E0 W- C% S
    factorial(5) = 5 * factorial(4)
    3 @0 A6 ~4 f  {1 q- ~factorial(4) = 4 * factorial(3)- b9 X0 ~" B1 m
    factorial(3) = 3 * factorial(2)
    2 E# `- D$ u- Yfactorial(2) = 2 * factorial(1)
    6 g1 B: |4 w3 g- F5 Z6 ]/ T6 o5 X" z4 ffactorial(1) = 1 * factorial(0)
    3 l1 c0 Q! k; U; R% ~0 u! |; Bfactorial(0) = 1  # Base case
    # j/ {& d; l  @; X6 r
    + g* V# c+ ^" W! TThen, the results are combined:( j+ h% ?0 o, `9 b
    3 W$ m3 u: c9 ?4 R" Y4 L

    0 `( X* ?: i: q3 O( k, Vfactorial(1) = 1 * 1 = 1( ?1 {4 V& j5 v$ Q
    factorial(2) = 2 * 1 = 28 ~, {1 X9 U0 y( t$ B& b
    factorial(3) = 3 * 2 = 61 f. i- ^+ e8 ?" c$ t
    factorial(4) = 4 * 6 = 24
    & k3 ^1 \: K4 {+ i( r0 [5 p0 b$ wfactorial(5) = 5 * 24 = 120
    " F# w6 c7 E' ]' `. }$ w( w! Y' ~( |5 B; O" X: H) a" I
    Advantages of Recursion
    3 ^. b  Q: X( A+ L% ?, H% w3 m  j3 F/ ^+ E* G; F4 O: 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).! v! y# M3 ~: z1 J1 ~
    9 Q0 s* L2 W8 M; s: O. |
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    # h& v* ?5 Z5 d; c0 S1 }. y& n& b( U7 I/ B5 ]
    Disadvantages of Recursion
    3 }0 a4 c7 e5 w4 a0 _+ m& b# \! W0 |; \8 X* R
        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.
    $ ~  o7 |3 L! i$ S( F
    5 e6 f  n; V3 H$ w) V    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).! T" p+ ]+ b6 ?8 V+ x3 K; {) X

    ( n7 \! B% ]* Q. ?, FWhen to Use Recursion" Z7 m% f. \/ s! r2 Z% G: z( |

    $ b: N. X0 s- d) R7 {" i    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).) q. U2 s. C0 n/ x- w8 R
    ; x% V# U/ Q2 J4 P" \( _
        Problems with a clear base case and recursive case.
    ' w+ x8 d: c* m- x
    " c1 s/ [! V  Y% c8 n: g5 TExample: Fibonacci Sequence
    6 A3 f& V# A0 i) [3 H. w, c$ ]/ Q* @, J) i
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    " u% d0 f* y  E+ }- S3 d* t7 d! s" y% d5 m6 K" N& k& n9 p: Y' n
        Base case: fib(0) = 0, fib(1) = 12 H% n, `3 v/ J! a* z/ ]

    ( m2 i; ^5 \! B9 `    Recursive case: fib(n) = fib(n-1) + fib(n-2)6 Y1 ]$ U8 {; y% ^! J: \
    7 z+ C6 A- K8 ]
    python
    ' U) p1 Z. X9 j1 c
    9 u: T+ M3 a5 i4 U' |4 s* C. F- W, X2 [; O! ?; K8 f  E
    def fibonacci(n):
    / J& v' N/ S# c    # Base cases( p# a9 a: a& _& d
        if n == 0:
    - D, I6 Q& H: i; B1 Y        return 0
    # U/ u- Y0 A  c2 G. V: Z$ P    elif n == 1:
    ; |0 @% `! B( Y* t# O        return 1
    6 J! B  s) W& Y: A0 @    # Recursive case
    + ^0 r( Q& X! s7 ]  U    else:3 ?0 M- f* v9 E) i# [1 X
            return fibonacci(n - 1) + fibonacci(n - 2)/ X+ D" `9 [' v% X4 b7 A0 U
    " I8 @3 n6 |9 o- f& I& ^
    # Example usage
    / s0 H: N, E2 u$ B: aprint(fibonacci(6))  # Output: 8
    $ z* n9 c3 ?' A" {9 ]4 a  D) Q$ b" s3 b% Q. {# Y- E4 |2 C& |, O( n
    Tail Recursion
    * V# s3 V' b% A8 J: l8 ^( f
    3 |" j7 C# B# [0 l3 t7 W& oTail 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).' S* ~) n; C. B: l! V

    ( [8 e/ i% d: e7 E; p. m; 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, 2026-2-1 03:51 , Processed in 0.055525 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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