设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    % j* G/ x1 R* G. D. D5 h% d; C6 q2 q) s4 ^, i6 Y& C$ `0 m
    解释的不错
    $ z) g9 y5 m  C" z% Z! N* g9 h
    " h) l0 d1 J* E% f# u7 s: [3 U递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。; F* x, T" L: @9 i
    $ q) E$ z% P$ t
    关键要素; _1 a1 j! c% d* z* Q2 Y4 ]6 S% m4 `0 z
    1. **基线条件(Base Case)**
    : J! V; D# v# ^5 ?   - 递归终止的条件,防止无限循环
    % Y! A+ Z! J& h6 g( X   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
      @8 Y( g* R8 M
    $ |$ h% `) j& B& A: l2 W2. **递归条件(Recursive Case)**
    " m% B# N4 ]1 V1 b$ _! g4 E" c   - 将原问题分解为更小的子问题0 G% y3 H! E5 D& i# L
       - 例如:n! = n × (n-1)!+ V$ X3 r' W, l) |2 C% ]

    ' G7 x* Y- P, z1 K5 U" i 经典示例:计算阶乘! e  i6 R9 k  X* P9 N- u+ q
    python
    8 `# U; o3 N  B6 }& Z8 Edef factorial(n):" ~/ ?. I/ I2 j+ F( q
        if n == 0:        # 基线条件
    $ p6 ~, C$ F0 k! T        return 1
    . `# \5 T: v1 j0 T& m    else:             # 递归条件
    7 w! y4 U5 O( t+ H. ?& {        return n * factorial(n-1): \4 B" T3 }% h3 M: T* \
    执行过程(以计算 3! 为例):0 ]5 D4 q6 B0 ]- |% P3 {( j- Z
    factorial(3)+ ^% f' k3 d% \- Q3 T
    3 * factorial(2)
    ' k4 _  P( I. W3 * (2 * factorial(1))& l2 N3 ^+ X! M
    3 * (2 * (1 * factorial(0)))- f8 O% x3 q5 ?; Y: h/ W
    3 * (2 * (1 * 1)) = 6/ L( D# d1 H8 g) u- O) C. y* `
    ; ~$ T/ {$ Y6 s& O% S
    递归思维要点8 \: _4 ~0 z) y! C
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    3 x6 y1 |8 _0 s2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    ; N* d$ b: b5 |( }3. **递推过程**:不断向下分解问题(递)! w1 e; t  b" n/ U" I3 \. u. z- |
    4. **回溯过程**:组合子问题结果返回(归)
      m$ D7 ?; t& B5 a0 I) w
    6 |. J( D0 e! N 注意事项' q# M7 z* W5 P* g3 K
    必须要有终止条件
    0 U! g) f1 m7 p, F, v递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    % k$ D' L' ^& x6 K某些问题用递归更直观(如树遍历),但效率可能不如迭代. {$ g* X5 b4 s' {) V, f1 n. ^, |
    尾递归优化可以提升效率(但Python不支持)
      A% J2 n/ Y1 t! f2 x: g' X9 U- q7 f1 x1 s( g5 e) W
    递归 vs 迭代
    9 j3 I) f( b$ |; y" e) h|          | 递归                          | 迭代               |# A9 s. ^2 a9 _2 k/ l
    |----------|-----------------------------|------------------|
    : T4 L0 S" O4 ^1 b( h* n| 实现方式    | 函数自调用                        | 循环结构            |& g5 ]; b/ d- S, S) W4 ]6 m
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    + H/ C; ^( L% ?1 x1 ~* k! V| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    . H1 J  E" T8 n% `. H| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |3 a+ r! _$ o5 ~! }  L0 t

      @  `5 C: G0 b5 _+ U( Q3 M$ u1 n+ M 经典递归应用场景
    + N. _* m7 t' [; \3 c1. 文件系统遍历(目录树结构)8 Z' s8 p& I5 G' i0 v% |
    2. 快速排序/归并排序算法9 p+ b; n; a0 S: r% M8 p- K1 e
    3. 汉诺塔问题& W: s# B0 J9 _3 R
    4. 二叉树遍历(前序/中序/后序)
    : y3 |) s# }' Z9 ]' q- U5. 生成所有可能的组合(回溯算法)
    " Z5 ~) ~/ o/ F( D
    8 a8 K9 j! T5 H2 b4 ~0 @' S! ~试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    开心
    昨天 01:20
  • 签到天数: 3115 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,' a7 ~# p3 N! [
    我推理机的核心算法应该是二叉树遍历的变种。  j5 P! Z9 p2 R  e+ d" Z0 P
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    3 ~! L% ~9 \* R* |Key Idea of Recursion
    6 R- L: U5 z% B" |7 E9 Z/ U
    # @- [! i1 Q- qA recursive function solves a problem by:
    " p$ q6 a3 D# M) c& d$ l: p
    $ z8 g; _; ]: v6 u/ `) ~    Breaking the problem into smaller instances of the same problem.
    $ Z- s5 O1 Z8 T8 @
    ( S7 G- L& Z% P, G% U    Solving the smallest instance directly (base case).1 Y7 U, A8 o# V5 B; w

    4 H# q) K8 s( A) p7 E    Combining the results of smaller instances to solve the larger problem.2 n8 ^/ u0 z; H* M, V% v
    % q- ]: w# ?6 x7 g* t0 B8 v( r3 `+ I& y
    Components of a Recursive Function
    $ X5 _# Q+ }& c# o
    / v/ `  B1 C1 I3 Z7 V    Base Case:
    1 \1 W0 l# J/ D2 N" V$ Q, |2 U# ~. U0 @
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    6 V1 S3 u, n9 V6 M6 N( W! H: j( x, q! s' a5 H, j
            It acts as the stopping condition to prevent infinite recursion.; @$ q( G0 ]3 j) p6 |8 a0 Y

      T" Q, x; `, G2 z9 W' a: B! `        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.: K; X) |8 \* M  P

    0 ^& \1 t. b* q7 U$ ?' i9 K    Recursive Case:9 A( o7 `) f* D* j- _* O+ t5 n
    8 c- I* L& X2 d, R( S; |
            This is where the function calls itself with a smaller or simpler version of the problem.# m0 t4 s! V5 a! Z
    $ L5 F7 X! ?+ y* _+ I2 O
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    . x: q0 y5 [1 @$ p: X* q/ Y) v" }1 p0 ]  e
    Example: Factorial Calculation8 c3 ?- w) B; |7 H+ X

    # g0 X  I: ~+ W, [) VThe 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:+ l: B( H6 w, p; V' d( Q' B

    0 C+ L9 y6 f0 K$ [3 q1 Y0 w    Base case: 0! = 1
    + O: k; E/ h. D/ B7 J  g/ [. l0 Y9 \) g9 a
        Recursive case: n! = n * (n-1)!4 G8 c% J/ R; a! v$ J
    - }0 \1 `. u) c/ K0 ^  e
    Here’s how it looks in code (Python):
    " h$ N, l. Q! ^( npython
    % b& k' A1 W8 k) b- s# V/ O5 h# K* }5 H  f. Q
    4 ^+ k. U+ f3 M/ A: Z0 C
    def factorial(n):' V! K3 [2 L9 |* S7 F8 i* L
        # Base case
    . U/ v) J/ ?: F* p    if n == 0:
    ! o, E3 @8 ]. u9 y        return 1& o8 y3 J& B: m7 m
        # Recursive case5 i* H$ f/ [2 f+ z
        else:+ J' v3 u# D  m$ N7 W% V) ^) C
            return n * factorial(n - 1)
    & t3 ~% H2 k6 U! h# T$ b) ^2 M4 `, w# b( _
    # Example usage
    - N, `2 A7 c, A9 Xprint(factorial(5))  # Output: 120: t  I+ V6 [2 @9 s1 S

    9 n  E8 n( b+ M( ?- }8 UHow Recursion Works$ q8 x+ ]; w$ ^9 M# r0 H  u

    * q5 g  M7 E- l" |  W& F$ ]4 q" I    The function keeps calling itself with smaller inputs until it reaches the base case.% W2 [3 w: ]8 B# d

    1 R' r' A! o9 |$ S. `% M- \    Once the base case is reached, the function starts returning values back up the call stack.
    7 P6 L% i% L  s- k
    * X4 E$ R' j% H4 K3 N; I/ M    These returned values are combined to produce the final result.$ O7 k# U1 ~! A+ q3 E7 ]

    ; D( w: x' ?, O; M8 v' dFor factorial(5):5 X, [" h* p. `7 L2 `3 t+ n* U3 l! k

    . s5 H+ M# `4 c% U
    , y6 H2 U5 c. }' Ifactorial(5) = 5 * factorial(4)
    1 ^! A- y' ]3 K" u* R+ @factorial(4) = 4 * factorial(3)8 i* M) U3 l3 M; _: ]+ C9 Z
    factorial(3) = 3 * factorial(2)2 c8 M& Y$ B+ K
    factorial(2) = 2 * factorial(1)
    - Z# q/ i) |7 Pfactorial(1) = 1 * factorial(0)
    3 Z- b  k# B; @  `1 M, @3 Cfactorial(0) = 1  # Base case6 s4 m5 U- K: I# N' T
    ) u' Y7 W$ c% P4 f
    Then, the results are combined:7 Z3 P; A1 g( J; v, P

    3 w. P  h( {7 P* |8 D  U2 m
      L2 e+ u3 A, L0 y) c0 r1 q2 Nfactorial(1) = 1 * 1 = 1
      K; J" Z! d& d. A% I# ^factorial(2) = 2 * 1 = 2
    6 f; n* j! U7 y- C$ w7 ^factorial(3) = 3 * 2 = 6+ X) R, v* {) X  |' z
    factorial(4) = 4 * 6 = 24
    ! j6 X. k3 h* @9 c0 c+ `. wfactorial(5) = 5 * 24 = 120
    7 {8 Y# z- V# o3 o3 m# \
    7 T  |+ a& V( U/ T  v5 M# SAdvantages of Recursion$ N/ j; N1 D% ^
    2 n1 P* u& g7 M; b+ Y; t9 v% k
        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).- @3 g0 t8 b! k/ y7 A" [/ I: k  w
    ) E4 P$ Q7 U( @1 N" _
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    / g1 u7 N6 M; m* i+ C! y2 g2 ]$ ?! C0 W
    Disadvantages of Recursion
    4 Q3 h. u! o2 Y8 E  o
    . Z0 R. m9 z) B9 T( a5 n- i" y    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.
    2 E0 I9 X' e2 D
    4 s; Y* B2 s) z4 w  _9 c    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).2 h- r. r  q8 c# w0 \5 P
    * I7 t$ m# E! w+ [! N3 H2 s
    When to Use Recursion
    8 s7 ^$ |& @* l2 l7 {+ y) \+ z6 c4 m5 g5 p
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    + P7 p! o9 o: J9 P% L
      Z' K3 a# h% U# }5 B    Problems with a clear base case and recursive case.
    4 ^" j. X$ f6 @
    5 ~" D" D% H$ e' XExample: Fibonacci Sequence6 g* a+ K2 Y7 O  s1 R
    $ R% z. {2 ^; @) A/ G
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:2 P% k& h/ r5 y+ b4 v. |8 T! a

    ! z: L* ^* Q# G! M  [    Base case: fib(0) = 0, fib(1) = 1
    ) f/ U7 `6 i+ w
    ! t: {5 U$ B8 D0 W# M# G! E" d    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    % x3 g' a$ ?# Z5 U1 c( `& V' L. T+ [! `( {/ l' }* H3 a
    python
    , U1 _6 J) ?8 s1 H+ j/ J$ W- V8 L" j; Q7 x" ~3 E& T( _3 V
    : k  |5 s. r2 K6 P- S* ^  \; D  O- t
    def fibonacci(n):& f9 i! q% L4 x) |, B
        # Base cases. ?; G3 q$ q  C, Z2 R
        if n == 0:! B1 \0 p9 C" M) U/ B1 h6 C
            return 0
    ' g1 L- i( ?- o    elif n == 1:
    7 _- @" W$ o3 c' P' r        return 1
    4 J1 w, e) w, R    # Recursive case
    ' _8 {2 h) v3 Q* l6 c, W0 |    else:5 j+ k3 B/ N6 ?2 R3 y" ]
            return fibonacci(n - 1) + fibonacci(n - 2)$ y: @/ m6 m. Q  O  |# q
    ! f3 G% ?& o5 F9 v" o) v; K$ z
    # Example usage
    & X4 L/ J: \6 e' }: U% wprint(fibonacci(6))  # Output: 8( b1 r! L; P4 K# [/ i
    3 g  Y  b( _8 Y
    Tail Recursion4 b6 D$ ?+ ]! C% N
    & y4 m7 w7 N8 P. V! |- [: T, m. 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).
    7 U. D* J' M& U( \1 @- |
    ! v9 A# t" M( g5 U. ?# C# bIn 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-12 03:15 , Processed in 0.030178 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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