设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    + W7 m/ o/ B1 _
    6 G! B6 a( @! b6 S1 N( ]$ p解释的不错
    1 l/ I3 `: ~8 N* o1 v5 `1 s* b9 B! n  ?: ]% D( m* F
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。+ t, W! O# f" J% H& g1 S, e

    7 A% H; }1 J5 ^5 @6 O+ ^' \. A 关键要素! _  E9 j) q' m8 g7 U) @4 u9 c
    1. **基线条件(Base Case)**
    ' E: U; _0 {' Y, x5 K$ e   - 递归终止的条件,防止无限循环
    ; Z( I2 |6 Q0 e, x" d  t8 _   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1& Q  ]  u; w: C9 J

    ! p) E/ @, v$ G' x- }: C2. **递归条件(Recursive Case)**7 p0 n0 O% U2 {6 P
       - 将原问题分解为更小的子问题$ f: j0 d1 Z  Y
       - 例如:n! = n × (n-1)!
    3 }* ~. F# G: ?. v. r7 P/ s0 R! f2 @, f. l! {9 `
    经典示例:计算阶乘1 @# C# D3 c5 K4 O
    python5 e4 v, h8 Y; D
    def factorial(n):
    ' z2 Q  ~4 [& `* w    if n == 0:        # 基线条件3 h; c8 e& R# k- k  z( L4 m. F
            return 1
    % r7 i# p6 j* ~! x. }    else:             # 递归条件9 T! Y& P+ M* [) b5 a
            return n * factorial(n-1)
    # S) x- L2 T) V; m' T# C- g$ e执行过程(以计算 3! 为例):
    ! P  N# y; `* |6 y; Rfactorial(3)- T* M+ H) Z" `! K, _
    3 * factorial(2)! V0 B7 R9 l3 P- s: R
    3 * (2 * factorial(1))
    : z! h) r* K6 I4 {# m4 b3 * (2 * (1 * factorial(0))). j* U( N9 }9 ?
    3 * (2 * (1 * 1)) = 6( z/ Q1 i0 R6 [& ?( z8 j, k

    , r9 ~# h7 ~! A: m4 } 递归思维要点
    ! _* ]  f" z  o# m, s' `, i. P) g1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ) p& ^: g1 p6 Y7 V+ {, m2 `( `- E2. **栈结构**:每次调用都会创建新的栈帧(内存空间)% ]$ {( \. T( d$ C
    3. **递推过程**:不断向下分解问题(递)
    * B* J" w+ k) Q: L+ {" |1 F: ]4 ~4. **回溯过程**:组合子问题结果返回(归): b4 v2 i, H/ C! z
    , }5 C+ y" `4 G! H
    注意事项' X" A2 f( A% f0 {" Z% i6 |; p" ?: n
    必须要有终止条件
    ; }' l& \% g0 b" Z% ^递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
      x( s& a6 g  N4 B* J4 S4 j某些问题用递归更直观(如树遍历),但效率可能不如迭代* G+ G2 ^. T0 R) [) |- X* u
    尾递归优化可以提升效率(但Python不支持)
    + v7 t& C4 N4 O* b) Q; \' V4 ?# `2 N
    ' ]' L) K& |3 `5 K* O8 g4 O. X 递归 vs 迭代
    3 |) \9 u. |# M0 T2 f/ M, z, _|          | 递归                          | 迭代               |
    0 Y: p% {9 F! R|----------|-----------------------------|------------------|
    ; X- d$ L; R' X; l& Y| 实现方式    | 函数自调用                        | 循环结构            |
    7 a: t, S& Q; U$ ~0 `. E$ G| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |, `& w8 O2 o/ p. E+ M) [
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |9 Q8 U9 u( ]; F9 E
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |. T) T# H, J' P, `

    " _6 t) k4 l# s6 o, x) Q 经典递归应用场景" a5 W' }: D4 s1 t! x" a
    1. 文件系统遍历(目录树结构)/ Y" }. W# R3 X  g7 f4 W
    2. 快速排序/归并排序算法9 I% D7 ~& d8 m. p: X$ I, t
    3. 汉诺塔问题
    # {6 E& f& K+ B: N" \4. 二叉树遍历(前序/中序/后序)
    9 [" Y  N8 m1 [5. 生成所有可能的组合(回溯算法)
    ! P7 g' h. ~; t- h; R9 l" v7 a  N+ X/ p! a" C
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    慵懒
    6 小时前
  • 签到天数: 3148 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    * v5 K4 u6 p( H/ v6 p我推理机的核心算法应该是二叉树遍历的变种。  J& Y  k1 M8 b& n2 m& i6 S
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:9 R' Z' B9 J  Z. _; c
    Key Idea of Recursion5 ~, x1 m7 `& H. `

    0 j" C3 h  W; I) R; Z3 yA recursive function solves a problem by:& d+ b( Y* j9 Z' ]( W0 J
    $ Z4 e- @- |0 F+ ]& F7 t
        Breaking the problem into smaller instances of the same problem.
    5 C2 [, ]0 {6 L; D5 S7 ^( T7 o, ?
        Solving the smallest instance directly (base case)./ _1 q; {: `& w$ b
    + b! Y1 P) K! X- R- X! D
        Combining the results of smaller instances to solve the larger problem.
    % n) \1 o* }. X
    " E3 g. s% q- D( h5 g) p3 _Components of a Recursive Function; o2 {7 w  j  ~( _% X

    $ r6 m1 q) V! R5 P9 s7 V' u    Base Case:
    5 I- i8 j! F0 }  [+ b
    4 i1 C4 ^- U: u# H( _0 i        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    ) g4 r0 T3 Y/ v* P0 J8 {4 i/ V- ]. |5 z  H6 ?
            It acts as the stopping condition to prevent infinite recursion.
    1 ]% r; b* p' q# `2 B/ j/ U! |! a. l- c' h& y# B, b% Y) G' p
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    * K) g6 X4 ~3 d- h& J" h" v; ~  K: _9 U6 f8 S9 o/ ]' U* G
        Recursive Case:7 }1 [. {, w7 y& m3 y5 m
    ) l" Q; H9 V6 m6 j( K$ L8 [/ e
            This is where the function calls itself with a smaller or simpler version of the problem.5 i5 H8 A) Y/ u# P( Q

    * q  H0 D" \3 n- F( a7 s; C        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    ( K! k* E7 {9 i. L
    # F2 N/ P; q) k- {) n9 _& [+ TExample: Factorial Calculation2 i, z( M4 Y% b3 Z  B7 r+ \% ]

    3 b9 W( w' m% AThe 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:
    & a& u9 s- X6 U/ T$ m6 _  \% @
    1 |/ m/ o# D( y$ p) u+ [2 V$ A8 p    Base case: 0! = 1" a3 k6 t+ A% C7 y, Q: [( L8 i
    % ]4 w& m: n* z
        Recursive case: n! = n * (n-1)!, i) `; U6 A6 o+ p- R

    " Y  m- S6 S& e0 J1 n# y0 Q5 VHere’s how it looks in code (Python):2 k& r4 N0 s1 e6 e: Z2 M
    python
    : B5 j5 `1 v( C. T8 p" P% V' |4 s# I' F% T
    * c3 [) J3 l( D# k
    def factorial(n):& M8 S1 l' m6 k) X; v* a' G0 h
        # Base case2 v% w3 \. W4 _. g2 H0 ~+ Q* u/ ^  J
        if n == 0:
    . o9 r0 v. E  k) A0 i+ ^        return 1
    0 f# D* |5 K( Z3 q# p/ _. K/ a    # Recursive case* @" O6 [3 E1 b& }" F0 v
        else:
    8 ]1 j6 d5 Q! G        return n * factorial(n - 1)5 R# D* _- p; O% l# w
    0 U/ q# k6 j% V. A
    # Example usage& P6 ?; K- L9 r
    print(factorial(5))  # Output: 120! a* A0 H* x$ o5 f# [, Z

    9 l! T- T! O! ?1 f' R8 j8 SHow Recursion Works) p1 D9 S6 E; Z  x1 b+ c; Q

      O3 v! {9 L0 f6 R$ R; F    The function keeps calling itself with smaller inputs until it reaches the base case.
    9 ?! R3 b3 p2 v( ^2 @) e' e# }- j2 C0 R9 n) e
        Once the base case is reached, the function starts returning values back up the call stack.5 S2 E6 z0 Q9 c4 t% t# N3 y

    5 d1 i" y3 ^2 e2 E. G3 F( h    These returned values are combined to produce the final result.6 G. I0 W6 z  W& V

    ; x  O$ b: P. u6 ~# ~$ @For factorial(5):/ Y0 r4 ^6 N7 P/ b6 ?
    # u9 G* ]8 e* _: t

    8 ~. U4 ^5 i+ efactorial(5) = 5 * factorial(4): F/ f3 d2 N0 |6 m5 m/ t- T
    factorial(4) = 4 * factorial(3)  g! k/ X( ~$ k# E1 r
    factorial(3) = 3 * factorial(2)2 @* x% @# V9 O3 Y( g. M; l! ~
    factorial(2) = 2 * factorial(1)6 w# y0 w3 l7 ~4 ~. }
    factorial(1) = 1 * factorial(0)
    * ^! x: I. _6 }8 Hfactorial(0) = 1  # Base case
    9 E/ G* a, v5 |: A  z  H6 a
    " M8 v$ h- L; n: m% iThen, the results are combined:) C- i+ }3 `- z8 A1 [

    8 F: r4 v* Z. O, ?$ T8 C0 Y' \' g. O0 p
    factorial(1) = 1 * 1 = 1
    + p: g$ _* \# Z, M/ K+ l: Gfactorial(2) = 2 * 1 = 2' k8 _2 K  \! r6 I9 |
    factorial(3) = 3 * 2 = 6
      W- i1 R  N& l+ o% ffactorial(4) = 4 * 6 = 24+ q- L4 {% r" t$ }
    factorial(5) = 5 * 24 = 1207 F9 t5 b; {" R

    4 t4 F0 v- o" _+ ^Advantages of Recursion, S' t' @% T6 m# p) ~

    ! e8 n6 N0 }$ p. p$ E' K* d    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 D, ^; X. K( |3 Y' ?( D" a6 b
    * H* X& H  _4 h. R
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    7 W8 f" T0 L, E& x3 {; ^( c+ w
    & }0 D" ~% L3 U# d. NDisadvantages of Recursion# y+ o! _$ c% h) |% h
    * K1 Q$ v$ V) Y, }% H
        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 ?$ ]1 q: Y3 t4 ~' Z
    * S0 |. G1 ?$ I% {    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).! o. @9 N, T" n; u) D# x
    ) C: B" w0 T' ?
    When to Use Recursion
    # m9 D& b8 [# R  B+ j# K
    $ p, Q- I: Y; V9 l    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).3 x% i. j+ K" P8 @
    + ^7 O* t% g5 V2 w# K
        Problems with a clear base case and recursive case.6 e: s7 x- s  ^
      \9 `9 B) P* [
    Example: Fibonacci Sequence- n0 g8 D4 s9 u. l' f4 L
    . M: S( |* k) ]9 _
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:8 s' }; n3 H4 Q
    0 C: b+ y/ G/ G5 i. M  o
        Base case: fib(0) = 0, fib(1) = 1
    . g4 @+ I3 N/ K6 R. V% e3 s
    * O# U* D: j( |" s3 ^0 d* q) L+ |    Recursive case: fib(n) = fib(n-1) + fib(n-2); a- t4 z) z% ]6 D
    ' p& m3 Q5 s& O! S6 g# z
    python9 ^4 B8 S/ `) i! f$ W9 Y* h
    . q, k' }1 z) t6 n- Z

    # a1 T& _4 f7 T, S! Ddef fibonacci(n):
    , Q- b* P& S3 K9 `    # Base cases1 b1 Q) L6 K# K8 A/ n4 a& k2 `4 T
        if n == 0:
    6 s  c9 Y) f8 s4 V        return 07 \7 [0 k1 `9 V' G& o/ _
        elif n == 1:
    : @# X3 q( ~. V- ~, G. Q9 P6 F- S: W        return 18 b* G+ P/ y4 `- _$ r' ]1 O
        # Recursive case
    " Y! J6 d9 _8 d. u: m" W5 s' \. d    else:5 |* W( M+ G5 @( K) p% a! e+ i
            return fibonacci(n - 1) + fibonacci(n - 2)% B4 s7 ~* D6 M  o: w; Q

      ]; L9 N% f( T# T/ _- E# Example usage
    5 J! o1 A! k) C) I4 tprint(fibonacci(6))  # Output: 89 @+ W; H' r5 j6 }( M" z8 [! c" V' r
    ( ]- w6 t; D+ A
    Tail Recursion
    : ], |# |7 p0 p( u% H$ F! R# C1 c5 x- Q3 L3 X; Z0 q
    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).
    & e' f  w1 T  U* @" l1 a0 H) q* ]  s- f: e! P
    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-18 16:42 , Processed in 0.030447 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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