设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 & a- Z, z5 ^  r
    5 G" i% H* `, w! O! H, H
    解释的不错
    1 R  |( @/ L( C0 A, E6 [% V
      ~1 H. d- K4 C4 I7 W. ^" |0 ^- V递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。4 A4 O7 b% P& U/ k6 x& y9 q% O
    # Z/ {' c/ P. E2 w8 ^' Q
    关键要素5 Y3 d# O% g; h" B( H" K1 N
    1. **基线条件(Base Case)**
    : o4 S; X: k- ]5 U  }   - 递归终止的条件,防止无限循环
    , a7 n8 m$ u3 |+ q, C+ a0 _   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1- g* G2 D7 g8 f; P, M; @5 P, ?; S1 W

      E7 W. y# Z- C1 Z, g, }2. **递归条件(Recursive Case)*** J  n2 l# z0 v0 e+ M' f
       - 将原问题分解为更小的子问题
    2 V6 ~' L/ r# r' Y2 Y" M; y   - 例如:n! = n × (n-1)!
    % O: q) m8 @. X
    6 Z) m/ b! |$ ]' L% c4 o+ P 经典示例:计算阶乘! ?" b8 e8 `7 Y* K% r* B( c
    python
    % C) Y& }/ A' d  V' L" X% v7 @( cdef factorial(n):
    6 ]3 V) s) }0 `# H    if n == 0:        # 基线条件& O2 H" N! ~1 |: e; [& i0 z1 ]- ^( c
            return 1; @' W4 V+ l! H( M+ i2 ~
        else:             # 递归条件
    / W9 K8 X( ]! M0 f! R4 N        return n * factorial(n-1)
    1 I. M6 I( ^8 |: X( o执行过程(以计算 3! 为例):
    . E+ O7 s# A/ Q! P6 H  Y4 J5 Afactorial(3)- M* Q) }6 F  W0 m
    3 * factorial(2)
    + X9 _! [+ {3 |! c/ z3 * (2 * factorial(1))
    & k* u5 A. U" q+ m$ r$ X: c$ v2 y3 * (2 * (1 * factorial(0)))
    8 U0 |# ]1 S5 d: ~3 * (2 * (1 * 1)) = 6) ^* ?  s0 d( t2 z/ e, p

    / e% x5 u* @  y, U7 S) K 递归思维要点0 _8 Q7 L: l9 b  [* F9 e4 `
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    + k* s* t5 y; S" `6 J3 ?2. **栈结构**:每次调用都会创建新的栈帧(内存空间). n0 f3 Z5 Z. J3 O& h! @* p
    3. **递推过程**:不断向下分解问题(递)0 p, l2 A2 n: G$ H$ p( }( _) T8 {
    4. **回溯过程**:组合子问题结果返回(归)7 j( F$ K- W- h. x+ Q
    ) Y! ]9 V9 Y  D9 X' v8 _
    注意事项
    ! F" n; G# F7 q% ]必须要有终止条件$ _9 H# z* t8 h) p2 x
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    * [8 t7 z# j# o6 g* V+ a" r某些问题用递归更直观(如树遍历),但效率可能不如迭代( f+ w3 p% N+ }6 L: ?
    尾递归优化可以提升效率(但Python不支持)
    ; u- Q9 ?8 m" w
    $ g& `& l% J3 C+ I% Y5 o9 k 递归 vs 迭代
    + k8 F- y9 I& K8 \- T! Q( x|          | 递归                          | 迭代               |: e9 S1 g9 K, @# c" o% i4 g
    |----------|-----------------------------|------------------|
    + c  \: q9 h. \2 f9 p/ z' O! n| 实现方式    | 函数自调用                        | 循环结构            |
    + R4 t$ W4 e2 {4 }: C$ Q3 P! C# s| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |. {' X5 l4 [# H9 L- d
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    + H- i* q8 v; V$ p, K9 Q| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    , v, ?6 G& Y" S. h# Q; \
    / J: W) C5 S$ b' X 经典递归应用场景; O; s6 l* x- D8 y# f
    1. 文件系统遍历(目录树结构)
    9 @; M3 Q( B- F1 x4 g2. 快速排序/归并排序算法' }3 c5 b3 u. _$ o/ x
    3. 汉诺塔问题
      i3 l" E9 j" z, A4. 二叉树遍历(前序/中序/后序)
      ~! j  O3 A  z% ]8 l5. 生成所有可能的组合(回溯算法)
    / [0 ^" o# @, V$ h+ B# z, K" F6 N
    5 F1 ^: ?$ G0 F& R3 {+ h/ f! [试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    3 小时前
  • 签到天数: 3142 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,( M4 h6 I: }1 ^1 h% w
    我推理机的核心算法应该是二叉树遍历的变种。% p- }, ?% [, t2 h& f7 S
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:0 m' f/ J5 x! |( R4 y1 G
    Key Idea of Recursion- x5 W/ ~, ~9 w) r& Y* h8 Q/ S

    2 |3 j1 o" U; [8 LA recursive function solves a problem by:
    & Z# p( d* s* `5 ~  V
    ) c$ P! t! m# T0 t& k    Breaking the problem into smaller instances of the same problem.2 x: ]6 t6 R" I. X
    4 }9 h* K. k7 A; m7 @
        Solving the smallest instance directly (base case).
    " E1 w) M$ S" F, V% P3 q9 ?; q( o7 H* U9 f" e* N7 |$ G7 R
        Combining the results of smaller instances to solve the larger problem.: s' E9 F) i; o( v( k5 @& S; y

    * d2 P" @0 W+ m# d% E) q; [7 j1 ~Components of a Recursive Function5 c6 \7 c% R+ ]6 }. r* `

    ) R$ X% ^% K  {- x/ R( ?+ Z    Base Case:8 F1 O' y2 `! o2 R# ~

    # y# P: Q6 h- q  t        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.8 h( N4 `/ X# l
    - S  o: V; Y/ d5 k
            It acts as the stopping condition to prevent infinite recursion.
    ; H7 ^% c; N0 M7 l+ M* f: ?  y( f; J5 G  }, ?$ V/ b6 }
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.: ]2 _) u# m, S7 z- V

    5 [% t1 o2 o* x    Recursive Case:
    3 v4 ?$ y' K8 G' s3 ?, n) @! r2 e
            This is where the function calls itself with a smaller or simpler version of the problem.
    ( r" l: r9 g; [* z7 q( G
    7 n/ Y9 d5 G5 {6 [- m) ^- A        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).$ r4 M# v+ y* U' y& ~3 k; y

    ) ?/ S0 `- F: A# j% t4 iExample: Factorial Calculation- j, {+ l; {1 c9 ^9 H' o
    0 V+ i4 N2 \$ E1 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:
    1 [, D5 x5 |# ^1 r2 x3 q! X. I# F; u: e& M3 D* p: J& x
        Base case: 0! = 1
    % B* Z+ b% F6 Q# _8 y) e, G# z" _1 K) ], b) @
        Recursive case: n! = n * (n-1)!
    8 A$ L3 G8 ~% y/ L( a
    ; J" U! e: J$ J* r" F# _Here’s how it looks in code (Python):
    - A1 w4 i; f5 opython
    6 }/ B  u* v( F+ G. ?: i& o3 m3 P; h, v& |/ e0 I  z5 l

    1 b0 j1 _- f$ e3 m2 d' Tdef factorial(n):
    3 ~; w0 b8 I. A3 @. J    # Base case
    * u" ~7 ]( A; E0 x, W0 B0 Z. }    if n == 0:
    & \- r" y' K! q        return 1
    4 a- p& U( O" b1 ]# k+ O    # Recursive case% G% P: {  r5 O, F- O
        else:) A! t% L$ N4 T
            return n * factorial(n - 1)
    4 Z+ s; W$ S! G, d3 I$ A5 C
    : ]; T7 F  |  \& L! {, P/ {# Example usage* A" D- Z/ U$ g9 U4 d
    print(factorial(5))  # Output: 120
    3 ?# r. \  p- [0 q# X
    " J0 s' P, A2 J6 WHow Recursion Works4 K' f% n' W$ L3 G6 f
    * ^4 _; i4 e4 r) R, Y
        The function keeps calling itself with smaller inputs until it reaches the base case.
    * V* x% n/ w7 J0 M; {5 X/ R
    4 w4 d2 h/ v. H. r% V9 N0 u    Once the base case is reached, the function starts returning values back up the call stack.
    3 Z$ w/ F. K8 h2 l7 w- N3 [* A9 T) l
        These returned values are combined to produce the final result.
    4 \/ c% P; c  ~" f5 _
    , U+ F3 s, O4 e! Y8 tFor factorial(5):( T& r  C9 u2 Z+ w; l( s, f

    8 c& p6 b# L1 w4 J0 h1 ~/ B
    + I' n2 Q+ y& n. ~4 m  ?factorial(5) = 5 * factorial(4)
    * q  [, p  V7 Z% x, [# efactorial(4) = 4 * factorial(3)
    # y3 v: G( C( Pfactorial(3) = 3 * factorial(2)2 Q* s  C0 p+ a! k6 ^- b
    factorial(2) = 2 * factorial(1)3 m7 u6 T0 p4 j1 R; ^& g' U
    factorial(1) = 1 * factorial(0)0 ^5 _6 n6 Z7 a6 K' w
    factorial(0) = 1  # Base case! i! k2 s# U! U& S, i  ]& p# ?
    : g2 O' K4 i$ R
    Then, the results are combined:
    1 b; b2 R/ k; D
    ' P' j' @4 y9 B8 E5 j! h0 I5 B3 k% n0 I8 z  x; U
    factorial(1) = 1 * 1 = 1) v% _$ @$ x& F( n* V
    factorial(2) = 2 * 1 = 2
      h. F- v' Z+ Jfactorial(3) = 3 * 2 = 6
    " N$ X4 N: n( _/ p0 U% N; `  a( |factorial(4) = 4 * 6 = 24
    ; z" F* y% _6 T1 N: tfactorial(5) = 5 * 24 = 120( ?$ K9 {- c6 O2 H
    ; D. X, b, {5 c% O' G* Z7 d' S# F) l
    Advantages of Recursion
    * H7 O9 t: [! R& d3 C
    ; ^3 ]7 i- ]( B. s4 j    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 \6 n5 m8 m) g, Q
    ; Y3 S9 n8 E# A- c    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    1 b2 ?. x/ @" Q: Q! _, X
    - t3 p. \2 }, z. V' p! v$ W. i$ VDisadvantages of Recursion
    3 i& z3 E0 E1 J( A
    : R7 d; N/ c1 Q3 F/ n$ @    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.
    % x$ D& Q+ v" K, U, a9 u$ I3 y( S3 l5 X2 `9 T, Q/ i$ Z! x
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).4 i1 b- f4 M1 e
    . B, h- w1 ^8 c9 m& _' m& B  o
    When to Use Recursion! s, R" l3 W4 z4 r5 b6 ]$ {
    0 d- E" m0 _8 l& W
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).6 d$ b6 ^& D2 k) L$ _

    4 f% }# A: c% O% I- a1 g    Problems with a clear base case and recursive case.  P" ^! ]& j$ [7 g6 ]* f/ T
    , _* P! H0 H8 u: b
    Example: Fibonacci Sequence; H* H' f3 z4 K  O( o

    ; R1 {: B% _  I7 Y# U& J! D0 mThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    8 l* b. q7 c& I3 i0 V
    : _) o! E* M0 o" n+ q5 h- z/ k    Base case: fib(0) = 0, fib(1) = 1* j, v# Q% w1 y
    9 e' x1 c# y# Y$ h7 C8 s3 i
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    # w( X) J8 C% ^% K  D& h1 {/ ]$ i. ]1 a: d4 X/ i) }# M
    python. s. p4 w# W! `7 J
    4 V5 A/ D' x$ K; ], N& r
    + [% A) @- _! [4 f
    def fibonacci(n):
    ) f3 h3 ]( d/ J4 I) {    # Base cases. B0 ?- h; W0 c" I  k
        if n == 0:
    5 S3 x! D* f! W5 Q% P# c        return 03 [) \5 F7 R! p$ e
        elif n == 1:
    5 @( ^& ?7 T/ R0 h' v3 G9 z        return 15 _; s7 w0 o9 Q& ^$ d4 |, }
        # Recursive case
    0 }. k7 Q! x2 z) s$ I    else:
    5 A8 W' K4 B6 p+ @! a8 K        return fibonacci(n - 1) + fibonacci(n - 2)
    ) E/ b8 c+ d2 [  l* a  A1 X( ~. j# g
    # Example usage  w: N* k* v/ g1 J, {: l( Z8 X
    print(fibonacci(6))  # Output: 8
    , [4 n0 [; L- R: r3 o- |' _" R8 b- A. [/ h2 f( Z
    Tail Recursion
    # B, W* }$ S1 G7 P; R* {7 ~6 [
    2 k+ Y0 a& r) c9 O# {: \; a! V) |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).
    ) E( F6 C% L+ N7 p- Z; |8 F- ?# k
    / m6 M, B7 I/ B9 [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, 2026-1-10 10:47 , Processed in 0.038782 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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