设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 " B- [- C0 F3 b  D! q; N5 P

    4 v4 A. W" P. o; S" F解释的不错
    ' k  D4 A2 j5 _+ Q* Q$ K$ F: j. U
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。: X+ r+ z% j, s! Z8 P
    1 o$ N& \! B7 y1 z
    关键要素
    ! h( @' q$ o8 \" t9 W+ D5 y0 S1. **基线条件(Base Case)**
    . w1 }' X" R9 y7 S. q   - 递归终止的条件,防止无限循环" l/ Z  W: t+ n0 t" y
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1! {; v4 ]' J9 S9 d3 t% E

    , d" X9 u" `* S: i; W2. **递归条件(Recursive Case)**
    8 Q! L0 c9 q, u' d$ \% X   - 将原问题分解为更小的子问题* \6 F" q) n3 e+ J& [
       - 例如:n! = n × (n-1)!
    + Z- v1 w8 ?2 l  @1 q3 T- j; n. r# F$ F* [7 {
    经典示例:计算阶乘$ g( @3 n( F% }
    python( a+ N: S+ Y8 T: w8 Y) M
    def factorial(n):& N% \' ~# N- R- f9 L( G, T  E
        if n == 0:        # 基线条件
    2 J5 L/ R8 g! T        return 1
    & y$ N2 y% S6 [& I! \" w- U& Y4 V    else:             # 递归条件  a+ k+ V1 k( G9 {
            return n * factorial(n-1)
    $ J) g$ A/ j- H. ?0 E执行过程(以计算 3! 为例):& e/ y' {4 t3 h( v" n# M
    factorial(3)
    4 y/ G% b; j2 z, x) \0 ~/ [3 * factorial(2)
    % ^2 n+ y; a2 C+ n3 * (2 * factorial(1))1 o& _1 d; d' d3 z
    3 * (2 * (1 * factorial(0)))' d: c+ {) S) ]! G/ {
    3 * (2 * (1 * 1)) = 60 P# c8 {* _% z/ N% _) {8 q- l
    4 t$ O9 a/ [: O
    递归思维要点9 E! T" p# t4 z# ^( w/ b' ]
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    $ |1 r, G7 R: |* S, O) l& z2. **栈结构**:每次调用都会创建新的栈帧(内存空间)% x: F- U1 u! Y% q/ A6 g: e; [
    3. **递推过程**:不断向下分解问题(递)
    8 p8 K/ j( R5 j, o4 k4. **回溯过程**:组合子问题结果返回(归)" k1 P& b  A# i  F) U  I/ U
    $ a) t5 d2 s- G& o/ {# f, o3 o
    注意事项
    6 C: S+ s* [9 `% `/ k( P# \必须要有终止条件. W1 f5 J1 U- e" J- [9 e6 z) e2 q1 Y
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    2 l$ i7 w+ ]1 D+ ~( q. E某些问题用递归更直观(如树遍历),但效率可能不如迭代
    ( z! ^& |, a2 n7 R2 e  Q' _4 D尾递归优化可以提升效率(但Python不支持)
    9 W) e( V( v8 @, Z. n/ O3 s
    . b0 W5 H5 ~% \; x# ?4 s 递归 vs 迭代
    # l' Z+ x9 ^' Y2 F% e( l$ F|          | 递归                          | 迭代               |5 I6 R, |# x4 }2 M! u2 j
    |----------|-----------------------------|------------------|
    5 _6 e6 `9 G. ^+ V- L| 实现方式    | 函数自调用                        | 循环结构            |
    " b; B, t4 k0 _- n# X| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    ) C5 P$ z0 z. e5 M' U( W| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ; T! v7 E8 x! P6 u0 Z| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |! T$ W, m2 e$ s: L
    2 {: c! ^$ i# @+ D! ]8 y! A
    经典递归应用场景
    9 Z, g- N, |7 [' I1 D% X: x1. 文件系统遍历(目录树结构)* R/ X3 B/ q8 r9 E  [
    2. 快速排序/归并排序算法! i. O# }9 w! G
    3. 汉诺塔问题! t; g. x2 B. @2 u* ^
    4. 二叉树遍历(前序/中序/后序)
    & T2 E" s. D0 J0 a: y5. 生成所有可能的组合(回溯算法)$ E* h6 j' C/ a' x; |

    , G3 W/ T( r7 ^5 d2 X试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    开心
    3 小时前
  • 签到天数: 3115 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,& o2 L1 k3 Z2 p0 ^8 N
    我推理机的核心算法应该是二叉树遍历的变种。
    1 f& j# r# w: B! v; y& i- w另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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 w; A% F! j% e; d% v3 tKey Idea of Recursion* v6 n$ f+ y- O/ v$ ?

    + m4 N8 l% D+ V6 e( i4 OA recursive function solves a problem by:
    7 y- A- A, O0 h  A
    / Y. r9 z" \1 g5 c    Breaking the problem into smaller instances of the same problem.
    0 U' Y& n' T, A9 \
    . X' g, h8 e* Y; R& R    Solving the smallest instance directly (base case).
    % D: E7 o1 l0 Z) o- f1 Z. M  o9 w2 f' M& {; e; v( J
        Combining the results of smaller instances to solve the larger problem.* p, i, j1 X& C( C$ z' y
    " K2 Q" V& ^( Y* B9 ~
    Components of a Recursive Function& H: r, W1 ?- Y, t: ^* Y

    . q! B1 H" R- [6 u    Base Case:
    & `& U, K' X) t
      |$ U1 s! Q# l) W5 ?  {        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.9 J3 N# C. D- D% X) D+ P! i. R
    + Q$ v4 R6 a$ p7 C  ^7 q" b2 ?
            It acts as the stopping condition to prevent infinite recursion.5 C: }% X3 r; k5 R
    4 _6 Y+ C2 O' z. i
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    1 c6 K- J* L3 Z" g6 X5 u* G7 K4 s. c* s
        Recursive Case:
    " W1 p# o% _* C" V" C) H+ x: p4 Z* ]
            This is where the function calls itself with a smaller or simpler version of the problem.& K& X, D2 [8 I. m' J( }' G

    1 o& w0 U% J7 C" R        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    $ E% R) P  k: _$ l# u& U
    4 S% ^; B$ L0 h" z* xExample: Factorial Calculation4 M( L3 M# ~* N. }6 Z
    4 K6 o7 t3 p' N$ P
    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:9 @1 c1 @9 z; i) y& _" g0 t; Y
    8 @) q9 m9 s& [7 z- C/ ^* X4 e
        Base case: 0! = 1
    ; i5 f; `( d; r1 t. a
    1 |7 x( y- J, Q- f! U9 q/ J' M    Recursive case: n! = n * (n-1)!
    / C" y' R7 m$ P# e  H
    4 f3 ]5 y( }# y9 ~+ A, n; dHere’s how it looks in code (Python):
    " d+ p: `! L5 y6 L! r4 xpython
    ! U5 {8 i8 S; J7 L! Q4 J0 `, v% l  N2 v) M/ q
    1 w0 z2 Y) b" ~% w4 t9 ^$ I% p
    def factorial(n):
    - A! X. i4 A& d3 R    # Base case- V* T( e  I( b4 f  i
        if n == 0:: I9 s$ Q; l% R' {) s# W. }
            return 1
    ( e! L7 w1 s0 L- j' }. A, n6 M    # Recursive case
    ; B; c& i4 ?* |: r, X+ p3 ~    else:, G! H# O( L5 H8 O) W- C7 L
            return n * factorial(n - 1)7 ?/ ^% ?# m  M
    0 B  p2 e9 x1 M- |6 \+ j: R
    # Example usage6 I4 A. a/ H, v  S. c  a
    print(factorial(5))  # Output: 120+ ~! L3 o- x) I  r% O* q- ]' T
    0 W  q0 {% G. I
    How Recursion Works$ M6 y" s2 }- B# l5 \* ^- T
    ( d; Y" o) J, k! c# b4 ]
        The function keeps calling itself with smaller inputs until it reaches the base case.+ i1 L. j. }0 q" C1 u- Y0 O2 _
    , l, F( w0 l" x0 w# m
        Once the base case is reached, the function starts returning values back up the call stack.
    - e- C# O1 n8 V% `2 Z! B0 `' f, ]# m2 a7 D' H( e
        These returned values are combined to produce the final result.7 b; A3 C+ s2 a) {! k1 y" i2 }. D5 N7 ~

    ) n+ O( V: v3 O: c4 u, w2 sFor factorial(5):9 \. U) J- |; t) c: E
    ) A. Y6 M$ a& n( P

    " U5 V5 {; P) a, A( Y4 k  i4 j7 Lfactorial(5) = 5 * factorial(4)! T. r- x1 v9 V, W- ^( ?, R3 X
    factorial(4) = 4 * factorial(3)0 R( H$ ]4 i! c9 N6 V
    factorial(3) = 3 * factorial(2). u" v3 f# D1 @1 S! p8 Y
    factorial(2) = 2 * factorial(1)4 q% Y2 B  I- Q! \. f: n, {
    factorial(1) = 1 * factorial(0)/ m4 P3 r: p2 p" F2 v$ B- t8 i; ^0 {
    factorial(0) = 1  # Base case
    7 a* p! h  H  a: ^! I/ J2 a& E2 T3 v3 i9 q# }9 {% I  B/ F. v
    Then, the results are combined:( x1 P$ m1 o& w" r  S$ m
    9 O) u$ p; H# \) T* |

    ' J. c2 i* u7 ?- g1 J; i3 `. Y& Xfactorial(1) = 1 * 1 = 1
    ' W" q  y. w) h# }3 sfactorial(2) = 2 * 1 = 2- ?) n0 s' I1 [' j7 H$ p( J
    factorial(3) = 3 * 2 = 6* V$ e7 z  A. {/ m0 ~$ `" c
    factorial(4) = 4 * 6 = 24# q. |( I4 r. G1 M' l& a: `+ L
    factorial(5) = 5 * 24 = 120
    0 J' |: ?2 Z) }' @- ?+ [( J  _9 j) T  z5 V+ O1 E7 W7 {. k) l
    Advantages of Recursion
    8 J; q+ H* Y* c; u& u5 u3 H
    - W# X) t. y/ M, D    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).  T6 }# _/ d' Z% s

    + E. k8 s. C) R% P0 i    Readability: Recursive code can be more readable and concise compared to iterative solutions.: I8 Z5 m" I( u  M! D7 V

    " i7 \* \# K3 I! o- ^# ^Disadvantages of Recursion  [( g% W6 K' k. V# f# k
    ! h+ H( A% @4 U0 @* U5 c
        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 T& Q1 R, x6 d7 R9 s
    0 _1 g  V0 C- ?
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    $ N% H) p/ X) i1 `- ^' }- W- c  a. }
    ) [! d6 H% U+ s8 g0 FWhen to Use Recursion
    0 z' `, ?  q# t. f; B9 N. V4 r2 T* U1 i/ `* p4 ^6 z: [2 \
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).* I9 ~+ B4 k' |7 I0 ^! [

    - c- J8 L) j+ O    Problems with a clear base case and recursive case.
    9 O8 O) E& R2 K) ]# E" o9 w
    ) b, C4 {: s$ A9 \8 bExample: Fibonacci Sequence/ _, q* k' ]5 Q6 _
      V: C1 F0 T8 G/ H+ [4 M# C8 t  f+ H
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    : T# Z) X* {# d8 F: e- [2 [6 i: c# k5 d, f2 e0 D/ e$ |
        Base case: fib(0) = 0, fib(1) = 1& a: F$ ^# T) Q4 e$ R" g% A

    ) K) g( q6 ]2 j/ t9 A    Recursive case: fib(n) = fib(n-1) + fib(n-2): a( q, V2 _& h& h+ o

    ' s1 a, a4 n/ B$ W4 f- }python, d6 H5 s0 \$ m$ D% b* m
    2 v7 r0 Y  h8 P
      A6 j# j; m' a& }( U
    def fibonacci(n):
    % n; P, o- @. `! g3 N, e- V2 _- j( L, Y    # Base cases0 w2 G5 K; I) W- j
        if n == 0:
    / q# x1 ^6 t! W' e1 t) T, w3 _# }( j        return 0
    & Z6 E' O+ R$ r( Z    elif n == 1:
    , i& u+ Z* s% w1 }" J* J3 c+ D# I/ L        return 1
    + M! o3 S0 u6 L1 H+ A8 o( [, J    # Recursive case) U3 K! ^; e6 p; z% d" O
        else:
    : q# m& a3 l& a" A" v9 }* Y        return fibonacci(n - 1) + fibonacci(n - 2)4 u$ k+ v: i* f. H
    - K" o  w$ D5 h8 E
    # Example usage
    ; s3 r" W2 K; a; d  Jprint(fibonacci(6))  # Output: 85 A- n, ]  @. X! l& x

    3 k* B( k2 t) r3 Z* |7 F# _Tail Recursion
    $ X4 W- a' ~# @9 W1 H6 O0 Z0 g1 y  [% \2 A7 a5 u- Z) ]
    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).% w/ s. I5 P6 S6 d
    ; C% c: ^: Q( X9 j! T( o
    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-12-11 05:04 , Processed in 0.031388 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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