设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    2 L7 [6 h  |5 r
    % _' }4 Z: t- E1 \/ }4 h! {解释的不错
    % b1 X+ Z, n. y5 Y3 |) `: Z+ h$ K4 ?; a
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。0 w. }( r: L# {+ l) Y/ `( W

    2 D2 c+ v3 V% C& P; B 关键要素
    $ o- x2 S; M$ }! |- |1. **基线条件(Base Case)**
    6 Y, y3 h4 `5 @0 m- Z   - 递归终止的条件,防止无限循环7 z$ j* I6 d9 J6 _3 a
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 12 Y$ r  H1 {8 `; e
    3 v3 @! @7 ^. E! m
    2. **递归条件(Recursive Case)**
    , w# G) Y9 u! ]5 c$ f, Z9 e7 n   - 将原问题分解为更小的子问题( ~# J9 Z( v) E% ?' Z! ]
       - 例如:n! = n × (n-1)!; [9 ]8 G# W6 v

    6 x4 f+ a0 \/ G" a! x( u8 i 经典示例:计算阶乘" p( G* o8 U# |/ `# @
    python, h3 J( M/ M( k5 Y
    def factorial(n):9 |% E3 b9 B! G
        if n == 0:        # 基线条件
    " Z) u6 T+ Q! Z3 k        return 1
    % }) z) f2 f& x6 j# x6 w    else:             # 递归条件
    6 h4 c% R9 y. M4 K        return n * factorial(n-1)
    $ x+ Z" D7 \% N7 m; ]. k执行过程(以计算 3! 为例):
    ( v% @" T$ Q; cfactorial(3)
    ) Y+ f( q  {4 L" h, h3 * factorial(2)
    $ ?! j- E; s. M" g& b  j3 * (2 * factorial(1)). F, Z# g- u% I! ~6 M+ q( M
    3 * (2 * (1 * factorial(0)))
    " Q  s3 m: G, i% H3 * (2 * (1 * 1)) = 6
    3 L+ {. P+ @/ G+ N, y' v: c% L% e3 N( c/ x9 V$ |, v
    递归思维要点. F9 `" C* S/ u0 E
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑+ I& o$ A! W7 s' c0 b( i
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    $ e* A' @; e* M3. **递推过程**:不断向下分解问题(递)" L# g. m$ z$ a' ?3 N! H8 d
    4. **回溯过程**:组合子问题结果返回(归)
    1 i0 }; F8 e1 t* \& Q* P) a! k# b) e8 W9 F
    注意事项+ x% e  k4 z5 p( N' ]5 l
    必须要有终止条件
    8 e/ k* _: d6 ^  q8 q$ x0 v递归深度过大可能导致栈溢出(Python默认递归深度约1000层)! p' R% Y9 n* e$ V$ |0 H
    某些问题用递归更直观(如树遍历),但效率可能不如迭代$ \! n* A- U+ P3 a7 f9 c4 H' q  \
    尾递归优化可以提升效率(但Python不支持)# m8 m* B- g! S# I2 p- y
    ! r; c* T# P2 ^0 U; o
    递归 vs 迭代' u' M, |' X, r- U* n7 u4 I
    |          | 递归                          | 迭代               |
    ; Y1 N' a( U- n6 G' s" Y4 W|----------|-----------------------------|------------------|
    9 {$ r' G6 _, k- y. @| 实现方式    | 函数自调用                        | 循环结构            |
    ) e, V4 E1 r1 ?3 i- ?6 S/ T2 Z8 @| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |6 a0 z' F: w! ]( {, e
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    5 V% m- Y% ?( T3 n| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    % `1 G  P. j: y4 W8 T" T
    0 ~9 R, C* E$ ]( W+ j5 Z 经典递归应用场景
    ; n) {% l6 F$ |$ {9 Y1. 文件系统遍历(目录树结构)
    * @: K6 V- o8 ^6 I: u9 p- \2. 快速排序/归并排序算法. [0 {- |" w8 j
    3. 汉诺塔问题) B. e- m  O$ z1 o9 {1 m
    4. 二叉树遍历(前序/中序/后序)5 l0 _/ M# q+ N6 {
    5. 生成所有可能的组合(回溯算法)# S/ f$ k! [6 k
    + a4 ]' E/ u3 A2 x/ q; L8 V
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    昨天 08:02
  • 签到天数: 3126 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    2 M" g/ b1 ]7 _- `* q我推理机的核心算法应该是二叉树遍历的变种。& ~1 ?' y% d/ s7 Y$ b
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    * o3 d& p3 a% J9 F0 c2 HKey Idea of Recursion
    5 I4 y. f0 @5 W
    " y8 g3 o! v0 QA recursive function solves a problem by:
    " [7 M  p: h2 X5 Z( Q  m2 m. R, J, z' \& V* i  n! V
        Breaking the problem into smaller instances of the same problem.
    0 V6 U5 }  a. E4 v
    7 a6 {# l2 J# E& x8 a  f4 Q! r    Solving the smallest instance directly (base case).
    6 C. h2 q) b$ d+ K( ?9 G& V# h( I  m2 y! P6 T
        Combining the results of smaller instances to solve the larger problem.
    0 D9 e1 X0 Q4 N3 |7 Z4 b
    % {/ s( Q2 q/ P3 q/ C! W/ M9 MComponents of a Recursive Function
    3 h- Y- R& c! B+ }- X  N1 A
    5 m- _: F& Z2 S& v7 o$ N    Base Case:
    6 V1 l& v2 T7 q! r5 ?+ G; o2 w
    , g$ B) @* A) Q1 j8 s6 {1 ~        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    2 i  `1 n, E9 j* g- ]
    " Y. W  x  z' i3 E7 _4 }/ H        It acts as the stopping condition to prevent infinite recursion.
    ( i) Q$ ?# @  G+ y, K: a% a  X' q' w
    ! q$ J7 a* w/ f0 L) w" s        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    1 {  X% k7 D" w9 y- f0 [. C) B
    8 f6 ]# _) |, J/ D8 ?' e9 f    Recursive Case:
    ' k6 I/ I6 K, Q: I$ a, b5 h5 H
    1 J, Z, `, ]3 }. a& U        This is where the function calls itself with a smaller or simpler version of the problem.  z; f+ d$ _. ~# Y

    - g* y5 u9 L% o! j2 ^' U! ~        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
      l0 }/ ]4 R  E" g, D" F6 b9 }( o; g
    Example: Factorial Calculation: U( Z6 j5 w  o6 _1 X; P. o' f
    2 l9 c: m" l! G3 I% K
    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:
    ; L" f' p' [' V9 h+ \# X* ?+ ]1 A
    7 g" Z+ W. `4 @) M    Base case: 0! = 1$ C1 I0 q+ X+ A* K- G

    8 B/ t" t* ?* ~3 c    Recursive case: n! = n * (n-1)!& N3 Y. X6 q( X6 N# a5 e
    5 k  J* S6 @1 D; D2 |
    Here’s how it looks in code (Python):
    4 G9 L3 P( [' O2 d1 Apython
    6 b6 g# y/ l: k3 w. H* D
    # X1 f' v0 b8 Q) b& N( g
    . g1 e% j% T( P( S; Z5 Sdef factorial(n):8 ^# Q( o# Q' M' t# y( s( I* G
        # Base case- a6 O+ x8 V7 ^4 ]% X0 m
        if n == 0:
    8 e8 e, {3 a: O7 V/ M3 |0 ^5 ~        return 1% n4 c' W. \2 L: G: L8 b$ d. \
        # Recursive case
      @. ?8 F4 ]2 m) K) \5 }( f    else:
      _( ^/ K4 y1 ?+ ]% M' a5 a        return n * factorial(n - 1)
    ' Y- j7 f5 {) h2 X/ n# I  u: Z
    , K2 S. c5 D# H1 w# Example usage
    % {, f: f; p" h& M+ J& Lprint(factorial(5))  # Output: 1202 d" s, b6 W9 ~

    1 p( E) T- b3 D% Q2 rHow Recursion Works% w6 @! A3 v  V% f
    , M% B& e; `+ n/ y9 i
        The function keeps calling itself with smaller inputs until it reaches the base case.
    5 |: Z2 B! z2 _  u" d9 ]2 |
    7 m4 S0 |1 [* Z& G4 z7 r    Once the base case is reached, the function starts returning values back up the call stack.
    8 d7 J: M. A' a' E7 F( e( ~! y6 M0 D1 O0 @8 l2 ]
        These returned values are combined to produce the final result.
    - q6 B. _, a( ~. @" O* O% U; H5 p+ G  w& R' T$ H8 h2 J' ~# ?
    For factorial(5):
    ) n8 T" t- r) M- r; Y6 n0 I
    9 E" Z" {6 D1 Z3 }/ E4 J3 n6 W" |4 k& D' x/ Z( v# s
    factorial(5) = 5 * factorial(4)- e; p# r9 J& S' M
    factorial(4) = 4 * factorial(3)
    . X/ A; z: e% a/ t$ P  Yfactorial(3) = 3 * factorial(2)
    3 t  n' H9 P! E& Wfactorial(2) = 2 * factorial(1)
    ( d8 J# m9 L( I1 p1 ~# K# [5 Pfactorial(1) = 1 * factorial(0)
    3 [! r* l" X1 x& Xfactorial(0) = 1  # Base case3 Z' y6 o- o( g" `* A  i

    3 X8 P2 J! h' f; t6 {- G/ oThen, the results are combined:$ s- e( u- f* o% u- D
    ) e1 h4 i, c4 a' F6 ^8 t; A
    3 f+ F+ }9 t/ b" a# O+ W
    factorial(1) = 1 * 1 = 1+ t+ p$ |2 Q/ [5 `; ^
    factorial(2) = 2 * 1 = 28 l- v' ^4 c, V2 H% V( M* ~+ [) {
    factorial(3) = 3 * 2 = 6' `* h# I! ?8 U3 K4 k, ~) D: e+ @7 y
    factorial(4) = 4 * 6 = 24
    % q* b7 x% k2 \! d. ]) @& }factorial(5) = 5 * 24 = 120
    / B( B8 v, |7 R  ]" F5 ]' l6 z8 s1 F8 V& n5 w3 G, C( r3 U
    Advantages of Recursion2 d9 N: b: u) N4 k6 T
    2 F4 _% c9 P# c4 ?6 @6 v: X
        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).$ o* Z/ `# E, }  a+ O; t

    8 q  f) `7 a% J: L. x    Readability: Recursive code can be more readable and concise compared to iterative solutions." w+ {  Q. q4 ?) b

    $ q% ]3 ~- y% x3 S1 g% A- qDisadvantages of Recursion
    ! \3 k: d6 c. M' t. u3 F) E) U. S9 u! P# E& q5 w6 n5 \( 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.
    1 I( n9 b4 O  n9 g& M* }/ E9 [+ _6 N' K( P: h2 E8 j3 e
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).6 y2 h6 @+ q, `  i& A1 ?& |7 H

    0 d4 f' g1 B0 r' bWhen to Use Recursion
    4 Q# w, ~% w) C4 L) |2 g, c! E" i% J6 x# B9 W" Y6 c' K6 ~- A
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort)., ]7 A5 T3 ^  C. @* F/ ~2 Z

    % _0 j3 |! A' Z; v7 W8 y( p" Z    Problems with a clear base case and recursive case.
    ( r, C- \* E3 h) U3 D) m: M9 n5 E5 {5 @
    Example: Fibonacci Sequence
      h3 f: ?. M% X- z; S# A+ {5 [& \2 N( j
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:4 Q: y& M5 x- x

    5 i' ?6 @: A. T: W1 V* h, D3 ?0 B    Base case: fib(0) = 0, fib(1) = 1. z1 T  K, H' `0 ~1 Z! ]& o
    1 I5 u, G( R* u" A3 S. h, U
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    2 N0 Q! J9 {* A
    - s" `8 ~) w- `' K9 Fpython
    6 V) a7 Y2 J! d& F% ^- z! d3 x- P6 `6 R/ t
    : C% U7 H4 }  G1 @1 n9 Z- ~! O
    def fibonacci(n):* E1 @+ U/ l4 }" c  ~% ^) v1 S, n% d
        # Base cases
    % S% s. R3 r# R3 i6 {( S) g    if n == 0:
    7 i; W1 }3 C' T1 h, b        return 0
    ! q# o' R7 J; b6 m* k! V    elif n == 1:1 v' c' d( s" h2 }7 V
            return 18 I, X7 K( z: U( w" b) G6 _, c
        # Recursive case
    9 X/ @) k+ o! x* f' J7 i+ i% v7 r    else:6 g0 B2 J/ o2 M# j: B% c2 B
            return fibonacci(n - 1) + fibonacci(n - 2)/ f' Q6 S5 e3 \7 p) d% P

    $ N1 d" O* Q! ~& }) Q3 f# Example usage
    6 Q: Z! B5 D) X. Q! }print(fibonacci(6))  # Output: 8
    7 G2 G& a& h: W3 {% \2 m
    5 w" r" y3 ^8 PTail Recursion
    4 ?+ P: G9 u0 t. S% ^3 w( m1 z1 V9 A6 I: @
    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).
    ; U# ~1 j% X, a  N6 m5 ~! K1 d* L8 H0 n
    ; K+ T- P8 b3 D+ O6 o7 zIn 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-25 02:52 , Processed in 0.031079 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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