设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 1 S0 L6 X% D" O: f

    ( `4 A5 ]$ }5 s解释的不错9 `1 X0 Z0 D3 g; E& c

    + s0 b; T" b' P递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    2 n; ^) G" k, R) r: `% F: P5 T+ t' K8 Y5 k0 @/ d) a
    关键要素2 f' ^) O. ^3 B4 I+ p+ Z9 U
    1. **基线条件(Base Case)**& Y8 x, y. ?$ N5 @3 x, ]7 `, Y4 b' i
       - 递归终止的条件,防止无限循环1 T( v* i3 p- @, k* X6 x
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 17 _$ y- y. S3 N
      A4 A. x2 F/ p9 I4 X4 H" q+ p, d
    2. **递归条件(Recursive Case)**% Q4 S- Z5 s, E+ r# k
       - 将原问题分解为更小的子问题/ v1 x$ F: R) X+ e9 x* P: F7 a
       - 例如:n! = n × (n-1)!9 W* P. V: o. L8 L1 F
    , v- q  w+ M+ H( E1 v2 I8 j/ ~
    经典示例:计算阶乘
    8 I2 J0 ^' b& A4 zpython
    1 I! c! K+ @+ z% j$ X5 a: Ddef factorial(n):
    5 D, h) t4 b+ m    if n == 0:        # 基线条件
    - }# [1 l# B2 E        return 16 U+ L1 L. p8 J: l+ O- a* j! l0 _
        else:             # 递归条件
    9 m, Z. D4 G# G. M# T8 P4 G        return n * factorial(n-1)' @( j7 Z. P9 C# U7 u' m2 \
    执行过程(以计算 3! 为例):9 o0 @& u6 P7 A- E0 I% m
    factorial(3), V1 M) u6 F+ ?  w& W- n1 _$ Z
    3 * factorial(2)) _* f# t# K7 ~9 M" n
    3 * (2 * factorial(1))
    * |1 f# K7 z2 q; f1 m: {3 * (2 * (1 * factorial(0)))# l" L; ], @1 U! [
    3 * (2 * (1 * 1)) = 65 i. J0 A1 }8 g' k6 S; {. F7 X

    - j5 [1 Y) R, ^# q  j+ j  i7 p 递归思维要点
    8 F/ Q" L+ x6 ]! _: B1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ; ?5 G1 q9 {8 W9 q. ^3 P2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    + J$ G: R. T" C; v, A5 c# ^3. **递推过程**:不断向下分解问题(递)4 c8 n4 I( u% P0 X' I+ c) n
    4. **回溯过程**:组合子问题结果返回(归)* T% p. u/ O; r2 u6 [6 Y7 P8 k

    # l$ n9 z. O- h, P6 F% H5 M 注意事项
      W- [. M2 F1 O$ u- c' z+ K; {必须要有终止条件  a' D# S( L/ l6 ^$ q  L
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)" m6 @8 @0 @: V
    某些问题用递归更直观(如树遍历),但效率可能不如迭代# U1 `% k8 p# v# j  v2 g. J$ ^/ W
    尾递归优化可以提升效率(但Python不支持); `$ _2 F3 p. ?. p- f

    ( w$ L+ c9 x- u4 Q" ?$ F7 k 递归 vs 迭代2 g3 K  h- T+ p1 d3 y
    |          | 递归                          | 迭代               |! K6 d- v5 y& X9 T
    |----------|-----------------------------|------------------|3 j4 \( {( @- s$ U; @$ A" @) y. h
    | 实现方式    | 函数自调用                        | 循环结构            |
    . R. q4 I7 H, n3 k| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |0 B8 @. `  l. S
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    7 q( W& m; Y/ I| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    * K% B  a) x5 O# G
    " ]" p3 `7 S' O. F3 { 经典递归应用场景
    * ]7 [5 B7 B+ w9 D: j5 h1. 文件系统遍历(目录树结构)
    : A+ x( k8 A& S  d% Q2. 快速排序/归并排序算法1 U3 E9 V' g- ^9 G; R# e
    3. 汉诺塔问题
    8 u# A6 u3 y! V* P5 x4. 二叉树遍历(前序/中序/后序)
    ! R. D+ S$ p  H: e5. 生成所有可能的组合(回溯算法)
    ( ?- l7 ?3 x2 A" D) a! Z% k2 @8 w7 ?" u3 g  h
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    难过
    昨天 07:02
  • 签到天数: 3221 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,5 N! a% k# v) z5 K% P0 e- x# d. |: z
    我推理机的核心算法应该是二叉树遍历的变种。
    1 V% s1 G; x. }) Z另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    % v/ {/ p5 a5 K1 K; \5 }3 f8 dKey Idea of Recursion$ X# [0 }7 {0 f4 ^" V

    ; f" Q$ z6 N) o1 l7 k; J4 G  b1 RA recursive function solves a problem by:  u9 D8 K+ s! s
    8 R+ }( }; D  k7 f% O" `
        Breaking the problem into smaller instances of the same problem.
    ! v$ L0 W9 \8 R: u- Y( Z
    0 V2 D8 N" {8 k6 I6 a1 [4 A/ G! i    Solving the smallest instance directly (base case).9 h1 l- Y# {, S* h

    ! }. r& j1 j1 W; g$ u5 P$ ]    Combining the results of smaller instances to solve the larger problem.- X( A: z& y+ s

    ! j1 T6 x' M( T. E7 r1 A- ]' t$ LComponents of a Recursive Function
    4 {7 k# s, @+ Q1 f& E' y7 x4 h' R
        Base Case:/ t/ k* S1 V4 r: \5 F5 g9 n
    0 U4 J* a3 p  D; ~# y# L, @
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    7 k: l& g: a& `
    & Y7 _/ M/ j- ~+ {3 ^        It acts as the stopping condition to prevent infinite recursion.) a  F& D  R3 @, N9 B/ S  b

    : a  I8 l3 P2 E5 J        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    5 J/ o5 b& [" l3 H0 `+ t6 o, x0 t% C9 x0 j/ o' q
        Recursive Case:
    " g6 `4 K, p! i! w: C$ H% x2 K. q2 W4 ]) D( R
            This is where the function calls itself with a smaller or simpler version of the problem.
    1 n% @8 L/ h( B' X# H# r% ~, S0 `) k; a, u. F5 J
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    7 m( d1 ?: l  `( b
    ' M+ l9 d  G2 g! z& w$ VExample: Factorial Calculation
    + j3 t) J' u+ }0 \* Z9 X0 K# N) O/ |8 b% x) N
    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:
    ; {/ J# r- H  I. w. _: Q: V  w( n; v# E+ \
        Base case: 0! = 1' h& C7 L' U% O) u

    " d- `/ `. f# T1 v+ d: a3 S    Recursive case: n! = n * (n-1)!% m* W$ @4 m( \! n+ e6 s% x
    8 D3 T4 ^7 ^+ M
    Here’s how it looks in code (Python):
    + ~/ `7 y! p* [- }$ S' Kpython
    ; G! Z; Y0 d1 L8 T9 ]$ J, H. s" S' e& L( N
    ( l. h# M3 \8 r, S% \
    def factorial(n):/ e/ M; \# Q: U4 {  ~; c9 j
        # Base case
    1 p0 P+ k8 o5 q  s    if n == 0:
    ' Y. b5 N4 T2 f/ W# }: O3 Q8 m0 Q        return 1
    + w' q9 A* @, H    # Recursive case  t. U+ G# Z4 f
        else:8 g: T# s: v- I4 U" h  j' @7 Y
            return n * factorial(n - 1)
    7 w& G9 M& K# \6 e1 c, v9 x4 q& {
    , H& Z% E; b2 _$ H5 Z9 V# Example usage/ U7 w# a! C6 R! m
    print(factorial(5))  # Output: 120
    9 O8 N4 q( J0 n0 Y2 I0 Q
    2 O, J3 [, V: Y: mHow Recursion Works
    : J4 V$ R! b2 w9 w
    9 I7 q- b, [3 w' a0 s    The function keeps calling itself with smaller inputs until it reaches the base case.- E. J( O, P( y0 y& V( g
    . `6 ^- M3 f3 V( [" d* u
        Once the base case is reached, the function starts returning values back up the call stack.
    ' _9 O2 u+ b% c
    $ k' T: L# e  K+ c    These returned values are combined to produce the final result." l% a, S% X7 A8 Q
    . W" v. s# m! }
    For factorial(5):
    , X- k5 M' l7 D) B+ {) T1 }5 h; L/ ?" F! y

    ( O" e6 w7 |' {+ n& s. }  Jfactorial(5) = 5 * factorial(4)
    - a, t* n8 |" S+ T' k0 {! @factorial(4) = 4 * factorial(3)
    9 g. v: I- k* ~- L/ H3 r- Q+ Pfactorial(3) = 3 * factorial(2)' H! w1 n; p/ ~) J
    factorial(2) = 2 * factorial(1)  r5 y: E* u; }0 I/ y: Z! g& W2 h- N
    factorial(1) = 1 * factorial(0)9 `" C% S0 B- ^" f+ Y
    factorial(0) = 1  # Base case
    4 F/ C8 Z5 P! V3 v) [
    + }" }% o0 s% QThen, the results are combined:
    + q; r( L6 o0 u+ n) o5 M. z# A* Y
    ! ~9 v/ O* z. b$ `% N6 T6 N$ C3 d, S
    2 W2 p' W, F( u* c1 O1 j& b" ^factorial(1) = 1 * 1 = 1
    / _  E( v% b: p% T5 @2 M8 k% [factorial(2) = 2 * 1 = 2
    ; ~4 J( P7 _1 l1 s" D5 Nfactorial(3) = 3 * 2 = 6
    0 Z4 F( w8 X$ F, a  ffactorial(4) = 4 * 6 = 24
    0 R9 G2 s* {4 T, H+ r. Y0 w7 Afactorial(5) = 5 * 24 = 1205 h1 O8 q: ~1 W

    # l+ y% q* @: sAdvantages of Recursion
    ) M. x. }2 ?. M- k2 _7 D+ M
    * ]) w! }& v$ a, |5 @. w    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).5 A3 h7 f2 q  u1 D' w

    ! ?7 F5 ~; M$ y  h    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    ) J4 s  Q% b$ D- i/ G+ S  A: u
    * I/ M) p; `6 p( U! q. m2 DDisadvantages of Recursion- U( V' }' i$ h% W

    & v0 ^# ~0 z* @/ o( o1 s+ 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.& _3 t1 p: W' x/ j1 `
    7 s+ V9 O9 c0 s/ k8 \9 ?# Z
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).! [3 L0 X1 V; x3 R& m& \( d

    , T8 t* j2 p8 W3 VWhen to Use Recursion7 l( o( \( k6 s# m. V$ H) i( P
    / Y6 U3 U( U) M5 w
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).- `: g* s5 L+ R/ o
    * e. i% _5 g- E! P1 Z* p4 R, T
        Problems with a clear base case and recursive case.- e' H8 h$ d2 ]2 L

    3 t! Z, ^+ x, NExample: Fibonacci Sequence
    8 g8 y7 T2 a$ P+ q' l3 c
    & u# j  b  c7 X) T% [& j/ V* x$ iThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    & Y' Q% ]% X6 K! P4 i' b4 P( x3 }' e5 Q
        Base case: fib(0) = 0, fib(1) = 1
    2 s0 M/ u3 E1 E8 S* K+ F8 x- V( B1 l0 M: C3 l% W' ]. S
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    7 W4 n6 y) n; }7 |5 g' x4 A0 ~6 q8 c4 \5 Q, P& _: h
    python5 A5 B2 P! V; z+ H& @) U2 \

    0 j, V: E5 [6 K* n  r6 X+ J8 n  s' [; E+ d
    def fibonacci(n):
    " F4 T9 A8 V/ ^- N, v: y8 n    # Base cases
      ~& ~+ O: Y( W# j/ q: \0 M    if n == 0:
    4 @( M+ x+ E$ O0 I' x0 e6 S        return 0
    ) r/ O. n8 F( |2 T. n* @1 R7 `8 B    elif n == 1:
    7 y# p5 j2 v1 Z8 T( v        return 12 W$ g3 j4 o5 @
        # Recursive case
    7 [' x8 _* e) `: Y6 N    else:0 U1 h+ r2 a' S# S4 @' O! l
            return fibonacci(n - 1) + fibonacci(n - 2)6 a" m" Y! @5 S4 I# o3 p

    8 s" t0 Z. ]' @0 y& F; t# Example usage
    ; O9 S2 |7 B7 Y) q2 r" Kprint(fibonacci(6))  # Output: 8; I3 F* b& l3 }  W; m2 ~; h

    7 H6 g( m: v0 I% |7 UTail Recursion
    ( t% v- r2 M% R. V) n5 p% |
    6 b: `* W5 ^0 \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).+ \7 c6 m4 H. J) d* H
    + }  i( @9 |# p$ A9 O; ^/ M
    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-4-23 01:36 , Processed in 0.064888 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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