设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 . A( A: ?8 ~/ z
    # p% V& J. x& U0 }
    解释的不错
    " C( m; W+ b/ [9 b; d  Z& ?) \5 M" j% g0 Y7 M( H* Y* ]; I$ l
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。; D/ W1 ~* n" d' F
    " ?$ H4 K5 E5 ]" z5 D2 B5 E* S
    关键要素( U) P/ o& n) _8 o( h2 W1 x6 Y
    1. **基线条件(Base Case)**
    , w5 v! b; M5 u0 ~3 A$ ?( ]   - 递归终止的条件,防止无限循环, u! @0 G9 n( W: ]
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 15 T* ~1 `% L& h& o. H1 c( x! Y
    ( v5 W6 W* S/ ]% u
    2. **递归条件(Recursive Case)**
    7 s7 p% f: I5 I2 Z' Q  P+ d$ T   - 将原问题分解为更小的子问题
    ! _$ t% w' t$ Y/ I   - 例如:n! = n × (n-1)!5 N, `: a2 ?/ H* G
    8 l) D$ ?4 D  p  }5 W& q
    经典示例:计算阶乘
    ) X' L& R# u8 |8 Vpython
    9 [! [/ y5 E' adef factorial(n):
    1 G2 \" d2 X9 [    if n == 0:        # 基线条件
    0 e  t" \  b9 V& V0 h- M        return 1
    2 _* U4 O2 y4 n* H8 G1 P8 I' z    else:             # 递归条件
      R* E$ w8 |( B8 `3 D        return n * factorial(n-1)
    2 A0 J3 L( W6 e执行过程(以计算 3! 为例):
    ! \" Y1 Q6 k% E4 B* Vfactorial(3)0 Z% i0 r% Z7 E6 Y& S" N
    3 * factorial(2)1 C3 m! X" Q: E; u) [
    3 * (2 * factorial(1))
    8 _+ U, O0 `, }& ]! X3 * (2 * (1 * factorial(0)))* h/ f* I# H! Z8 y$ D$ a% A- L
    3 * (2 * (1 * 1)) = 6, A+ l& a; z6 B5 ?. @; j+ M

    : J3 V" {9 K* L 递归思维要点7 W8 g9 b' N# v+ u+ V" V, q
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑/ j3 J5 n; F' ?" r
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    2 l% ^4 z" R7 A/ }3. **递推过程**:不断向下分解问题(递)0 m% l; ^; a8 F- p2 c3 L) k& t
    4. **回溯过程**:组合子问题结果返回(归)
    ! k) L) c3 K4 f: z
    2 C! I+ r! \3 g. t; S. w# g% g 注意事项
    ; ?" u. i" B+ o6 X+ J, o" T6 e必须要有终止条件
    / `+ R& Z0 \; f递归深度过大可能导致栈溢出(Python默认递归深度约1000层)* k, B- k& `3 b; P( u
    某些问题用递归更直观(如树遍历),但效率可能不如迭代( f1 O( ]) o' Q- `. z3 o( W( q9 O4 F+ k- K
    尾递归优化可以提升效率(但Python不支持)
    % Z5 e6 {7 Q0 z9 v) \3 i, w6 A
    / u8 t& m5 x" q" V/ O 递归 vs 迭代
    9 \. i/ J. T$ }9 c  Z6 L0 p) X% l|          | 递归                          | 迭代               |6 B# H( t5 @+ B* B" A# }5 ]8 Z
    |----------|-----------------------------|------------------|4 @8 j  g7 V1 k$ X3 k! g4 N; A7 M
    | 实现方式    | 函数自调用                        | 循环结构            |; T( ^' M& x; c9 |0 u
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    8 K; d* G- \: U0 I4 ]| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |. K3 j( G% P1 V
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    ' J! f+ }+ q# j% q/ F2 C: a/ l* l$ @2 a
    经典递归应用场景
    * N! s3 K9 u- G: Z1. 文件系统遍历(目录树结构)8 H; f$ Q" W/ f( ]" n1 l, W/ N# U
    2. 快速排序/归并排序算法
    & B' u# ?' `7 g  D, {3. 汉诺塔问题
    4 y! G8 N3 o# x! P) N4. 二叉树遍历(前序/中序/后序)
    8 c$ C' ]! y& X% y8 W, \3 ?5. 生成所有可能的组合(回溯算法)
    4 e3 ]/ H6 t$ Z# A/ Z; g9 T8 P7 [2 G4 c( K$ p1 |: Q' t$ ~
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    10 小时前
  • 签到天数: 3045 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,0 J) A" s5 y' ]+ N; a- u
    我推理机的核心算法应该是二叉树遍历的变种。3 T& C8 H8 \! c: N+ g0 p
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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 j5 j' S6 M! N3 Q
    Key Idea of Recursion
    3 X0 x6 U8 D0 Z- q- _$ m( q1 N( ?" o0 W# e' B1 b6 Q1 D" |) l
    A recursive function solves a problem by:
    : Y1 M0 W, Q" b, z1 Z0 K  ]
    - h: C% P; `4 b* Y    Breaking the problem into smaller instances of the same problem.
    - t7 S9 D4 K. f3 O# p" k. p1 j! ]$ U& ~7 e4 H3 @* {4 n9 r
        Solving the smallest instance directly (base case)./ w4 X- G! a4 R7 A
    2 r! ?7 q$ @' F$ [1 g& r
        Combining the results of smaller instances to solve the larger problem.
    0 q/ h3 A. ?0 d6 Q
    3 D0 D* l+ D; M, Y5 W; w9 LComponents of a Recursive Function
    7 b/ b) d) \1 N7 C2 k/ V, Y; z0 i) X$ P4 ?, h$ T
        Base Case:, m) X9 T0 T+ S7 i% x
    7 ?9 ]! G9 R  ~: `, y
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    % w, F5 N0 G  d) q' H6 L
    $ V: H6 i3 f) ~* g2 s        It acts as the stopping condition to prevent infinite recursion.! w, w  C7 o3 B# h( g5 l$ N

    & }& c7 f  ^) N- s9 w# M8 a# |9 M8 p        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.6 k. j+ F& c5 X$ ^! `% g3 |. s# Z

    : c6 ?" P8 b) |    Recursive Case:% U3 X* }! ?$ v, u* J4 Q. M2 \
    ; n8 K. u' L. U5 r0 s' b: _1 h
            This is where the function calls itself with a smaller or simpler version of the problem.* `& M) s% @5 o4 y; D( N- i
    & t6 d3 L5 k. L( v5 m
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    . t. R/ b2 D5 D( m4 j/ G% |% z  g  }! |
    % q0 M4 x, U) DExample: Factorial Calculation
    . |3 n2 G# h4 t+ [# Q7 |( W" F3 X& R
    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:% q4 ^. w2 c- Y4 W+ T2 G- a

    : Q2 g2 R  S* @' H" \9 i, T    Base case: 0! = 1+ V5 z& L8 w- V  e$ I+ a

    ; S' B% r5 [5 x3 ?; I9 f    Recursive case: n! = n * (n-1)!
    5 Y' I* o9 W3 [- s% F& I4 n
    . \# M1 N) J: v  l+ SHere’s how it looks in code (Python):+ ^# m' e; Q8 U1 D1 Q! l
    python+ A& g1 D% I, l( b2 c

    - v% Y, X7 _3 ~" }$ _2 B9 S
    - E: ~4 _% R, N' h/ L& r( [7 adef factorial(n):
    ( e; D% M- k- V7 A5 M1 H    # Base case
    ; `  J. I! M# t5 _8 C. b% s    if n == 0:* U' d' {8 e2 f, T) W
            return 1- E9 n4 u' ~( d8 A# i1 P$ t
        # Recursive case
    : q! Q7 ?. I) L; B. S    else:2 W; j4 l9 u" R/ e
            return n * factorial(n - 1)
    / j6 M6 Q: b; y1 Q0 Q: n9 O6 Q$ b! v. L" ?
    # Example usage  v" D0 R6 z# l) G5 @
    print(factorial(5))  # Output: 120  \, u- n) s! ]/ K, d
    1 B+ s. ~+ k! k% R
    How Recursion Works
    - K' I( z4 x. ]/ {7 K6 z3 C
    ( L7 A+ d. n% Y" e' }9 d# z    The function keeps calling itself with smaller inputs until it reaches the base case.
      _- t7 e; h" ~9 {& F/ V& l/ M" k) t8 s# _+ M( V0 t
        Once the base case is reached, the function starts returning values back up the call stack.6 _, T, z" d& `! \$ _; Z  ]

    ) m/ ]  m% i2 T/ @: n$ X    These returned values are combined to produce the final result.6 X+ t! S5 G5 R+ L
    , \% |* p$ u* Z4 Q
    For factorial(5):6 b" b4 K$ O% p3 l0 _# R
    2 s; Y/ ~* `2 H6 j4 t( b) G

    ( Z2 l$ r8 @/ G5 n/ B5 H; N0 Dfactorial(5) = 5 * factorial(4)
    " [/ }9 j+ X5 l! x: D: I0 rfactorial(4) = 4 * factorial(3)' F7 n. }8 @  ]4 \# O
    factorial(3) = 3 * factorial(2). p7 s" x; S" O
    factorial(2) = 2 * factorial(1)! A0 @5 k; E* s5 n8 Q1 E9 ^( p
    factorial(1) = 1 * factorial(0)
    + k  C3 J8 U: j0 `1 Hfactorial(0) = 1  # Base case
    : v$ w& ]/ L: u- a; b9 m* a
    & h% n2 L+ T( C) OThen, the results are combined:
    ; H# U+ W% L) G. v
    3 i3 O2 ~  Z; o3 p9 W
    . |" {- p& i8 |+ B& cfactorial(1) = 1 * 1 = 1
    2 s* z5 K  @1 W/ D5 n1 Mfactorial(2) = 2 * 1 = 2
    ! C1 z$ h7 {4 ^" ?4 `) Cfactorial(3) = 3 * 2 = 6; ?: c  e3 u0 R; m
    factorial(4) = 4 * 6 = 24/ [# t2 l( [% c# Z
    factorial(5) = 5 * 24 = 120/ B& i5 `. `+ j9 u. b0 S2 b

    . Z8 [$ j; d( G1 z" a* hAdvantages of Recursion
    & B; g, E5 K" Z7 V
    + R( O5 V+ j, f: ], 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)./ O/ I5 W; h& R  O( Q
    4 j9 X( z% T2 U
        Readability: Recursive code can be more readable and concise compared to iterative solutions.5 E# d2 P: o6 ^
    1 h- d1 z! f/ |, X) t5 p
    Disadvantages of Recursion
    0 c% }( Y, E0 N8 \$ u9 {' s+ w, S( _0 ]4 F, 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.
    , V# q( M/ ?& r
    + X* D/ ~# G2 _% w4 J* o* }    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).' y* K$ B- y* D- C- R# `

    % |$ B( g1 S3 n0 l$ L; j! d. w& ~When to Use Recursion
    5 C8 s+ v2 g( a4 d6 z8 h( u! k9 a* [; j/ L5 V) _! k, X, j
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).' @: k( q. G( G& N

    # M; s, i4 `9 G: k, {( X  m    Problems with a clear base case and recursive case.
    3 V; H0 Z) N2 [3 ~% s3 o
    , B; t0 E; b$ ?& L; SExample: Fibonacci Sequence1 W7 w. H, X# P& `; S( }

    * |* `- C5 H- x4 _/ L8 i& EThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:% u' r' b, u- q" V
    + x7 P, M) J0 Z1 I# ^) j2 `
        Base case: fib(0) = 0, fib(1) = 1" J7 h/ J3 L. d! x

    ! ~* \) @! W3 {% e    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    8 N0 E5 G. y' l  P0 q* l; n* b( e6 T" B+ V; U3 X9 j' l9 W
    python
    $ i! H; E4 K* X# a. W& T. `- f4 ]2 H9 b4 P
    1 a6 D: ^9 `; f4 f. n
    def fibonacci(n):
    % L' _& u0 B7 [' m    # Base cases
    6 `3 B! j# `4 |' D8 w0 s    if n == 0:
    ! d1 U8 z% C+ h! p        return 0
    + ?/ O- c3 `+ A2 k* u    elif n == 1:
    0 d' M+ D- c; y  {        return 19 q# K- D0 r4 B$ j, e
        # Recursive case. d) a* v) R, e$ L9 o  j( I
        else:
    0 Q, F) c* }6 @3 K) Z3 H/ R% k- T4 A        return fibonacci(n - 1) + fibonacci(n - 2)
    ( L) ~$ U+ w, [3 _9 l2 h/ d4 D
    $ u4 v+ ?3 W% O; y5 n8 E# Example usage  Y0 o5 L8 W' L* L# s9 U
    print(fibonacci(6))  # Output: 8$ K' r5 G5 }4 t  o7 l0 Z

    - [5 R+ @! x  j7 eTail Recursion5 y3 m% K6 }) V9 ^5 w3 S8 |

    , s, X, r: t- s+ A( P$ U6 t3 eTail 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).8 F/ K) m$ {$ m( U
    0 V; B; Y, s- [* z& }0 H& ~0 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-19 16:37 , Processed in 0.035348 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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