设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    8 [/ n/ O+ I4 I& S+ @- {; L/ @
    - q3 u3 E/ c) C8 x, {" o解释的不错
    1 l5 ^6 }( t: z. p( |9 O( w7 \( B; [8 y
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    % t6 N$ }+ D) m) ?) H( j9 b
    5 V6 U: ^0 V6 y( y+ u2 ^" r 关键要素- }+ E) a: ]2 T8 b9 f: e8 \6 C
    1. **基线条件(Base Case)**+ S. v4 n  T; b. |# ^
       - 递归终止的条件,防止无限循环" s6 E* a! j6 ^! ^) g3 v' m
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1( s/ z7 L0 J/ e. L

    ) z$ d2 f2 S4 s. V7 h0 K2. **递归条件(Recursive Case)**
    . J: l1 }/ z# x& K! V% j9 N   - 将原问题分解为更小的子问题; U9 Y9 C. w: n! m) G* n
       - 例如:n! = n × (n-1)!' D9 ]. B% l4 W( r: J& g- t% {

    : i  ~5 @/ s. P6 \; P, T. p/ K 经典示例:计算阶乘0 j# A+ x' Q  y1 o* A
    python/ y/ u6 Q' k0 e* F: d
    def factorial(n):
    % x% n$ M  u( L3 q9 w+ U    if n == 0:        # 基线条件
    ) j: C, w/ @# q$ {        return 1/ [# Z# B2 H6 E% B: p6 S! b
        else:             # 递归条件
    7 f0 L! o3 b/ T5 Q1 o. o' _& L! m        return n * factorial(n-1)
    $ I( N+ p( O# T" Y执行过程(以计算 3! 为例):' h( M9 m3 {8 a1 B" Z
    factorial(3)
    4 j! K# Q4 y* S3 X% d# b9 N6 n3 S; x" l3 * factorial(2)
      H/ @! g7 D- G) s3 * (2 * factorial(1))
    9 \; r5 h. y$ N2 Q( x$ f3 * (2 * (1 * factorial(0)))
    8 M# I4 P  K/ X% x7 m3 * (2 * (1 * 1)) = 6
    # R( o0 d$ H3 C# K6 h, J. V# B* w  g) r4 c! G$ b
    递归思维要点( f1 [" E, \7 X1 E) J0 u* f/ s9 Y
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    ' S' }6 J) v* K1 Q3 Z7 O: H+ j; K4 g2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    2 {4 y4 [( J* U  W) j3. **递推过程**:不断向下分解问题(递)
    ' u% I3 `+ S+ ^$ `4. **回溯过程**:组合子问题结果返回(归)
    0 S' D% v5 A/ E' e$ X7 R
    0 @9 [0 i9 K% `/ T 注意事项9 S. r& u; ~* V3 U+ N
    必须要有终止条件* p/ B  d4 R0 n- K
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    & P/ w; O) k! z, @& ], J某些问题用递归更直观(如树遍历),但效率可能不如迭代2 H' b) t  q+ }- j, \
    尾递归优化可以提升效率(但Python不支持)2 m: e" G5 Q. v4 E. d

    4 s) Q" Q1 z: Y- V 递归 vs 迭代
    3 R$ ^2 U$ ~0 y! E0 o, U|          | 递归                          | 迭代               |
    # l. J/ p0 N% J6 G5 k3 Q|----------|-----------------------------|------------------|
    $ U; j, _* B+ E" n$ w( e& |* ]| 实现方式    | 函数自调用                        | 循环结构            |9 Z  y; h- [6 D6 W! P. b
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |+ D: t% m+ X: ^% p  V
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |' u; d1 \8 `% J. w* r- i/ o
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |) A) A0 z& x) O/ t8 F( ?' V* j
    ) \" h& h  A* {' b
    经典递归应用场景
    2 P* C7 D  |: |6 c1. 文件系统遍历(目录树结构)
    . Q( Y2 L, A+ M( I2. 快速排序/归并排序算法
    / p0 d, I* N4 f/ M" d3. 汉诺塔问题
    " O" @0 F$ o5 k: i- @4. 二叉树遍历(前序/中序/后序)
    - M: @5 z6 m. g. z- Y3 e" E5. 生成所有可能的组合(回溯算法)+ w% a" C) a  H

    8 o9 L0 P, X. w+ N, h* M试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    奋斗
    昨天 06:39
  • 签到天数: 3105 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,  h1 K) s% J, d4 ~" ]* |
    我推理机的核心算法应该是二叉树遍历的变种。: J5 j: U9 i2 L+ A+ H
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:/ P6 r  d' ~: C& l% G" `$ J0 ^
    Key Idea of Recursion
    ' A! H' }. \+ U6 [& Y
    : f8 C* T4 P, S, [& w; s1 @. SA recursive function solves a problem by:
    ! ~' b& \: [: ?  f+ `! ~$ Y
    . A3 ~2 t7 J5 ]1 B; W: ~# E    Breaking the problem into smaller instances of the same problem.
    ! Q  d1 x% n2 L6 l. w# f
    + l( X, m; s+ a3 J4 I; F# W# u! M    Solving the smallest instance directly (base case).
    * H+ o. p7 H, ]
    8 o  k8 r( }- B' {2 Y5 o6 `    Combining the results of smaller instances to solve the larger problem.
    6 W* l; f/ }1 y) v4 [- M
    0 t% ~8 n8 u+ \0 `, @; O% ^. jComponents of a Recursive Function
    ( C2 Q7 V( {5 g1 L8 r0 u/ V+ T1 U5 t* R
        Base Case:$ k7 S9 O, k) W4 x3 U: i! c8 l

    3 Z3 Q: S  _5 ]. g4 S+ o        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    + w+ v) B  C: O0 ]3 D! z' x
    ' s: _! X+ X$ X6 i" [- P8 n& m4 [        It acts as the stopping condition to prevent infinite recursion.
    : P& T0 |1 z$ K1 l3 d0 ]
    # y6 ]' N0 F# s+ ?  y$ o4 Q        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    3 o7 ^5 B9 J! @$ x8 H: ]* p- f+ M+ S( Q9 x# d' R+ N+ K
        Recursive Case:& M6 r- w* b0 O
    & V  S3 h( J. O- k" f! ~1 S
            This is where the function calls itself with a smaller or simpler version of the problem.
    ; p4 w8 i. g* j. @9 w# J4 [& N
    ; P/ l2 o5 ?: K        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    + y1 f5 p+ n( g* \
    ! U5 r( |& P1 G- SExample: Factorial Calculation
    ) P3 R% D3 S5 Z8 ?9 N' h3 t) t! f$ g& {. `& X+ F3 u* J
    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:
      x6 q4 Z" ]* P9 P& C
    . S! Q% i4 d0 F# f3 h2 |    Base case: 0! = 1" o3 f9 E5 p8 H% n6 j6 n* M" \
    : Z7 I" h( x: I. O2 \4 U* K3 a) V
        Recursive case: n! = n * (n-1)!3 Z8 ^3 d- m3 {/ b1 A7 ?! j9 x

    2 ^8 [& ^0 e& U- P; Z4 z9 M. ~Here’s how it looks in code (Python):
    ' \7 D1 q- O4 f% \4 }. [3 dpython8 ^2 N5 f+ [0 _% o$ T  N8 Z
    6 u; l- B) u; l7 p; Q2 l& b
    3 g6 D3 v9 l7 m' T% q2 k! |% u) O
    def factorial(n):
    " D/ _0 u. _2 ?    # Base case
    ) n" P# [6 v+ _    if n == 0:- R2 U& I6 x5 k$ @, i
            return 1
    " M7 J: g; \1 F. \( e8 `    # Recursive case
    & _8 \" X, a. z0 W# b" V    else:
    3 r) r; T2 r; `" g- c6 B        return n * factorial(n - 1)4 C, f/ r) |6 Z, S4 M# D+ U

    ( D# [2 S9 Y4 x$ p, M) E: |) A# Example usage
    " t9 y: r- H: x% Aprint(factorial(5))  # Output: 120
    5 H* b( ]- W# P" M( F
    & r5 q, v$ N$ `+ a# SHow Recursion Works# F6 n( x! ^1 E4 F( z' E  k
    ' U3 v6 l* v' O! R, B' d
        The function keeps calling itself with smaller inputs until it reaches the base case.+ ~; B6 ]0 ~' I7 l: n# b8 ?  `$ A" j

      m+ X1 e  c1 _3 f7 C4 s) Q0 l    Once the base case is reached, the function starts returning values back up the call stack.
    / ]: L9 J/ Q4 u9 {- [- V* e! t, C4 R2 [
        These returned values are combined to produce the final result.
    % Z$ h! i" @, `/ N4 o- p, X; n, L9 e  e- c9 Y+ X; {. W$ q7 H7 M# @
    For factorial(5):
    ) \: u0 B7 Q# j# a0 C; _( M3 W; o- E
    3 ~5 @% l3 U% D8 v6 K6 m, E9 G
    factorial(5) = 5 * factorial(4): C' J2 V; S8 L% N
    factorial(4) = 4 * factorial(3)/ B5 i( q  k2 a' U+ D0 f9 I4 p% S
    factorial(3) = 3 * factorial(2)9 B2 j6 u7 ^( w; K. D3 X* S! ~
    factorial(2) = 2 * factorial(1)8 Z, c0 o/ I' l, V( `# ^  _5 ~& L5 E; m
    factorial(1) = 1 * factorial(0)
    * H. q7 |1 R$ N8 Z* c! Q" G( hfactorial(0) = 1  # Base case9 P4 U! M- x3 @' e
    ( T; g  s: f3 t* C* }0 T. n
    Then, the results are combined:
    7 @2 B$ F: `4 I; J& r7 x7 h* Z$ b) h+ B

    : W  n+ l4 C6 }. |8 r) z1 afactorial(1) = 1 * 1 = 1
    & E( C' w# K3 Y3 P2 |factorial(2) = 2 * 1 = 2
    1 R9 p6 H2 G8 t1 I' e8 F& s1 W& ofactorial(3) = 3 * 2 = 6
    2 p1 D* U7 m$ J+ D7 p) K) kfactorial(4) = 4 * 6 = 24( ]! q- R7 d% V1 Z
    factorial(5) = 5 * 24 = 1201 P; D: f, f+ ~$ R
    / C8 H  D# U5 R' p) u% _" s& }
    Advantages of Recursion
    " C! [8 E& m9 B, h4 D( Q7 [- }: }( G6 ^* t/ M2 Z
        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)./ ^$ S5 N4 \& k1 H( |$ L; E, _5 C) C

      z7 @; B% F, @7 o, x    Readability: Recursive code can be more readable and concise compared to iterative solutions.# R  Z( R. F$ x! ]% L; W

    * ~. S, l$ a% |: z: RDisadvantages of Recursion
    * Q- j* K8 K6 W! T& Z
    : `: M/ ^' x4 J/ ]    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.9 I  Q2 W: Q) r8 W; {% Y) M  w) G) o

    % G( w* c, q1 |, p1 ]; M1 l    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).& w8 f; M! i0 _, P

    # D8 X; T0 h; x" AWhen to Use Recursion8 g7 M# H4 X) f2 V" b' R

    % P2 D8 r3 {$ S) S# X" t: j    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).+ C0 `* E' H2 y: S- ~/ W8 k
    ) }" f* [) @. W- W# s/ z
        Problems with a clear base case and recursive case.
    * _0 W0 A, ~3 Q
    0 R$ h" E) u4 w) Q4 ]2 H( l4 b) v7 N8 wExample: Fibonacci Sequence
    8 b6 S( F# M/ V7 z9 Y5 D& ~3 E2 e9 X/ x
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:. I: E! i* T7 {- ]1 @  y1 K
    6 k$ X- T; ], w( R9 }
        Base case: fib(0) = 0, fib(1) = 1
      Y9 `  Y. o! K" c3 y2 E
    " Y# E0 [% u& K3 o7 I( n: C- n    Recursive case: fib(n) = fib(n-1) + fib(n-2)) I9 H- W2 \$ c
    * A* k) _5 i9 h3 h' y* Z
    python, v3 g  [9 c1 _( }2 L
    6 D1 V* r7 w) p) r9 M

    ) W& p: D& M5 ]$ ^. r5 a( Tdef fibonacci(n):
    / b$ W/ I7 n2 G) F    # Base cases. C3 e& b8 ]1 j# H9 C9 d; R+ f0 h
        if n == 0:
    ; d' j6 m6 r( R6 {: ]        return 03 g) @5 Z( U, Z
        elif n == 1:' C. s+ _+ f. J
            return 1
    ! a% W2 {7 W% G. [! ^$ q/ F" O& V    # Recursive case( V* {4 U& _3 ~. h
        else:- z- T1 e- ~' m( I5 ?) N" B
            return fibonacci(n - 1) + fibonacci(n - 2)
    9 ?3 w- l9 X) Z& p& t* W- Z2 Q7 {8 \* Z
    # Example usage) ^; h  a# `) O! J/ e& `
    print(fibonacci(6))  # Output: 8% [5 @6 ]* ~! D  g6 e  B- B

    9 r6 Z5 M1 \& [, w0 P# \Tail Recursion. A' S9 X1 e; F6 _
    ; U/ w4 u- {0 O' H' F. }
    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).( T7 D8 A* M# A: X; P& X
    # E$ f) O' g- U- z; L& K8 b
    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-1 16:42 , Processed in 0.036308 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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