设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    : n0 [4 {9 o/ [5 z. ~9 s! Z8 l. k. [$ k
    解释的不错
    ; G0 }; n& K2 p7 J9 }  J1 X4 v6 W4 c- V: d
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。4 ^# o2 D5 S  t1 t( j& Q, D

    , C  c( x) u" A- Z% s% E 关键要素) p) c3 A% W$ y8 [+ D, W
    1. **基线条件(Base Case)**- j% Z: s  F/ _  ~- R5 `; u! R; y
       - 递归终止的条件,防止无限循环+ Y- \' F. Y* b9 ~& Z0 x
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    - M1 U% W. e4 R5 `9 X" ^8 M; \3 b% w
    2. **递归条件(Recursive Case)**2 ?) g8 ?7 D" U- w1 [
       - 将原问题分解为更小的子问题
    ; D- [8 [6 k; P$ m5 C6 |   - 例如:n! = n × (n-1)!
    ' B" `3 L* a) v" x# r
    2 _5 I  H- C" |+ N5 K2 W 经典示例:计算阶乘5 n. W+ B1 I# s& x- w# E2 K
    python3 W5 F* t9 J$ R) f2 y8 t6 K
    def factorial(n):+ ^0 N3 I4 T; [# I/ q
        if n == 0:        # 基线条件
    7 j8 G; P! O6 q8 U0 k, N# H        return 1# s3 Y& o- `; s$ L
        else:             # 递归条件
    6 R% s2 X+ t! _5 {1 _        return n * factorial(n-1)
    0 _* y" r: H% D) I* ?执行过程(以计算 3! 为例):
    6 O1 R' c, }, ufactorial(3)
    ) m$ v2 c" N8 W' J# q5 a8 H, z3 * factorial(2)- p3 ^) z5 `3 f1 F7 O
    3 * (2 * factorial(1))
    , M# r; t/ G* ^; B& R! |: a; v& j3 * (2 * (1 * factorial(0)))
    , d2 o; [4 l( G" k$ t+ R' \3 * (2 * (1 * 1)) = 6
    0 Y5 G* |; u: K7 }0 S  y! C0 D# Y) {" O2 ~
    递归思维要点
    % L$ E# n- t' O8 d2 s& @) m1. **信任递归**:假设子问题已经解决,专注当前层逻辑# S& C5 s8 O! ~' `; t1 [1 _+ R
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    % F6 A/ ]" u; m6 }2 ?$ K: _( f3. **递推过程**:不断向下分解问题(递)
    ; Z4 ]/ W9 Q$ z3 o/ ~2 I+ M$ n4. **回溯过程**:组合子问题结果返回(归). W' y: E7 O1 C6 {
    * A1 n% k1 S' p
    注意事项
    ) H1 O& _) f$ q7 W7 U, |% H必须要有终止条件2 g& `4 i9 J: c9 V9 E5 i& n4 h
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    , f. n3 _& {, k$ B6 G% V" X1 L某些问题用递归更直观(如树遍历),但效率可能不如迭代( Q& o6 O( D7 Q+ m  R( x
    尾递归优化可以提升效率(但Python不支持)
    3 ^. l) O6 e. H4 z
    , A$ T& O' h# U( @& ` 递归 vs 迭代
    7 M0 i  ?1 U* D) {6 ~% @|          | 递归                          | 迭代               |$ }8 {/ W/ \% ]& r5 E: e% |$ R
    |----------|-----------------------------|------------------|3 ^5 O" w0 z9 j1 d
    | 实现方式    | 函数自调用                        | 循环结构            |+ B: R+ {$ T7 X6 {$ X7 S
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |7 _3 v( [* B6 }/ ]2 r
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    # f$ J9 D6 n8 H7 G1 c3 E| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |' ?+ m( G2 ]8 F$ j, m; r$ A

    2 x" V% x0 l, s8 c6 Y 经典递归应用场景- G3 \; k7 l, x" u
    1. 文件系统遍历(目录树结构)! v3 b) F4 B" R7 [+ D. I
    2. 快速排序/归并排序算法5 y; Y) r$ }; O$ E
    3. 汉诺塔问题
    ; d1 n" {9 K% `4. 二叉树遍历(前序/中序/后序)/ ]1 A" v# z9 P8 r) w5 g6 W
    5. 生成所有可能的组合(回溯算法)/ y- k$ l9 q8 V4 z
    ! E* ^- u5 g% d( {
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
      c* w  h: D! S/ y1 n我推理机的核心算法应该是二叉树遍历的变种。
    & @; u+ f. d/ P, T' I7 J. 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:
    3 S( w9 @$ d5 P% x/ DKey Idea of Recursion" Z  e8 V8 p1 B1 h

    # U+ |0 E4 o9 P9 l" i6 X3 {  A) VA recursive function solves a problem by:
    + a4 w: e: M) V
      l" l  v- ~; N    Breaking the problem into smaller instances of the same problem.
    6 D, V( i+ N# b% @3 \. s% H0 u$ N1 y2 T/ ^+ s. C" V
        Solving the smallest instance directly (base case).
      c# s" @" G. H4 S/ h8 d5 E/ B1 x& F7 F& E5 A  o4 H
        Combining the results of smaller instances to solve the larger problem.) f: ]6 ?; Q  k+ U: N6 T! W- o

    " O2 G  I# j/ U5 ^  h+ uComponents of a Recursive Function
    % F2 ]8 g+ s8 U9 @- e8 S5 j
    . v- M7 u7 B4 ?& K& F& a    Base Case:
    ) J+ I! O# |. N2 y: G0 Z, h8 D9 p. h$ q" n/ O; H
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.0 R% l5 z' c4 o4 }

    . H2 C8 X, s% E% C, j: b        It acts as the stopping condition to prevent infinite recursion.
    ) T+ e8 l- X( }6 [: j% R1 t8 T9 M8 S3 b6 u! M; V+ r: R
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    5 w7 Q0 a7 k* \1 ]4 ~) j: b- v& Y0 _) t* ]$ ~( }' Z' d
        Recursive Case:! ^3 \  R+ u# d8 v' T! w8 i
    6 i! u& ]! V  ~5 b" ?5 z  R" U
            This is where the function calls itself with a smaller or simpler version of the problem.) N; x6 a. Q) K( T6 J

    6 g4 D! x2 i. U        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).. @+ @2 r4 t+ {9 g# s7 V& k, ^

    8 S- e4 {6 {$ @# \3 o& qExample: Factorial Calculation; A5 ]2 |( `/ p- U  D8 N1 [

    4 m. H4 {$ p2 b$ e8 _2 Q0 Z* A7 p* WThe 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:8 W3 \' D. ~/ u  K5 i5 X) `

    . |0 g9 o. \3 y  c! x9 _) P    Base case: 0! = 1- l! M% F" c. o  n
    6 q* H! Z* m# P1 G- \- J
        Recursive case: n! = n * (n-1)!9 m/ A4 k4 ?) w/ w3 s

    & E- l1 X6 e: [Here’s how it looks in code (Python):$ A0 L0 O8 S, R( E/ A, ~
    python
    6 {4 _6 w" w2 i% y! i$ g! G2 n2 a+ Q1 b7 l3 x# J: L
    ( H; Z/ J/ w) N3 r& q
    def factorial(n):
    $ O) N4 v" n" e8 A4 a* |    # Base case, U6 |, B/ ~8 n. Q
        if n == 0:* l: F, P7 U" ?. F% {  k
            return 1( u" M. i: m5 p& J$ T; e, g
        # Recursive case
    2 o: l- m% a7 L0 O7 N4 M    else:7 J7 p7 s0 s1 R* I
            return n * factorial(n - 1). u, O' T1 Y. {0 b

    8 g) l' M5 e) l1 |2 v9 r# Example usage
    $ n6 B, P( y1 [% ^7 K/ Tprint(factorial(5))  # Output: 120$ d; |/ ^# @  @1 i

    / m# t8 S: t4 {* |8 O& ^4 RHow Recursion Works
    - ]- a% m% U" A: W, T# C
    ) o7 Y. j" c8 F: l    The function keeps calling itself with smaller inputs until it reaches the base case.2 N6 X1 \8 t* |: ^/ G' R

    % v+ \; e. B, l6 Z, N; p! \1 A    Once the base case is reached, the function starts returning values back up the call stack.
    7 W2 N) `+ ^* K1 H, f
    - Q, K; q, P6 x+ n: g    These returned values are combined to produce the final result.
    : I% g! ?$ E$ V" P+ b+ s: J9 a$ t
    For factorial(5):) Z( C& }6 i1 O1 v, h0 |, d( a
    4 U/ T3 J/ I4 M3 i, m/ `

    " n" B; Z! f6 n# w5 Sfactorial(5) = 5 * factorial(4)
    / b4 E4 L/ N7 W6 Ofactorial(4) = 4 * factorial(3)5 S( R; p; A7 m1 ^
    factorial(3) = 3 * factorial(2)1 y, p1 k+ N& z7 j2 X# k* M
    factorial(2) = 2 * factorial(1)# t. j% \' T+ l) U# c" `
    factorial(1) = 1 * factorial(0)6 f5 r% ^2 p$ s! |$ }' I" h
    factorial(0) = 1  # Base case
    9 Q4 c" r( `5 W6 w$ R) S# M+ a1 ?
      r7 T6 i& [: P" Z/ ~4 XThen, the results are combined:7 O6 x: J1 K+ t3 {

    , ~' R3 t1 U' I- F/ T# W. d
    ; B& {$ o/ Q1 I2 I% ]+ `) M9 sfactorial(1) = 1 * 1 = 1
    9 |0 ~  S6 Z. y) B3 afactorial(2) = 2 * 1 = 2
    " u  q( g. [+ |' Sfactorial(3) = 3 * 2 = 6
    + y, E! Q* T  e7 P8 d# s6 l# Efactorial(4) = 4 * 6 = 24
    . t3 s2 b. \" y1 g% g2 g+ yfactorial(5) = 5 * 24 = 120) ^" W' ]" F, ]1 g4 |0 W  [9 s: l

    $ }% y) {4 n' u7 A4 pAdvantages of Recursion6 K2 U. N$ I5 w: q* V1 b3 }

    4 X5 I( O& D9 a+ E- u1 e    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).+ ?% C5 s% e, x& {. w7 P7 c0 o
    & e- Y7 v7 W: H$ L+ d( O
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    $ m+ `5 h$ W$ j  x+ C: r1 u  I! ^& _! t) v$ g9 i
    Disadvantages of Recursion
    & T. ^! T- K! b& U6 T( w4 ~% e' A$ S* @  U" b
        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.
    ! i( E$ Q3 c  f7 I
    - I. I0 h" i5 \    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).: a0 x/ Z- ?$ h# z! H* T
    9 A8 X8 Z' _# W# e
    When to Use Recursion: K0 ?& S0 D9 Z) B4 D; R
    2 _, {" P/ \, ?8 n2 H" H5 `; M
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    3 S" I9 b3 ^5 A, e
    $ e* o$ x4 I3 _+ g0 [    Problems with a clear base case and recursive case.
    6 D( x3 _& Y: b4 v: s6 n: l9 ^1 p: ?1 \. V
    Example: Fibonacci Sequence. [6 M) M2 y5 B

    1 f2 \: n9 n( w! j4 S2 DThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:0 M$ ^+ `1 \4 R
    7 P% ]" S( `4 C1 A) G
        Base case: fib(0) = 0, fib(1) = 1
    . O" z+ M1 h# {. c
    $ u1 K- E; P! a+ }6 @7 K" C0 C    Recursive case: fib(n) = fib(n-1) + fib(n-2); ?6 K  e! I& Q* j, m# C+ D" t

    8 t8 s2 [" X+ @3 O. W; n( Ypython
    + T4 R5 @5 w3 F" M/ z" `
    ' o0 j4 V4 h3 ?, Z* Y3 u/ P5 k3 ?( N4 g; a' q; n; v; I
    def fibonacci(n):
    * k+ W0 {1 L3 V5 l    # Base cases
    # z7 }4 M& Q/ i+ X% z& `: _! w    if n == 0:
    ( v; f( x8 ~' x! k        return 0
    4 ~% {0 ~7 N/ N" |! s/ r$ h7 S  b    elif n == 1:
    * }3 W/ W; G! e% G        return 1
      N, T, x5 q1 V    # Recursive case
    # K1 q; W% V; j! W/ b    else:& o' O1 i! V. j! [- x
            return fibonacci(n - 1) + fibonacci(n - 2)
    8 a& _& \  @- }
    * l# ~) [1 K8 r* P+ a. g# Example usage
    ' S/ ~8 K3 t" \1 s$ kprint(fibonacci(6))  # Output: 8( h+ U8 v2 Q8 w3 B2 M- }' k

    + F: M# f' H# p( l" kTail Recursion
    / o! B, z; B* j5 S* s# c$ r! o
    9 W2 _3 i# P6 |0 gTail 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).
    3 Z6 A8 d2 D. b  @% w' G
    ; K/ b+ ~. ~' K& \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-3 00:38 , Processed in 0.031963 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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