设为首页收藏本站

爱吱声

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

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

[复制链接]
  • TA的每日心情
    开心
    7 天前
  • 签到天数: 3 天

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 + N# G+ N# c5 ~' B

    2 K  t7 b: r( X, c2 Y' [3 F解释的不错
    / ]0 E% @9 ^2 c  S2 Z) h  v( w& \4 N0 t0 |/ g: U+ G
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。- z- w+ u% g) ]4 ]) t' d
    ; ?! n3 f" M$ B- ?' A
    关键要素
    ( R% X) Z% C2 t1 W$ y: v1. **基线条件(Base Case)**
    $ r9 j2 j& C4 \! \$ y. f   - 递归终止的条件,防止无限循环
    / L9 _% b+ H8 S6 O# L   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 10 P7 m( l+ E5 U! a

    & M- j* t8 `2 I; ]2. **递归条件(Recursive Case)**+ B, w! V0 S( Y8 J. s& g: P
       - 将原问题分解为更小的子问题  j( H, k# {( x- _8 p
       - 例如:n! = n × (n-1)!
    8 Z7 H  l" v( E8 }7 [5 L2 V/ O4 H& l/ r3 T
    经典示例:计算阶乘
    2 R/ h1 S! G3 b2 ?7 f) H9 m+ Hpython: @5 J6 @2 T% h' U' u. M
    def factorial(n):
    1 H7 Y6 s) E" {$ R    if n == 0:        # 基线条件/ X1 R  P* t# `, A2 E
            return 1
    ) m; Y' b4 ]- z5 @* k    else:             # 递归条件
    - I3 n! g( \+ ]        return n * factorial(n-1)  Y5 W) y& [4 C8 b! p) O* P  ?
    执行过程(以计算 3! 为例):
    $ W  |6 i* X+ m* _7 kfactorial(3)
    * @6 p0 j# I" W6 Q3 * factorial(2)
    * w  j9 R7 E# z. B5 r3 g0 j% ]3 * (2 * factorial(1))
    / M" U" n6 O% T* H3 * (2 * (1 * factorial(0)))
    * O8 _" B7 j8 \/ q# S3 * (2 * (1 * 1)) = 6' d- {2 X. M" U1 W. W
    & O& v( n1 ]9 t) ^) R  L) ?: H6 _  P& Z
    递归思维要点
    . }+ ?: |; x. d, K1. **信任递归**:假设子问题已经解决,专注当前层逻辑5 }0 p' B; @- x& y
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)! T2 ]5 }0 }3 h& L1 r6 n/ t5 z' ^# x
    3. **递推过程**:不断向下分解问题(递)' J* y  c- Z+ {% B  k' H
    4. **回溯过程**:组合子问题结果返回(归)# B: b' s) K$ g" \( T
    + G2 j- z* q4 q* O$ |
    注意事项
    , ^$ J7 e4 R1 z5 G, R/ q必须要有终止条件
    . {+ o" i- Q1 f- b% u递归深度过大可能导致栈溢出(Python默认递归深度约1000层)  E# e$ d* X7 i6 M: O$ d9 E7 K
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    4 i" t8 H& O! O0 m; z% w尾递归优化可以提升效率(但Python不支持)7 i$ ~, h5 Y' N: d* i- j; ~
    9 E) x9 u+ R0 K' Z/ }, ~
    递归 vs 迭代, N7 O. Z/ z9 ?9 X
    |          | 递归                          | 迭代               |
    2 ^- t9 x- @8 b|----------|-----------------------------|------------------|
    6 }; Z8 K9 W9 I; f/ i, }& z+ K! `% k| 实现方式    | 函数自调用                        | 循环结构            |8 f/ B" G$ l( K* ?8 e5 o
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    : G5 m/ L8 T) t$ Y8 o; t+ M| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    # b# n  i2 e; V/ z) b9 k( G* x| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |) z# c+ j" }) P, a5 C+ P3 N

    / A3 o. H% h0 O8 @; F8 I 经典递归应用场景
    3 ]# Y& c# j/ Z1. 文件系统遍历(目录树结构)
    $ Q8 S; K5 S0 f4 O1 K. Q2. 快速排序/归并排序算法
    , Q- L/ e8 x% z. S9 L3. 汉诺塔问题, ]$ ~. E( }. e. b: Z2 Y: a
    4. 二叉树遍历(前序/中序/后序), B% m9 y& G9 I7 H/ k$ x
    5. 生成所有可能的组合(回溯算法)
    ( u7 I$ @3 _. v; H0 c
    0 L* `: M5 A$ T. w% V试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    23 小时前
  • 签到天数: 3041 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,1 K5 u  M2 X% O! l5 U: a0 K) W
    我推理机的核心算法应该是二叉树遍历的变种。  R9 T' F5 l$ N, u5 q4 R. v
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:7 z+ R  o( w& M4 G9 e
    Key Idea of Recursion
    2 o7 X3 G' m: L; F/ V
    ' q: @% N& z4 `, d! Z$ }8 f  X# xA recursive function solves a problem by:
    : J5 R, @7 A5 s$ S( P+ o" Z
    " s- N  \& v0 S$ v( w    Breaking the problem into smaller instances of the same problem.
    " n. g/ a5 {0 Y# t; ]7 e% p4 s/ n' u# }4 K# R
        Solving the smallest instance directly (base case).
    % i% _& ~6 A+ ^
    : A, _% h& P, L4 k    Combining the results of smaller instances to solve the larger problem.* q) e7 m! H* l$ J3 ^+ S; ?# H3 o
    ( g4 @  `$ u. {& z- S0 B5 O
    Components of a Recursive Function
    ; L6 @0 o4 a4 z0 j* q# @. N! o6 X4 y6 [/ D8 {0 z6 c6 m
        Base Case:& [3 U* @8 |" R& ~

    6 W; y0 }! }( j+ t        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    / k( K4 Z% k4 R9 ?
    % w9 e4 e; P" M5 b        It acts as the stopping condition to prevent infinite recursion.
    0 p* A9 e, E" i8 |- H7 g, ?6 s
    3 P/ w  ?- q; k& _2 Z) S0 b        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.: R! G; x  M6 P% F0 j, i! o( N! R" P
    % e4 S8 b$ ]: L' u, i! [
        Recursive Case:
    ) v+ e6 B- \0 q, u6 A5 l) K6 q# v; G
            This is where the function calls itself with a smaller or simpler version of the problem.
    1 u" r3 g. G! j
    : u. P5 M) @0 c* A        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).% [" Z1 B) Y! I. y9 \6 j0 I

    # |" L7 S5 ~  L& b3 LExample: Factorial Calculation. z: v! s) Y' V

    0 j, J# Y/ G; mThe 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:2 {( w* `  p0 g4 c; U7 N( O) n
    % c2 j. M1 B4 |' n3 B9 Y1 j
        Base case: 0! = 1
    - O% `+ p6 y/ }: L% k. i( Y: Z0 }
    ( K% c& z1 f- J( e    Recursive case: n! = n * (n-1)!
    0 |* C1 c- p. ^+ ?" R2 ^
    ! {! j- v; s9 a/ N2 }* rHere’s how it looks in code (Python):
    0 {( j2 S; S7 _' Apython
    ( \' s9 O4 e9 n: U2 j2 R8 p. @% z" f5 @. U) D5 }! I# ~

    . B1 h9 T' ^3 Z- `) ]5 P# ~% r/ zdef factorial(n):
    / \& K* J4 Q+ j7 G) t, t- L+ t( [    # Base case
    5 A( z: H8 n4 ~4 n    if n == 0:7 L- n3 |% u2 `- j" D. B
            return 1
    ; |7 H* B5 ]1 _1 u+ S    # Recursive case
    - d# }$ ?2 l5 Y6 Y% Z    else:
    6 [1 s) C% N- n" z6 ]9 ^9 R( S        return n * factorial(n - 1)
    $ s5 i3 |8 }8 N' S
    0 `, O3 l# ]8 k# Example usage
    7 g4 F( ]% W* H3 K0 N: J, U) s+ ^print(factorial(5))  # Output: 120
    - @# t3 `7 X- s1 O1 A* B
    5 w2 `  ?. @4 jHow Recursion Works: c+ I+ p8 {5 X' k

    ) T2 r3 V. `) @4 p    The function keeps calling itself with smaller inputs until it reaches the base case.& E) q) B* n) ?4 W( X

    " a3 J6 q% i1 X! F1 `) k7 T/ C    Once the base case is reached, the function starts returning values back up the call stack.
    : c& w. ^! x: ~
    & J5 k8 N. D) W4 V7 E    These returned values are combined to produce the final result.
    # y+ t) C0 `) _+ b
    8 I+ Y# G8 _) j; K. _3 w" G! n' QFor factorial(5):
    " q# ~& p6 |" D5 Y1 R& Q3 L2 c2 H1 L

    # |% U, _, m: M# gfactorial(5) = 5 * factorial(4)0 U  L% e. @* S# n( x
    factorial(4) = 4 * factorial(3)
    ( F  X2 A4 D9 L+ Lfactorial(3) = 3 * factorial(2)8 q& J% a9 F% O4 Z3 x; U' A
    factorial(2) = 2 * factorial(1)" r9 p4 ?6 s* _
    factorial(1) = 1 * factorial(0)
    9 N1 t1 b# E) Wfactorial(0) = 1  # Base case- h* N; k4 J; n. c  l3 F7 A/ |% @

    $ L2 M3 R1 j3 \) c: V) S" A0 i  cThen, the results are combined:
    - |, o; X$ o) w+ z) u2 x& a0 B
    & N2 X* U3 d  z  y# M0 N6 d% P. \0 j, Y1 N% a$ o3 s7 M. E
    factorial(1) = 1 * 1 = 1
    5 b4 p7 q$ K  U. nfactorial(2) = 2 * 1 = 2  \' s! k# b2 f* W" d5 u. N
    factorial(3) = 3 * 2 = 6+ i' l% t6 V  [4 e! ^. L' {5 E7 _
    factorial(4) = 4 * 6 = 245 s9 A: g. {! X/ h8 a( J1 ^
    factorial(5) = 5 * 24 = 120
    0 Z9 T) c8 o+ C' y( _6 P% ~" m2 Z8 h) T$ q# }2 t) O& O
    Advantages of Recursion$ p/ B5 B3 t5 X$ T5 L( H
    5 V3 d3 d) a4 z0 Z7 E
        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).
    * L, I9 m& x8 {1 n! r
    8 c, n. d! P+ k! x( c( _; w" l    Readability: Recursive code can be more readable and concise compared to iterative solutions.
    . a3 n. N4 V/ J
    ! Y4 Z2 E! b- D7 R" zDisadvantages of Recursion) B/ ]- `" K$ l

    7 z0 g$ h# v: T    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 W2 n9 w: ^% P+ J* E1 D; x
    9 W& w' f- x8 m4 @    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    # |' ]2 f2 Y# o2 A+ D1 p
    7 O! o$ ~5 V& [, v- hWhen to Use Recursion
    : E9 I  f* i0 k9 S
    ' ]+ p# ]9 C  K' }    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    6 l2 f5 F5 q# |" h
    ! A. c+ a7 S- s  i1 g. P    Problems with a clear base case and recursive case.
    1 ~3 K6 n8 _9 e( m( U$ p1 [# b2 H+ k( h
    Example: Fibonacci Sequence
    : ^; v" e+ n  I  y6 ^1 B! K0 V( z3 l/ E& Y1 n6 M! t
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:% o0 @  {" b; O, o1 A9 i4 H& B* b

    ' a) D9 \4 r# h1 K, s) M& b6 K( _    Base case: fib(0) = 0, fib(1) = 1- u% j3 r- ]7 T) y. h1 t
    ' F' R1 K3 U" {) t
        Recursive case: fib(n) = fib(n-1) + fib(n-2)0 h! c) y+ i# |6 u' p3 C

    - p1 ~$ k( h( c; s9 m7 ppython0 p. r8 J+ m8 t* I0 r7 ?

    - Y% B7 g% `3 i$ n$ E! q
    0 Z! y6 U$ O0 K$ edef fibonacci(n):
    ! h+ d4 i7 g" r    # Base cases
    0 D. j, L2 J5 M& k1 g8 N% b    if n == 0:$ k3 x; i6 r4 ~7 M+ F
            return 0% E. q5 }( i) T- o
        elif n == 1:3 J( [* t8 Y% b  }% ~, e4 O
            return 1- i7 s6 r  o( s+ I) f+ d
        # Recursive case
    5 s( T/ E. u! J+ i* q    else:+ ~& L9 Y! ?$ h9 P/ P; v
            return fibonacci(n - 1) + fibonacci(n - 2)+ d! ?) [( W9 i+ y# K

    , ~' O6 P$ J( _4 G, K" t# Example usage+ Z2 u- Z0 n" r; T7 V$ i) U: L
    print(fibonacci(6))  # Output: 8
    & }" E1 F9 D+ N4 i: ?( j/ O7 G7 s2 `
    Tail Recursion
    + Q9 G; y5 j7 O* ^5 t" a% L
    & m# t: \- j$ W: |! v* o5 CTail 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).6 L( Z! z4 `" U
    ' ]; `  E) X; M% Q
    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-9-15 23:10 , Processed in 0.040644 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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