设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    $ ]0 K/ s, I0 q! t7 f1 X/ i
    0 ~4 S. e# n* {6 E& E解释的不错
    7 N2 ]4 x5 m0 u' x! A, R0 U! d, M& l: V- r
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    " M, ?! d, t: U
    * B- L8 \6 {( ~& W3 Y  e 关键要素
      [6 G' G; y, u1. **基线条件(Base Case)*** \0 f9 V; ^0 K
       - 递归终止的条件,防止无限循环$ p* }1 X; I8 ^
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 10 G' j! i! q/ y' d

    . g6 A5 H. L* m  _' W2. **递归条件(Recursive Case)**6 W) j% [% i( w9 M& M7 }
       - 将原问题分解为更小的子问题$ v1 s. |! U8 t/ Q; s  x
       - 例如:n! = n × (n-1)!- c9 ~* Y/ p) K& ?3 r2 p
    , \( B* {7 p4 d9 r
    经典示例:计算阶乘
    * G7 [8 M3 _! h! I' ?python+ P6 w4 e: b! ]! m" o
    def factorial(n):
    ( |: l0 G) D1 [* a8 _/ s1 n    if n == 0:        # 基线条件, T0 W  G5 G3 V
            return 1
    . }2 y' [7 A" {' B. d    else:             # 递归条件
    9 V3 N( d6 r( J$ O        return n * factorial(n-1)1 u( n8 x# p( S  t% @
    执行过程(以计算 3! 为例):; K% Z0 C1 ^) W3 v1 Z
    factorial(3)
    * z$ h) Z8 T1 n: |1 ]8 t( y" T3 * factorial(2)
    , e; J$ X" S2 i2 l; O6 V, y3 * (2 * factorial(1))& u9 J* ]% F5 X
    3 * (2 * (1 * factorial(0)))4 S9 l- X7 e3 h+ ~
    3 * (2 * (1 * 1)) = 6" t* R7 x! C, d" _! w' a% U
    % k6 g7 y4 v+ ]# |- L$ N
    递归思维要点
    ) b7 p- P  H/ x: V5 ^* Q1 {1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    2 `! V5 ~/ E+ F. f! h% ?2. **栈结构**:每次调用都会创建新的栈帧(内存空间)7 @$ w; F" I& }
    3. **递推过程**:不断向下分解问题(递)5 w+ `' ~* h, W/ i- v
    4. **回溯过程**:组合子问题结果返回(归)
    ' }4 M0 o) A; q4 A" k% M
    6 L! H. B' z; i5 K 注意事项
    + L  Y% Y( n0 A  y$ w' q必须要有终止条件  A# D- J3 {2 v: K" u, b
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    2 I' k. `: G( M某些问题用递归更直观(如树遍历),但效率可能不如迭代* Q9 `/ _: t" T% Q" c$ M
    尾递归优化可以提升效率(但Python不支持)
    $ \# x9 u$ q# d' Q5 H1 h6 H# T
    ( t1 q; m  W7 U( w+ t! E 递归 vs 迭代& H; d2 G! y9 ?. A
    |          | 递归                          | 迭代               |
    3 _$ \2 \6 M  A- V|----------|-----------------------------|------------------|
    * b# c) y- Y) S6 b6 `| 实现方式    | 函数自调用                        | 循环结构            |  z: c5 U6 ~# H, `# Q( i
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    * ~" H; ]5 N4 C) e" m| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |. a5 p/ e5 k3 B. r  ?  o
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    , H# p0 u5 o" n, j1 C" g8 A3 H! }. M3 M  c
    经典递归应用场景% v7 T$ Y0 @1 `: K6 ~$ F
    1. 文件系统遍历(目录树结构)
    # z/ @9 f5 ]3 F" Q# ?& `2. 快速排序/归并排序算法
    6 ~; y0 L: b* ?) f+ t% o5 ^. ~3. 汉诺塔问题. |4 j5 T* g- h0 l
    4. 二叉树遍历(前序/中序/后序)
    2 b% |0 A3 |( n% Y; ~5 O) s4 C5. 生成所有可能的组合(回溯算法)
    , |1 X/ q/ u) Y4 @0 _4 n) \0 C( E  X# O0 ?
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    9 小时前
  • 签到天数: 3043 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    6 v% j9 C0 ^4 u5 u4 G4 f1 z: ^我推理机的核心算法应该是二叉树遍历的变种。
    4 t! H6 d+ @- Y' r5 ]1 m- M另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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 c) }: ]" f0 B6 i: Y# QKey Idea of Recursion! M+ Q) o# {- @8 M3 v4 h+ r
    + s% A2 K7 L2 a) q- p( p
    A recursive function solves a problem by:
    * Y9 d& I( t6 B- Z# C1 s4 C8 c; T8 T
        Breaking the problem into smaller instances of the same problem.6 l7 j0 j5 ^1 R! O8 W# }! H
    4 K7 v5 O( c9 H
        Solving the smallest instance directly (base case).6 U# @- [& z# i. c
    : j' y$ @4 g% f
        Combining the results of smaller instances to solve the larger problem.
    8 @$ I. i# x, p* ~
    6 D  S7 g# F0 N1 x+ @0 B! IComponents of a Recursive Function( [. z3 Y$ k/ F8 E/ L, f( m% y
    9 A) [, P0 x4 ~( |; z6 o* i
        Base Case:; b+ e# Z% ~/ d/ T6 f# P
    . Q! ^% h) v( {0 F, L" k- k
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    1 A$ {3 y0 \2 R
    ' K. C" K% [9 ]1 e8 J6 n' O: f8 k( B        It acts as the stopping condition to prevent infinite recursion.: g  i, Y, o, H7 Y

    " m+ s0 J2 Y$ C* i( I' N$ o        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    ( H; @% k9 o- E
    6 h8 E4 ?6 ]6 R5 s- r  e    Recursive Case:
      C$ a7 k+ c' i" ^5 I5 ^1 ~
    / k0 e' w2 v2 {3 z        This is where the function calls itself with a smaller or simpler version of the problem.
    ( t/ O" ]/ l  W9 p  v# S
    ' b0 S2 d& t( M' T        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    3 B4 M6 ~& O) R5 g% W: O: ]7 S4 P/ f" s* ~) i% ?1 I
    Example: Factorial Calculation
    9 l% R6 c3 x) I5 D1 P/ ^  u) z: D/ `* f; D% a
    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:( S  h4 I- S* U- |
    + X9 r4 ?" s" U' j# A- \+ M, ?4 N
        Base case: 0! = 1; f2 Q* v1 f# O* {# Y$ K: h" `$ p, W

    0 ~! o- E7 w, S    Recursive case: n! = n * (n-1)!+ h8 E# m: G6 t0 r& Z* }, Q

    $ ~# r( y8 }* G+ O' ?# o9 P) Z5 bHere’s how it looks in code (Python):
    1 @9 F* h7 b8 {9 [3 P* H, Npython; i5 s' e- P! D. {9 O) n- V
    5 o) {# u# ~9 x3 ?4 Z

    # C- p7 d+ e% a* Xdef factorial(n):
    : H+ i- _0 `1 R* i0 V    # Base case% q# O! D0 A' }
        if n == 0:0 ?4 F4 a; ]6 H$ ]/ D7 _9 s. e
            return 1
    ( v& e% y0 P: u# ^4 H    # Recursive case
    : i1 ^3 M) |6 z3 |" j3 P- P  f    else:
    7 x+ i1 J9 l9 Q+ P        return n * factorial(n - 1)5 @8 _: r0 I1 ]& m" Q

    ( A% |- d: K3 x2 p# Example usage. D0 q7 q* ^% Y- s( n
    print(factorial(5))  # Output: 120( `8 q# o+ L2 J5 u0 V

    * N7 y3 R4 `2 Y/ W& c" i8 nHow Recursion Works0 n0 L& ~: L2 [- ?

    * p4 y+ a% B4 ?8 @; O    The function keeps calling itself with smaller inputs until it reaches the base case.
    . r$ j. F3 n9 Q  j8 ?6 ^
    ' S. V" N* f) f+ f    Once the base case is reached, the function starts returning values back up the call stack.* l9 B8 s% Q9 C

    5 z  s3 G7 M; h% [# m; A: K2 Y    These returned values are combined to produce the final result.
    0 W% C- v. v- r! u$ c6 b
    - T$ h9 g: p4 d; p+ ~- h' d( X) VFor factorial(5):
    7 E0 A# M5 W' u) {" P& y' N
    + ^6 M5 }. D# N9 c6 p4 N; d# f" v- b4 G2 H, P+ ~( Y+ E
    factorial(5) = 5 * factorial(4)
    ' |# E6 _- Q( j7 u+ l3 ?, j7 ?factorial(4) = 4 * factorial(3)
    - C' p1 f6 r1 Y* j1 M& t" Jfactorial(3) = 3 * factorial(2)/ r" W) G, E6 \4 E
    factorial(2) = 2 * factorial(1)8 S, [2 q& K9 B9 B9 q5 u% I0 x
    factorial(1) = 1 * factorial(0)
    , v4 O# W2 j# m  G8 t% Pfactorial(0) = 1  # Base case
    # ~5 D; Q1 H  y- @! ]8 J
    ) ]4 q. c: [" ^* HThen, the results are combined:
    . {! p/ B; E0 E! h* n& H0 n( t/ V6 P3 r2 D: Z

    7 H- k3 y5 O0 T0 {( S. ]( ufactorial(1) = 1 * 1 = 1
    ( |, {/ R/ N1 _0 s+ G* T: Z& b/ M, Ofactorial(2) = 2 * 1 = 23 K# ?& M+ C( Z
    factorial(3) = 3 * 2 = 67 I1 f9 s) `+ N% r6 W  Q$ |
    factorial(4) = 4 * 6 = 24
    9 J0 K; h) D! j8 C; v* I+ s' ]' Hfactorial(5) = 5 * 24 = 120
    5 y' f0 p2 Z3 Y
    - g! R% E  V. S# LAdvantages of Recursion# x' O5 P% ^) @7 C7 ]
    3 R* M. W3 r  L+ _' X3 R
        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).# ]1 B$ i: S# d* C

    " [( X9 X9 m, F    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    - f# f' x# E, v* q2 O6 @, }$ C% K6 y( i# k0 I
    Disadvantages of Recursion
    . Q) i' i9 P" j6 f4 E
    & d/ a$ t# u3 p8 ~( d/ f2 l& z    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.% U5 N0 [+ A- P: I' K

    4 ^6 `. }+ c# ?  F, c) v5 ^    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).& x1 k1 ^7 J( V

    2 M7 D6 z. r# x+ ]( O+ T, ?When to Use Recursion  i7 I7 X7 Z  E! Y: _

    , ]: P5 q: b6 B- T    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).1 p" Q! p( v( {
    8 W* F, P* t! N5 A
        Problems with a clear base case and recursive case.
    ! |1 w/ l# y* s( `7 s* H: ^% z8 O# y5 C6 b4 K/ Y& g
    Example: Fibonacci Sequence
    % v' Q8 T7 W) V( w: N6 J; T- P7 E  m
    " f5 X* D3 c& h& f0 T& W, o7 ^) n* ^The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    , E/ S: z2 W$ m" B3 D, ]; i' o  h- V" U" h7 S8 p6 Y- ^
        Base case: fib(0) = 0, fib(1) = 1* a9 Y1 E) a* ~+ _. k% e6 j
    : j2 L9 i6 k! p+ T- Y
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    8 {2 M1 |: q% E  ^- ^/ r1 K$ r" K1 J3 r
    python
    * m5 N* L. ^* U1 M& F! G* K0 j( R, Y. K' ]

    ( W  A$ |; l1 g( Q* N$ }def fibonacci(n):
    % x9 w& ]% P, d% F0 K( f    # Base cases, l9 t$ g5 z* B+ T: S2 r9 v( q. N6 K
        if n == 0:. U1 u$ p! x0 ^4 T3 T7 o1 |3 H  Y
            return 0
    & C# m3 o( m% }& i' u    elif n == 1:
    1 c% D+ D+ W; f4 q        return 1/ v& {' d. v5 w2 k5 S$ m" V
        # Recursive case
    8 y/ l" B9 l6 T8 t: b9 x    else:- a% X7 Q( y1 S: X$ F
            return fibonacci(n - 1) + fibonacci(n - 2)( U5 {: E2 L- p7 f) h  [" F% n! ]3 ]
    9 o8 @4 [7 d  H) ^$ k0 t
    # Example usage0 t2 }& Z9 t3 j- U9 b" |
    print(fibonacci(6))  # Output: 83 q0 T2 G: }: ?# v
    " |4 h* J4 i8 E  R
    Tail Recursion
    4 ~  B. ]/ i8 ]+ z- h- b0 j/ P8 D( Y  g
    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).) k! j: L& T: W9 R; b- Z4 p
    ) n4 E& m  @  V
    In 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-9-17 15:08 , Processed in 0.036280 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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