设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 " k/ [+ T" M% e% C

    9 @5 _( m, |6 V" h解释的不错3 b. N$ ~# ~9 {

    ' j/ _% ^7 a8 M2 ], r递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。1 Z  ?- d& s3 R% ]

    / }+ g2 K$ `' _+ ?  ?- U1 _" { 关键要素2 r% W3 P: b' r/ b# `6 O
    1. **基线条件(Base Case)**
    " K% j+ }# }: |' w; ]   - 递归终止的条件,防止无限循环
    4 ~+ y. n: l! e0 t+ q   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 10 Z- n! ?( [: _/ H
    / f: J5 S- \/ S2 e0 u5 w* J
    2. **递归条件(Recursive Case)**
    # P9 j0 Y7 U# [4 E! V1 y0 |   - 将原问题分解为更小的子问题0 j6 q8 T* D! R2 W
       - 例如:n! = n × (n-1)!; r% l8 F- S% E% W

    ( k- J- H5 N. Z  q/ V$ r3 Y3 V* l5 [ 经典示例:计算阶乘1 ^" |5 c- L2 P* Q
    python: f0 f5 X0 W* L0 r& f- F1 U! T3 X6 ?
    def factorial(n):8 _) h9 D, h# H5 D, z
        if n == 0:        # 基线条件
    ; x% W' F4 k) p' o        return 1
    : Q  V* L. z; N4 |6 N$ j    else:             # 递归条件
    7 L; O" j" D5 ]- t; N5 b  }2 Q        return n * factorial(n-1)9 j6 p  i7 m) `, J% A+ c
    执行过程(以计算 3! 为例):
    ! x4 M' B& l2 |8 [factorial(3)! ~& `* J9 O; O2 A
    3 * factorial(2)$ p( }. Z- ]/ {4 A! E' d
    3 * (2 * factorial(1))6 ?. o' h1 F, F, a9 E2 t+ c  \
    3 * (2 * (1 * factorial(0)))
    2 S/ x$ Y. E1 \3 * (2 * (1 * 1)) = 62 Y8 p* ?; U6 }- e0 g3 H% N6 ~* x

    : I0 ]  P  z! y 递归思维要点( k# S1 N8 J4 [
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    6 E. s# I; {! |) K1 \+ W* y3 |$ f2. **栈结构**:每次调用都会创建新的栈帧(内存空间)/ H7 M+ T2 I/ Q0 e, \" Q" d
    3. **递推过程**:不断向下分解问题(递)
    & G9 R9 B' n4 d( l, X4. **回溯过程**:组合子问题结果返回(归)
    ; x; [& V4 k; A- p+ W) v' L
    5 b2 k7 m7 `' L. k. f2 \. X, e 注意事项
    3 L/ ^# a) g1 t2 R7 j必须要有终止条件( J' I' v2 M! {* ~" w& f4 X
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)# k7 f! H, U/ N# O/ X. ~6 H3 u
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    . B, a( m- s! E  t7 ]! U+ W0 C尾递归优化可以提升效率(但Python不支持)4 [' `; ^" O1 \3 G- [

    / @- [+ \: g, `& L$ P1 ` 递归 vs 迭代
    ( t3 \4 @5 g9 g" O7 ]|          | 递归                          | 迭代               |6 ^3 k4 N+ X6 ^8 e9 ?0 T( j
    |----------|-----------------------------|------------------|! q8 ?2 S7 {, R1 b% S6 v5 S& D
    | 实现方式    | 函数自调用                        | 循环结构            |, |+ {3 w1 S* R* @8 P9 h' n
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    . x. F9 _0 q4 X  ]0 B* h3 q# p| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |% ~" h; e  X7 n3 S. g
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |. i- l+ I3 H$ Z* C6 c3 f) Y

    * k# W) @. ^8 ? 经典递归应用场景
    $ Z/ Y# t) F& z8 n: w4 L6 l1. 文件系统遍历(目录树结构)4 Q1 \; |) G4 e" {1 \3 G
    2. 快速排序/归并排序算法
    1 X3 I$ S7 t$ E( _9 [1 d3. 汉诺塔问题+ Z3 f4 }) S2 N1 F
    4. 二叉树遍历(前序/中序/后序)
    ; p/ w, b' i9 W/ G4 ?: f5. 生成所有可能的组合(回溯算法)% \8 |/ l/ H8 t9 i: d( i0 `

    9 ~4 g* O  q( H试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    难过
    昨天 06:15
  • 签到天数: 3181 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒," h) [6 T- T. j2 n
    我推理机的核心算法应该是二叉树遍历的变种。1 a! K# g0 e- a5 Y# ~4 K
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    - n3 Y+ z5 k5 [3 kKey Idea of Recursion
    / Y  B  y$ p- R& j5 [6 N! M* ^3 \
    $ G  z' I+ r$ }& ?1 d, }7 jA recursive function solves a problem by:
    % [/ i; x0 w! J% Q) P6 ]3 m* k" S  Q
        Breaking the problem into smaller instances of the same problem.
    ) D  T7 X* E* ~. ^
    + C) B) o' v; D    Solving the smallest instance directly (base case)., C1 Y+ x! Q0 Z. ^# m7 _5 Z

    . u! J& h! @9 p% G) I- W    Combining the results of smaller instances to solve the larger problem.
    1 b# v3 ]! i& w  \$ B+ |2 M
    ) V" M/ H7 r) e3 SComponents of a Recursive Function
    5 `( O# D% ]# l( `& L+ G2 J! H- [: Q$ r" U2 s: ]* Q
        Base Case:
    0 s6 c+ K; T( [3 f* a3 j+ ], N  r1 k9 ?! K: k: s* `
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.; a  P/ P; J6 D# V

    6 Z" W" W7 a9 r- }" ~        It acts as the stopping condition to prevent infinite recursion.
    7 V" t: c; v- k! l  V  _6 ~3 |3 ~4 |  q7 ]) ]; g
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1." r% o2 Q- S. b
    / v( g- o& A$ Q+ A% S% k7 w
        Recursive Case:
    - M, Y4 O2 `! Q. g
    , J# W% e4 K+ z, Z        This is where the function calls itself with a smaller or simpler version of the problem.
    : x5 I0 I7 p, V1 B3 N. n+ x( p0 m* A" Z  _6 r
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    1 |! C( y. d" Y  @; Z$ G% c  f; ^/ G
    7 ]5 j9 w' {$ g. C7 H4 G% D: Q9 rExample: Factorial Calculation  v7 v7 }4 x/ L6 R- p% I) K- M: {
    ) t4 y/ ^. T% Z( n, o- R0 G- X
    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:
    : F+ Y/ d* ?: ]  R# Z' a! ~* [7 x9 @6 D1 v
        Base case: 0! = 1
    9 Q9 o4 Z* }9 r9 p# |7 P
    % Y9 A  ^5 A- e9 I8 q, W7 f. X! M    Recursive case: n! = n * (n-1)!
    3 o4 u/ F( d& L5 {' Q- M) d' t2 N& r% o! a# I" [: z9 v
    Here’s how it looks in code (Python):+ J1 ]; _# b( Y
    python8 Y& y% l" o1 J% v' p
    ) O$ D0 s% A: Y. ~/ }
    1 e$ z9 C+ U' |( t/ I% b8 e, \
    def factorial(n):+ ]) a5 a/ g$ B8 b  h4 h2 M& T* A! R
        # Base case  l: S8 B" e2 s/ i6 D7 O# D
        if n == 0:$ ^. a. M" n* [9 O/ h& d
            return 1, |! h7 O4 D! m' @
        # Recursive case2 y. f, J' r- r( c$ q, T. C/ }
        else:
    , e. a& z7 L& }1 s) l5 u5 Y        return n * factorial(n - 1)
    , [/ h. _2 ?' }6 B% \$ h9 q. s7 W& }
    # Example usage0 Q# O& A3 n0 P: N/ K* ]4 @+ r
    print(factorial(5))  # Output: 120
    , s% k& R/ G+ E/ I6 P. @
    " ^  L. E8 m& T3 uHow Recursion Works  g1 L2 p4 i$ _- ^2 z2 Z
    + I7 n7 M( t4 u- {- r$ Q" |
        The function keeps calling itself with smaller inputs until it reaches the base case.
    7 Y+ h: ^; j) j7 t$ s2 q7 h/ o) r. e- g/ Y8 e8 T
        Once the base case is reached, the function starts returning values back up the call stack.1 X7 ]. k0 l2 }( C# u9 d4 s
    - T: ^6 }' [+ |) L5 m& U
        These returned values are combined to produce the final result.
    : C1 r0 A) e6 @" H$ X: t3 O" D7 Z1 a3 r
    For factorial(5):
    ! {  T6 s7 l$ B. q) b! Z
    * q3 D- ~: O: Q" `" \! }& u9 ~4 B+ @% [/ L( h
    factorial(5) = 5 * factorial(4)
    + o- N& ]* s1 s) Ofactorial(4) = 4 * factorial(3)
    $ V" H( S5 o# V* C- q: `) G9 jfactorial(3) = 3 * factorial(2)* J  y; i4 A$ H  E" b& P
    factorial(2) = 2 * factorial(1)' J6 U$ M, q" Y1 g: z1 T+ z. P
    factorial(1) = 1 * factorial(0)
    + E* S% s# ^- x% Z1 _. M4 I) Y) J# Rfactorial(0) = 1  # Base case8 Q, N3 h: M, `/ Y
    ( q* e8 ?6 A0 a, F
    Then, the results are combined:
    5 Y/ Z/ r; o4 I6 Y! [+ O
    8 d/ ]) z  B  T; [9 ~
    * D# ?" |; Q8 @6 x( V  I* Lfactorial(1) = 1 * 1 = 1% I  g" |* m+ ]7 o. w
    factorial(2) = 2 * 1 = 2
    # L" e6 u5 }6 e/ afactorial(3) = 3 * 2 = 67 `8 b# N; c% F; f( Z
    factorial(4) = 4 * 6 = 245 n  h# {- y* S, a! Q
    factorial(5) = 5 * 24 = 120& d- ?" A9 u. K; z7 A
    8 A+ H$ J' |5 T4 c5 w) {
    Advantages of Recursion
    ) v" f' f/ d* ]* ?+ G9 m4 v" F( F
    " h6 P1 ~2 x- i5 I6 s    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).2 e0 d9 h# W# n. I
    5 K% o' M- A# b: P- E
        Readability: Recursive code can be more readable and concise compared to iterative solutions." n3 t9 X1 c. }

    - H! z2 F* \! j  t+ k' h" HDisadvantages of Recursion
    5 `5 o9 o( M8 j8 U9 U( Q# b5 H3 S3 e
        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.5 `2 J" H: O9 Z! o

    " g; ?) T; |7 ~" ~3 v    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).% v4 f$ W4 q, r# I* z; z
    , E; ]. \2 e9 a+ B
    When to Use Recursion' @. A3 d' [; |) T% Y) p  V

    0 F. W7 ?  V8 T: l    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    * v! i; a4 ~' l! w# F' z8 _9 }; a3 V# x3 v/ f- ]* u0 l& V
        Problems with a clear base case and recursive case.
    ! j, O2 O. P' n% i5 v  A
    8 g4 a5 P0 C3 ?  SExample: Fibonacci Sequence6 e7 m7 A" Y2 [. D) Y
    2 Q5 i7 x: c! a* Z1 C$ T
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:( ]. m6 L* ]! _

    7 X: A9 l8 J) M( A8 v    Base case: fib(0) = 0, fib(1) = 1! a9 L( ?0 J+ p

    8 g3 ?+ d9 i4 z: `! s) D    Recursive case: fib(n) = fib(n-1) + fib(n-2); s; H3 e$ E% \2 }
    / Q( }- ]/ t) w' B. k' M, ^  F
    python; J$ M! V) c1 C/ K/ O/ K9 N

    " Q# G" }2 }) Y1 x
    " |: ^# C; `& G) k0 P* a4 [( W; F. pdef fibonacci(n):  j3 R4 j2 o* g6 }6 Y; a! u
        # Base cases& r$ D) M! |. A$ ~2 i- h$ @
        if n == 0:
    ' l# J- a% S9 D        return 0" v) c- ~+ A* ^* A  f8 l. `+ K  E  R' I
        elif n == 1:1 Z1 o9 Y# ?, |6 `
            return 1
    " C$ u1 s9 c7 A( k' m4 O4 b    # Recursive case) P) C7 S* G/ C& l7 ]* L+ u
        else:
    + Y4 ~4 g& T. P& u" M        return fibonacci(n - 1) + fibonacci(n - 2)  R* K. Y+ a0 ~7 K) l

    6 n# y2 `! l4 Q+ u9 @2 }& Y9 g# Example usage
    ( |- b) V- A9 Y7 d& Z1 F! y) lprint(fibonacci(6))  # Output: 8
    ; ]7 U# O- U' s3 I7 _
    / e+ n1 \- u( o1 q3 k( D0 ATail Recursion. [4 m6 W$ K( @% |8 Q5 \% ?

    2 r8 a. R1 h- @+ {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).8 f& Q7 Z% H# J2 ?/ ]

    ' r$ y# Z$ B) `" IIn 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-2-23 02:19 , Processed in 0.062307 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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