设为首页收藏本站

爱吱声

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

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

[复制链接]
  • TA的每日心情
    开心
    2015-11-30 11:11
  • 签到天数: 2 天

    [LV.1]炼气

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    9 B- \5 h$ K+ Z6 c2 ?$ v: d5 [% \; q. m6 q* n( M
    解释的不错
    8 a* b, Z) N# b
    ; A0 m+ E$ Q6 C) o# K/ \, D0 z) u递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。$ ]8 E! D: i: ?+ H+ \
    9 f3 q6 E0 [8 v9 i9 D" L
    关键要素
    - s% m" e' K0 l9 b5 n+ a1. **基线条件(Base Case)**
    * @* F/ X6 h. g: L7 N7 K% ]" L% ]. f; R5 f   - 递归终止的条件,防止无限循环
    0 ]+ B& N! D. W+ ^  N   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 11 _) E" b; b" T2 W; ^3 U+ n
    ; s% p9 p+ @+ Y" B
    2. **递归条件(Recursive Case)**
    3 o9 g- D5 T% N$ P# _' g   - 将原问题分解为更小的子问题8 v- v0 C  l" C* i" V
       - 例如:n! = n × (n-1)!* J5 r+ B7 K% D
    8 Q4 O5 b8 {. W; D5 }
    经典示例:计算阶乘
    2 E$ m# T# F( N5 C! gpython
    / m$ a, T4 D1 A9 z2 k2 ~) Udef factorial(n):
    ( O, M- ^7 y2 d$ O! n: j& W    if n == 0:        # 基线条件
    % L0 Z# {" n3 }8 X( n        return 1
    # ~$ A! k9 T# z6 Z  t6 c3 X    else:             # 递归条件/ L- s" b$ _$ a4 k
            return n * factorial(n-1)
    # K. ^: L# R$ Q执行过程(以计算 3! 为例):
    9 W  Y* M! d5 ?# n" G3 W7 O2 h& pfactorial(3)2 W1 {% \4 Z4 A4 D$ G" x7 R
    3 * factorial(2)
    ' ?1 a1 i6 z7 ]: z: o- \- ?3 * (2 * factorial(1))
    ) d: q; U  j$ W! y# R3 R0 n) W3 * (2 * (1 * factorial(0)))
    % J+ b; i$ b, Z/ X3 * (2 * (1 * 1)) = 66 H3 Q  L6 [1 e; a4 I- I7 T& J
    ; z- E4 ]( m- S- j( n2 O& ?
    递归思维要点0 L* A/ M- J0 ^6 H$ q4 R5 ?  @. m
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑7 D' W1 J; [* @2 x3 w  p4 G/ C
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)  [7 _9 J7 L& P; T- b
    3. **递推过程**:不断向下分解问题(递)
    , f# o; U, f  y- h6 e  [4. **回溯过程**:组合子问题结果返回(归)
    7 l9 A0 C; q3 g0 u- P' d/ `7 m
    8 Z5 r! F3 C0 }8 q- n 注意事项2 P6 s# O0 S$ ]/ `$ C
    必须要有终止条件6 u, s5 ]: u3 s  ]- z& b
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)0 `; h, E) D; o% f# a- Y
    某些问题用递归更直观(如树遍历),但效率可能不如迭代4 k, @  w9 r) i6 G* V9 {
    尾递归优化可以提升效率(但Python不支持), [4 w0 w8 y5 |9 r  N
    * U  p/ ^/ V- G, t2 y; D" N
    递归 vs 迭代3 d$ ?/ L: L* Z6 x0 L. w2 B" J
    |          | 递归                          | 迭代               |
    " A9 i8 z0 ]4 \; z3 c) {2 \+ D5 E|----------|-----------------------------|------------------|+ \' X. O. C8 ~5 }
    | 实现方式    | 函数自调用                        | 循环结构            |
    % G# `1 g5 A' G6 u  Q0 T  r| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |( |* a, V- F: s
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    * w. u& |- k, D0 Z5 [6 m| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    - n/ Y3 U; k5 d3 d/ o
    " v1 @$ B" q/ a 经典递归应用场景/ \# N1 C* _; r% x- D! m( B0 u
    1. 文件系统遍历(目录树结构)
    $ G# j& q: _: y! _& o  E2. 快速排序/归并排序算法
    3 f5 l  Y) b# t) f* f) w3. 汉诺塔问题
    $ J2 I% ?) m3 l$ L4 Z. t& W; i4. 二叉树遍历(前序/中序/后序)
    9 c2 t1 Y% s# y1 ?; v$ i5. 生成所有可能的组合(回溯算法)6 e3 w+ p, U4 Q4 Y4 [  a

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

    评分

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

    查看全部评分

  • TA的每日心情
    难过
    23 小时前
  • 签到天数: 2977 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    6 T7 B. f2 N" }: l) p" C# x3 m( |我推理机的核心算法应该是二叉树遍历的变种。
      ~9 W/ d8 I4 n6 u/ q/ i另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    / z/ ]9 j2 S0 S6 b  pKey Idea of Recursion8 P+ w% f$ e$ I; ^' x

    9 t6 \) a# C" A6 nA recursive function solves a problem by:# N! C1 E# s7 h. e4 u, P1 ]0 f
    ! B) {, b8 M% l6 S" d; X, u
        Breaking the problem into smaller instances of the same problem.
    6 v1 n7 x& K* w% O1 S8 [' y  m4 N4 k
    / r6 x% k* p* d" I* I    Solving the smallest instance directly (base case).
    # N) G9 ]# L2 p: F* t/ A7 U; I
    $ ~) O# S# d! @% ^# m% y    Combining the results of smaller instances to solve the larger problem.% L" o2 Q6 ]' Q9 l- n0 N
      s# H% R& z3 j
    Components of a Recursive Function
    4 B$ @) g. ^! h. Q, |5 z2 P6 B
    ' C( K( D9 E& S/ X" w6 Q    Base Case:
    / i+ V4 A4 ]7 F% e( f) v. i
    3 n/ _0 J; ^! x- }' M        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    & t0 L& y# m& J! v( D$ D
    9 X0 g- u2 ]* K) p        It acts as the stopping condition to prevent infinite recursion.3 r& b4 u9 f$ s* a9 Q7 Y; q
    9 _* R% R/ ~  P
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.! B- r0 r6 F& s6 f

    2 b7 o# O2 K" L" j9 L- Y0 L" Q- n    Recursive Case:2 K# A4 N) T1 e0 O2 ]
    # A5 z  Q: L3 X3 |( b2 ]0 F
            This is where the function calls itself with a smaller or simpler version of the problem.
    5 w2 z3 s& }3 j! E3 g
    $ O1 }0 r8 }1 P. B2 t        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).8 k# V8 [% y* V; z. d' e7 x' w! D
    # S; p0 g8 T1 |2 |& I
    Example: Factorial Calculation
    5 B' \* A: O1 H; ~
    ( O4 q/ O- R& \! w% q2 fThe 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:
      E0 T0 e- }9 Q4 h
    ( t2 j/ Y/ j) N/ u" A9 @  J) F    Base case: 0! = 13 h9 ~. D0 K' N4 N2 \

    1 y) P3 s+ ^7 ]* p    Recursive case: n! = n * (n-1)!
    : `' s( o8 o# x5 y7 ~2 T
    0 i& D+ A" N0 g9 aHere’s how it looks in code (Python):, F% {9 H0 Q8 K/ E1 }
    python
    1 h( b- Y! \: e# P3 q  u' L. K1 o; h& k4 S' p8 g- z
    4 S7 D+ Y& F! q; ^8 b% h- s
    def factorial(n):
    . ~7 m! J4 m! H6 B    # Base case7 c$ s: @0 v4 B8 F1 M9 Y7 I
        if n == 0:
    , [! O; ~9 W: h        return 1) X% b6 E% C! d7 o
        # Recursive case
    . W+ y3 h! A, z- u% A    else:
    2 K1 S+ s  I" W+ O/ m        return n * factorial(n - 1)
    ) s3 v' f" g% Z: a2 A# C9 e2 n6 l, T
    # Example usage! r: |3 ~/ _' c3 q* X5 W. F# o
    print(factorial(5))  # Output: 120
    # c/ X8 r' L/ o# x9 u, D# }* }9 N, F; l# R( \
    How Recursion Works" n6 @. `$ Y1 L& {: @/ m

    & q! W( q1 V$ P: d. ?% x0 Q    The function keeps calling itself with smaller inputs until it reaches the base case.: {2 T- z6 D( P2 \& i  ~. Z
    . V; i9 @7 h; [- [$ j
        Once the base case is reached, the function starts returning values back up the call stack.$ a+ m" @5 w+ [% L% D( E6 c/ v2 a
    / w- P* _6 k' W
        These returned values are combined to produce the final result.
    % i$ s, L% i5 g  H
    5 R( o1 b9 G$ _. F- _For factorial(5):
    ( S% U  _( ^7 ~( n/ A3 L# [; r! M. L
      V. W5 h# E+ m; r3 @" y8 M
    7 ^. G2 I/ W- cfactorial(5) = 5 * factorial(4)! z+ u% H' U# i5 g0 t: ]
    factorial(4) = 4 * factorial(3)
    ( z- R0 j* ~3 p; Yfactorial(3) = 3 * factorial(2)9 K2 _. ~( K3 n' t7 |. R) V( U
    factorial(2) = 2 * factorial(1)3 P! \8 h6 M) d; F. y4 Q
    factorial(1) = 1 * factorial(0)3 t8 @& `* H* y
    factorial(0) = 1  # Base case
    $ m' j0 b) q2 s* s* B
    * g& \7 O( l% k3 eThen, the results are combined:
    5 h+ w( }! N  S0 [2 W
    4 b) z2 x* p9 I. [; O  T
    + a$ j$ ~1 A! y9 P9 afactorial(1) = 1 * 1 = 1, H* d$ o- Q: C6 |
    factorial(2) = 2 * 1 = 2
    , Q  G& i7 Q* p- A. ?" a, Q* Y/ sfactorial(3) = 3 * 2 = 6' f& M9 x7 Z, B8 X9 [! v1 I
    factorial(4) = 4 * 6 = 24! j( S& j8 I- |9 l. b$ j2 W6 `
    factorial(5) = 5 * 24 = 120. a% C; Q& S' _: v

    . I! `1 L! E" pAdvantages of Recursion
    / v3 @/ C# o1 |% x  I7 K: G8 D' H1 u; y& H  ~% A+ L$ Z- y8 L8 _( P
        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).
      s) e- t2 q- a% b' M+ D( o( y
    ) {8 L. o2 Y8 |: t    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    ( Z$ q1 ^! l$ n( I* i. O, E! r# i5 m" R/ K: N  N- A
    Disadvantages of Recursion
      U$ d' R- F% f* |
    ( y2 A9 x- D+ Z# K% M    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." |3 w& Z9 _2 q3 v1 P* e

    % S( Q" r2 ~& ~4 [# ^0 N$ I    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).5 v) _# D4 P7 G4 N6 E1 ?6 T0 o

    ; d/ S3 G+ D% t& }4 eWhen to Use Recursion
    3 e# N) D9 G9 c: m) F
    , ^# K; _/ K, D9 d# g. a/ O' s2 e# ?    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    ! @) u  G& c. N- k; f  t1 u9 g" E( G& y' P
        Problems with a clear base case and recursive case.
    + r7 l: j/ E8 p2 c( P# A. q8 S) }+ d/ l8 i. x. b" N) G4 J5 r& J' r
    Example: Fibonacci Sequence
    : w% |* C& G2 q; a; G2 b: [8 g, Z3 C: z& T1 H6 H. ]" }
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:/ Q5 E8 y* g  S+ z9 V0 K

    , r7 T0 A% k7 s- n- b& z$ l- N    Base case: fib(0) = 0, fib(1) = 1
    ! v8 A: ?2 L0 k# ]/ @, R* x6 B* Z# Z, A1 @* R4 g$ V: g
        Recursive case: fib(n) = fib(n-1) + fib(n-2)/ b( O, v1 a: ]* }0 M& b( O, s
    3 t+ H1 Y- L* y9 i
    python' x8 |- H/ V' v2 U3 i

    % A( ]6 \8 J6 p
    9 t# Q- l& U' }6 }, udef fibonacci(n):0 `  X$ f1 l2 w* \5 \
        # Base cases  ]: c" C  ~$ [$ g1 P2 p
        if n == 0:
    . Q. K, A4 ~7 i% g/ G        return 07 @2 \2 ]5 y3 d) e* a3 J, \7 M
        elif n == 1:% s4 B" x/ a! b2 s. O8 l
            return 1
    9 r2 B/ g- H0 z$ k" O2 Z& X    # Recursive case
    3 z  N. I% ^' r' v$ a  F    else:
    3 @( s6 L- M9 o9 Q        return fibonacci(n - 1) + fibonacci(n - 2)
    : u& C( [# h# b7 c- U+ ~, n$ h- ]) O
      w* U& Z0 U9 N+ H# Example usage
    - I% Z' I  Q# D/ t3 X/ w7 |" uprint(fibonacci(6))  # Output: 8$ e! b7 q( R+ X) X+ s* b

    % j7 S' L4 r/ C1 l5 y5 h! i' lTail Recursion
    1 y5 k0 G/ i/ p: `4 A: X
    " t0 E/ G2 ^; F2 l* e, [7 t7 ZTail 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).4 R5 M9 X! f* {' v0 x
    ! q8 m+ e% p) K4 z
    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-7-12 23:24 , Processed in 0.050934 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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