设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    * f0 X4 u6 m# O8 f6 o0 o7 |6 j4 q1 ?( j$ l4 y
    解释的不错9 C6 ]6 I6 k  p( W. D

    8 S: Y8 G4 f8 g$ q递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。/ N9 N0 T% B% H7 ]/ z- w

    8 r; `0 F$ h8 l 关键要素
    - u6 Z; F9 D4 m& F1. **基线条件(Base Case)**. D8 K, B! z: U/ }% K) R1 i
       - 递归终止的条件,防止无限循环
    1 b- _4 v5 Q1 w3 F* F   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1  ~9 l7 ?9 Q" N8 N" x6 W

    ! d/ j0 x* c. T( p3 w0 |2. **递归条件(Recursive Case)**% `5 W9 K2 t6 R
       - 将原问题分解为更小的子问题8 d6 ^* K5 g+ c( n# G2 P- O
       - 例如:n! = n × (n-1)!4 z1 p2 i- @: x+ k; d5 C

    ' [( c3 I0 R& n 经典示例:计算阶乘2 f0 X7 ?# p3 u; i6 h" A: G3 @( e
    python: m9 j. R, O- }) I; b$ |) S
    def factorial(n):
    5 }2 r* A. N3 m) N/ h2 Y    if n == 0:        # 基线条件! h. Z* N) @3 P- }+ X1 C
            return 1. e+ W  P* m, n# V- g: Y
        else:             # 递归条件
    ) E$ a  k% C- w  m! E$ p% G        return n * factorial(n-1)
    4 |6 o3 f( r( |0 `执行过程(以计算 3! 为例):8 J6 ~  `( n9 s! J5 p" U
    factorial(3)
    ; f$ I- G' A+ t* J' C& V3 * factorial(2)
    * i7 Z+ A" _9 B3 * (2 * factorial(1))- x7 r# d7 `/ I6 Z; I9 f) L
    3 * (2 * (1 * factorial(0)))
    : I; A  j& v5 I! h5 B+ J' P- N7 D# e. J3 * (2 * (1 * 1)) = 6; M2 Y& Q1 D* C: P3 j+ f

    2 {6 P5 ?4 z1 S' a7 X& l 递归思维要点
    ' M! ^4 g; ~. i: Y5 W1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ' P# J7 p7 y4 ?2. **栈结构**:每次调用都会创建新的栈帧(内存空间)) U' [8 |8 r, L9 i" G6 \$ i
    3. **递推过程**:不断向下分解问题(递). u: O3 `& B6 h, b! {
    4. **回溯过程**:组合子问题结果返回(归)
    . J( C+ w7 W/ v( b# p  f# H, t& D1 k. e0 ^# `6 O  F
    注意事项0 J- H+ H+ @! C4 j2 U
    必须要有终止条件
    2 n9 e- R$ L5 ]- P递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    ! F% J2 H8 y+ M/ }" r, q( S" o8 G1 ?. c某些问题用递归更直观(如树遍历),但效率可能不如迭代
    ; ?: e5 h  k& d2 \尾递归优化可以提升效率(但Python不支持)% R2 d% a3 `# z! r9 `) S
    & K% ?$ ]6 P+ }. j* o
    递归 vs 迭代
    6 q8 ~  J% t9 a0 @" E: E|          | 递归                          | 迭代               |
    2 V$ U7 U  e% @2 F9 [|----------|-----------------------------|------------------|
    4 R+ L$ s6 I5 g  }  A8 U| 实现方式    | 函数自调用                        | 循环结构            |
    5 b# S( s/ f0 ^" M1 _. V, A| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |6 U$ i! _( P' A- w, C6 D9 w
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    7 }. P9 P8 C# Q" p- {| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    " ^7 l( C, s- w9 D% V' O) O" K7 u
    9 ^- |3 o" q6 u6 M9 t& ` 经典递归应用场景7 U# w4 J, J% w& d+ i
    1. 文件系统遍历(目录树结构); l9 W$ Z! D: B  |
    2. 快速排序/归并排序算法
    5 n# q" K& @" B5 |3. 汉诺塔问题
    1 |( d: d0 ^1 _2 m4. 二叉树遍历(前序/中序/后序)
    , b) Z; z8 S. }, X) `5 W/ W$ \$ t5. 生成所有可能的组合(回溯算法)
    + l6 b5 U. D8 G, O$ Y. ]$ @2 t9 }' z" K( _& u; n
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    难过
    昨天 10:21
  • 签到天数: 3151 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    . F9 ]/ s# ]$ D, Q9 K我推理机的核心算法应该是二叉树遍历的变种。- y; J6 M: i3 h1 z* S! J
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:& T: R/ z: B: D; `, p  B$ ~
    Key Idea of Recursion/ {% [# @1 W) W3 N3 v
      J% P7 Q' G1 u" W
    A recursive function solves a problem by:
    6 q3 j% v9 q$ e$ j/ h8 V; t7 x# |) y
        Breaking the problem into smaller instances of the same problem./ Q0 P& F( a9 e/ ^+ G/ D( ]
    5 y0 q' a: ^! @8 Y* U7 i1 K7 Y
        Solving the smallest instance directly (base case).
    7 [& T& C& d! s3 j6 o7 C5 e4 {* E0 B
        Combining the results of smaller instances to solve the larger problem.1 e! K' I0 t  b8 Z
    2 H" u! d  a/ K
    Components of a Recursive Function
    : b/ l+ l( l( C, L3 E
    / f" Y8 x6 Y: \5 K: D* G1 K5 v    Base Case:- k2 Y0 y; A0 r: L: Z* Q9 `7 h8 g2 h
    2 G8 L7 x2 i- ^; ?, K
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    5 y$ ^$ H' x1 ]8 O) t6 f* u* J  l1 c, J# y  y
            It acts as the stopping condition to prevent infinite recursion.
    2 i( i( p/ ~1 S. f
    ' {. \- e7 y5 E7 F* w' S5 R        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    ' T& b$ I9 j: A  E2 s2 o/ J8 O) p' m- z7 v- H  x
        Recursive Case:
    ! e9 O4 z+ l0 z4 d4 N2 H
    : @  {5 x8 L3 {+ z, R' P        This is where the function calls itself with a smaller or simpler version of the problem.
    . b3 T0 w6 M; g" e/ }# u2 I, o+ K9 r! \3 t. _* k% Z" n
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    1 s+ _2 e6 h$ G* }  z0 [( l0 t8 ^, N
    Example: Factorial Calculation
    ( G7 _' p( }# V) `
    ; S# }6 ^8 j2 J) r# d: C2 h* |' xThe 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:! p. v1 v  u9 z; c* p
    3 K5 g) }2 ^( T7 D
        Base case: 0! = 1. n, O1 e& b: ~* O
    . F8 ?$ D0 v3 V; x
        Recursive case: n! = n * (n-1)!
    & H9 I3 S$ a- [+ W2 N
    & w4 c8 d( u1 u7 Z8 j  l% dHere’s how it looks in code (Python):* ^$ O7 R" `( L" Y" x
    python
    7 C" j! b9 C0 W6 n6 V4 r. T8 w2 \6 E) w: W, H

    6 m' ^8 _: G, M4 O, h' B$ c" sdef factorial(n):
    7 Q' c- b7 s5 H' r+ F" {+ E5 {    # Base case
    / ~. K, c. s* `( Y# ~% K    if n == 0:4 v8 B# v6 A7 _4 D. h' d, n
            return 11 @3 B# ^" E2 F3 y, E: h7 j2 }, \% @3 K
        # Recursive case
    8 q4 z# s# a; c- E9 a0 P    else:. C) V0 Z  J; ^  d; ]
            return n * factorial(n - 1)
    ( q$ Y3 j) G6 K( f$ o* P( |5 I9 a4 J* m3 p+ m
    # Example usage4 [7 ^/ n2 l* v3 `: S- O
    print(factorial(5))  # Output: 120
    , Y8 b! S; e/ |
    * [; a* w# H1 NHow Recursion Works5 _8 }: c/ p! x" a6 t

    7 Y* @" ~, t$ M$ v* m" r5 J    The function keeps calling itself with smaller inputs until it reaches the base case.
    : l) ~6 \6 L* o( w, b  ~" l& a* [
    / _, S# \$ G0 G/ w    Once the base case is reached, the function starts returning values back up the call stack.* V: b6 D  }! V+ R
      U3 {5 W& g3 A+ B$ w/ r2 E$ U& b
        These returned values are combined to produce the final result.
    - L; A# A0 d: K
    ' T; E; I3 Q: F( m0 f/ lFor factorial(5):( ?! B4 j2 B6 L, I. `7 V* W3 Z! H
    : ?; v2 A9 L+ ?0 O9 e( ~
    2 g5 y- c# P: C8 Y" H: q
    factorial(5) = 5 * factorial(4)5 o& Y" ~% t' A  q5 c* s
    factorial(4) = 4 * factorial(3)6 o1 Q- d5 x3 f" E
    factorial(3) = 3 * factorial(2)
    ' k1 n0 J4 q* Y$ S6 ffactorial(2) = 2 * factorial(1)+ z$ u7 u: N  m& T1 x
    factorial(1) = 1 * factorial(0)
      v6 p$ c9 R0 ~+ \! rfactorial(0) = 1  # Base case
    0 F+ \- i" \8 a' g# N9 q7 T+ `" J- H: e( R: |+ F0 B
    Then, the results are combined:- m( v3 o/ M( V  ~' x

    ) A' [: ^. ?% x) d* K; |1 G, g( M  M$ ~* |( w/ D
    factorial(1) = 1 * 1 = 1
    " T- Y" L, H, _4 l& M6 G, Rfactorial(2) = 2 * 1 = 2
    0 B/ ?3 z# q' z% jfactorial(3) = 3 * 2 = 6
    " C+ Q1 O5 S6 b1 `8 Gfactorial(4) = 4 * 6 = 24
    ! M% s5 R) ~4 e. ufactorial(5) = 5 * 24 = 120
    ) _6 _! r$ D8 ]2 W$ B' b3 f/ h7 P2 x3 ^, H6 L4 N
    Advantages of Recursion
    ' |7 u: M2 q; i: k! Z' Q1 r& K# X& z& o6 \% c$ n- s  z8 K
        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).
    " a! @/ ^* I6 @5 J& `& b, }! k% g: c: L# O6 I  {  S8 ^% }
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    7 Z! S& m( r9 ^" @3 Z: R+ d4 I# B( u, U8 n
    Disadvantages of Recursion
    . B' Z9 n. ?7 e3 l1 l
    2 a' @$ R& }% 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.0 {, e9 j. d0 g6 H* P/ F
    + R5 _1 K: f2 v" b3 b1 C' X
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).* E: I) p7 K# d3 H0 }
    . U$ j1 g' F0 g8 S6 ^/ c" A
    When to Use Recursion+ D6 Q$ x6 d- [5 g* b: z

    ' {. |  K: P7 U" q1 A0 r    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).4 R: {- S8 \" c% Q: @

    + T+ ]* X7 |5 R- x! k    Problems with a clear base case and recursive case.
    # O( h' k4 k: A' V$ G
    0 v0 n, g( ]9 W3 R, P& wExample: Fibonacci Sequence
    , k9 X* B: c# w) j( h8 ^9 S3 _3 V: E
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:3 V, j7 ?/ x2 `- i: T) o* O; q

    : e! _& o2 V3 o) t) Z# R: y) R    Base case: fib(0) = 0, fib(1) = 1
    " m% d# k1 y" ^1 K$ J! F- a7 i
    - O# p  e, i; `+ C; i, S    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    1 ?" e  L+ c" @2 e9 ^/ h* e! m5 l5 w3 F  m; h- P
    python
    " A1 P& Z5 M0 l$ c* u
      U' k7 r% _4 e, Y" C
    ; x; w+ f0 [' R; f* A; x+ Y; ]def fibonacci(n):/ a0 ?" U3 w! R# }3 R
        # Base cases! ~" {: v0 p% o8 N6 z: h4 Y
        if n == 0:
    8 J7 g" r0 O" i" {        return 0* l8 c) P& U0 g
        elif n == 1:( i; S) b0 B: x2 [/ H; X. I8 O
            return 10 K- }3 I0 J' Z' }1 x6 ~) G" D
        # Recursive case
    6 n- c6 P' Q  N/ ]9 s    else:# C3 _" {1 J( K0 t; O/ H$ R
            return fibonacci(n - 1) + fibonacci(n - 2)8 p3 [. B6 d* @. l% W( w- E2 e/ U
    , w# Q) P) A' L5 `2 [/ w, H
    # Example usage$ Z- }' x$ J  H3 Y: ]) h1 E9 U
    print(fibonacci(6))  # Output: 85 N- }: w' f7 [3 W$ K( |# F- l+ \0 A
    4 _" d& R6 D( v% w" {
    Tail Recursion
    1 v# G# ?$ S/ b/ o3 E1 Y+ c& P: K9 r4 o* v7 d
    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).+ n1 z% m. \* k4 v4 @* y

    * ~; X# _  i  p, L2 ~  R3 P1 {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-23 02:10 , Processed in 0.058433 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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