设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 2 C( [3 }' R$ T7 V

    ! z+ b$ l! T: \5 e2 B7 @  t) K解释的不错5 z9 u' _- J) O3 }# _6 w+ N% @5 e. h+ j! h

    5 o0 V8 O  Q/ c" H3 P+ @/ n2 t递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    4 i  h- f7 _1 Q5 z: \6 Y, O+ G7 A# g2 E
    关键要素
    . |1 S1 n# W) v# Z1. **基线条件(Base Case)**8 T, B5 e& g2 N! `2 W6 w5 i& u
       - 递归终止的条件,防止无限循环, i+ U" q, E) O! z2 f1 r, c
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1/ f' ^2 i& T2 k
    : h  ~/ I. K  M' b) U
    2. **递归条件(Recursive Case)**1 B$ h  T/ g/ M# I. G
       - 将原问题分解为更小的子问题1 K4 D6 x5 d$ E0 r' j( B
       - 例如:n! = n × (n-1)!
    8 @. P4 l  h1 b% R) a* u7 W. f( L
    经典示例:计算阶乘
    - l- N1 Z9 n6 A0 V! [. H, g' r! jpython2 F. Z$ H8 T3 f' I1 F" t% ]
    def factorial(n):2 [' A0 C: I- |+ g$ Z
        if n == 0:        # 基线条件, o' ^7 N9 O# P  r
            return 1
    : {" V  h+ R- q8 P2 Q0 F    else:             # 递归条件
    ) N% T/ _1 Z  p/ T, q        return n * factorial(n-1)
    8 Y, I1 e5 R- o# q执行过程(以计算 3! 为例):" U3 w, }+ Z5 a. s+ r4 X
    factorial(3)
    : C# X" k. [4 @6 y  L3 * factorial(2)" P4 s5 a( j& n# a; j
    3 * (2 * factorial(1))6 B3 {$ \. k6 I" c" t
    3 * (2 * (1 * factorial(0)))' v5 f: s9 m0 Y5 }
    3 * (2 * (1 * 1)) = 66 ^0 g- k) v! X3 w1 T# h/ Q2 b" a

    + D8 ^1 X  U" q2 D 递归思维要点
    / s' `1 ~* q" x6 b  {7 b; Q1. **信任递归**:假设子问题已经解决,专注当前层逻辑* }6 u/ p: K6 w% l" L9 @9 D! U
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    ; L! `5 m: N- `: N& @3. **递推过程**:不断向下分解问题(递)
    7 D" s  d3 q( `- g" W4. **回溯过程**:组合子问题结果返回(归)
    ( p' z( P# @" W* Z# l' ?& {- U" X
    : D0 ?4 ]; V0 Y) R0 J( Z2 ]% X% S 注意事项3 j- c2 P; B3 M6 `1 \5 O
    必须要有终止条件
    + ~5 N; u# D" n4 {; m" h递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    4 N+ U( \0 C2 ^: f  e' s某些问题用递归更直观(如树遍历),但效率可能不如迭代- g6 `- P$ k8 [( J: J) \, i* X  ~2 u
    尾递归优化可以提升效率(但Python不支持)
    4 h- K. u7 _! i% g8 `1 ?6 A
    + P$ T( R9 {4 ?& N+ t! G7 @ 递归 vs 迭代
    : R* {& z8 u, w1 T, }0 ||          | 递归                          | 迭代               |7 S; d" D, i3 o! O0 j8 u: \
    |----------|-----------------------------|------------------|1 L& \" u+ J5 B/ [  |% p
    | 实现方式    | 函数自调用                        | 循环结构            |& o! ^6 U) }7 A5 m6 I8 K
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    % R# ^# @" r- q) s% S* r3 r' q| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |' k6 R! O0 l6 X8 q% G2 l
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    / s  n( d. B- Y5 p2 [, f6 W
    : `4 C- k8 z' ]# U2 a* Y 经典递归应用场景; ^3 w' E4 p- M
    1. 文件系统遍历(目录树结构); x4 P( X8 L  y  j8 ~0 u0 u5 Q
    2. 快速排序/归并排序算法( Z+ i" n+ c& z& m0 R% B
    3. 汉诺塔问题( S* d! v8 a7 g# U
    4. 二叉树遍历(前序/中序/后序)" h, u  s+ Q/ }; k9 ~$ @
    5. 生成所有可能的组合(回溯算法)( H5 m! Z' u( p, o, T. i

    & y$ e# K0 x0 c( }4 \4 B( Q9 b) u试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    昨天 06:31
  • 签到天数: 3146 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,2 F$ p( N. Q8 @# E, d4 I3 D3 F9 }
    我推理机的核心算法应该是二叉树遍历的变种。
    : @9 q5 V0 v; `3 p7 Z% d- ~6 u另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:) f6 [! d" K; B) i* Y, J$ _
    Key Idea of Recursion, D; m  @; v9 `+ j' o1 I2 B2 |& w
    # D" V4 L, I; w  z
    A recursive function solves a problem by:% T" M  F+ ~% i) O
    3 B/ Z2 n1 G4 F) i* p
        Breaking the problem into smaller instances of the same problem.
    - O* P+ ^/ f  \: u/ B1 K. d  X! x9 s6 v! Q/ Q. Z$ o) b6 a
        Solving the smallest instance directly (base case).9 o2 q5 P; n( h
    7 }' g* t. V/ d) A# k) X5 J
        Combining the results of smaller instances to solve the larger problem.1 L0 o% S6 n7 H2 j+ ?6 P$ ^
    # m# l. N  G' f' }& y
    Components of a Recursive Function9 N$ N- ]. `% r1 X8 k# m

    ( N2 N! u; }! z* U: O$ s8 \7 d6 l& }    Base Case:
    - U/ ]# j( I' ]$ D8 f) n
    ! T& O4 \& U; c! J3 s7 ]        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    9 `+ A1 p$ c5 |) ]7 ]7 r$ Q
    0 y2 t+ N) t( R' }- p% A! q        It acts as the stopping condition to prevent infinite recursion.
    1 a; l# N5 g! l% Q, R8 m, a7 ], `7 z( l9 i4 Y* T
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.: _8 S/ y4 E7 J, J! N: U( f
    + J/ H4 x; t* F5 o
        Recursive Case:  O$ `  r8 j* O1 u3 U& A( M; K

    1 J8 n. Y) a8 ]+ I% i) ?; a3 c        This is where the function calls itself with a smaller or simpler version of the problem.
    . D, z3 k6 d- m+ ?2 N# ^; J
    1 m, B! u$ R- v! o6 }        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    / ~: c( q9 L' K( t8 O7 C: J& o; t2 o7 [3 \/ s* O
    Example: Factorial Calculation
    $ ?& u( x2 h: Y4 u
    1 a& U0 E! `) a  k# \% A" r& nThe 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:
    $ ~) U0 }3 o" l1 l- ^( d/ F2 I- ~, X
    # P1 J5 r/ {4 x3 `! g    Base case: 0! = 17 r8 J4 ~2 F* f: e% h" T* i

    & f+ E! P2 H6 C# n& {1 G* P    Recursive case: n! = n * (n-1)!# @, x9 A$ Z4 |$ c' z1 M: e

    ' Y6 b' p) e8 ~Here’s how it looks in code (Python):  j" [# J4 v: Q2 l/ m+ v
    python
    " X9 C1 [7 w8 K! G8 U- z; t# {7 x: |) _: ^

    ( Y# _( [6 ]% _# F8 Bdef factorial(n):0 b* _( f/ O7 j
        # Base case
    / \( n. `, C0 d" Y+ V9 f9 r    if n == 0:8 p8 A" h% M5 V7 ?
            return 1
    ' U0 l% c1 A' ~% @    # Recursive case
    ! u& ?( }8 B6 I( \! ^    else:
    ' e# L; M" V# p: v" z) o        return n * factorial(n - 1)" m6 ?: n- X# u8 \
    , w* O9 k# X7 A
    # Example usage
    ' Y2 d+ l4 V* ?print(factorial(5))  # Output: 120* d! V; N3 z$ x6 h2 u5 H- {

    6 l9 o' ~5 N, ~6 Y  ~How Recursion Works
    & K" i4 c3 {. B! r. \! n) g' Y% L5 `$ |- o2 _
        The function keeps calling itself with smaller inputs until it reaches the base case.1 v; ^, }! r) V+ j
    - w" [8 q( f5 d9 X( ~/ }* O) z
        Once the base case is reached, the function starts returning values back up the call stack.. L4 U$ @4 F; |$ n  b4 r3 M% j

    ! @& D' `; H/ ^- P  L6 o2 J) G    These returned values are combined to produce the final result.
    ! i9 B* R3 v# \5 y- J( ]3 m% s! U1 T1 [- [; J9 _2 ^) ^) L2 L, x- o
    For factorial(5):
    ; v0 k3 ~* F" d6 h+ `7 P5 U1 f
    1 |1 \; p1 S, Y( x: f' ~
    ) }" q2 p! e; F" R7 F6 p+ Gfactorial(5) = 5 * factorial(4), V1 m) A* A# t' f+ o
    factorial(4) = 4 * factorial(3)5 b% e" d* m# `
    factorial(3) = 3 * factorial(2)9 l: n9 q' N* E' \
    factorial(2) = 2 * factorial(1)
    : N: i5 T6 [- R: [7 {$ v$ \factorial(1) = 1 * factorial(0)* r' m; T1 ~8 i  M/ B* d& B! p& y
    factorial(0) = 1  # Base case! f+ |! o& h5 w8 j6 v2 e8 h

    5 V( k! Q& c( Y5 T( i( s, AThen, the results are combined:
    # D4 Z3 G3 s3 ]6 ?2 u: [' F; n) `
    % w4 ]! |" n/ M8 u  _
    ' b. f! |* X% L" V, p# r" C) P+ ffactorial(1) = 1 * 1 = 1
    + z$ }' g5 x- [! R' Mfactorial(2) = 2 * 1 = 2+ R% W! |# G9 N% |& [9 I7 m
    factorial(3) = 3 * 2 = 6- B$ k) l% i! ]0 @
    factorial(4) = 4 * 6 = 24
    / k4 g5 n1 T+ ]: F: ?factorial(5) = 5 * 24 = 120# s+ H( }3 a( i7 \% j0 \) e

    7 x/ _/ ?/ Q, ^% b  n8 [Advantages of Recursion
    1 K5 ?  u8 X5 U6 |  P. q9 V0 u
    & y* y$ C, c; Q' o9 g    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).* [1 U$ n" B) O  x# W5 \$ l! C
    ( `; p* v/ W, R) K) [# X
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    0 L7 q0 V, C* `6 |0 f
    " d( @# M0 L5 ?* F; f, m6 yDisadvantages of Recursion
    : j" O) ]% V3 M" p* `3 L8 R: L, b/ C/ X- P. m! `  L& Q7 V
        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.
    : k6 ]( k: I6 T! \4 Z
    4 y( h+ x$ @# g& \5 ^; @- s    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization)./ \2 L& R% ^9 {: c" @; x3 b
    + Z& [5 B  ?# D9 W3 r
    When to Use Recursion
    , ?0 U7 e3 s7 y" |) [8 b
    6 i* {  b0 P# K  Q    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    # w2 c6 F8 L4 }$ V4 r
    " w; W$ K, p2 @; D- ]4 x9 k    Problems with a clear base case and recursive case.2 b$ I/ ]+ ?! R
    . _" A4 A7 r& a9 q# O
    Example: Fibonacci Sequence+ o* y* u. v# n5 t

    4 M& L" I0 _" b! z& PThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:6 O! W2 R) @8 p" h: ?
    . }& u9 E9 q. X0 \
        Base case: fib(0) = 0, fib(1) = 1
    / ?( a7 o5 d2 {; c4 R1 s# x. o1 Q& P+ t! G
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    $ n' p& r+ f. K7 p# O- B. f7 z, m5 R
    python% h7 C. N) f" L7 k2 J! _  i8 Z2 b/ M; {4 I
    6 p, [. b- \0 `
    3 G3 p5 e  u& d0 m5 j
    def fibonacci(n):6 |" w, g3 p& K# R3 t
        # Base cases
    + i4 W5 O2 W* v+ k! s! q) J9 Z7 O    if n == 0:- r6 X- c# u. H# M) m! @# I; Q4 ?
            return 0
    $ ~3 S3 m3 L9 m) n9 L+ Q$ f* G    elif n == 1:# \8 q0 S1 h, N6 V
            return 1
    - P+ Q& ~- J; F, e/ ]4 i4 y    # Recursive case! @* J+ o' _7 |  u2 F* i
        else:
    9 ^  c; E& v9 \3 h' b7 C        return fibonacci(n - 1) + fibonacci(n - 2)
    # T0 V  r- U/ n. U  F0 e( s
    9 j5 a6 n% h! L# Example usage0 T; p# p1 ^& g" M- F
    print(fibonacci(6))  # Output: 8  T+ |3 B* M# w

    ( a4 R2 f! ]0 V  T( ETail Recursion/ w: h( x2 Q( |0 F6 _

    8 b* [( W, `4 o9 [$ |+ ]' O2 oTail 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 t  l1 r( Z, Z, R( ]$ v

    ( F* U. Z. m  g  w8 lIn 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-15 03:46 , Processed in 0.029877 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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