设为首页收藏本站

爱吱声

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

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

[复制链接]
  • TA的每日心情
    开心
    2015-11-30 11:11
  • 签到天数: 2 天

    [LV.1]炼气

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 ; t& [/ N) G8 t( q% D# g6 T

    % D2 }; J+ \, k( ~2 d+ S( a解释的不错0 @; C) p- Q. l  s, e0 V
    " ?8 t, Y+ U0 K6 B8 x/ [" {9 E
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    + f% w2 S* l3 L7 l2 E5 q
    & r; g$ Y7 J0 v( `' i 关键要素
    ! }" J: f) Q, [) ~/ E0 g! y) K4 `1. **基线条件(Base Case)**
    . h+ E2 I! |' C- @0 e   - 递归终止的条件,防止无限循环- G# Y; ~0 n( t7 w1 ^3 \
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1, J! l  T( i. R# b" e+ E

    # D5 P1 k7 g) X; d2. **递归条件(Recursive Case)**
    ; t$ \+ R" V9 E' X2 k   - 将原问题分解为更小的子问题' a2 P- l5 V& E$ S, e9 e
       - 例如:n! = n × (n-1)!
    : ~: E/ y3 g: z" o) o' a, U+ s
    7 s$ v! x4 ~! l  ?' |0 ~ 经典示例:计算阶乘) d" S7 E% w& f- J
    python3 {3 {$ l. l- d" ?# O$ E4 z* P
    def factorial(n):) C( w' F" _4 ?5 v) `' q  O' m# i
        if n == 0:        # 基线条件" X! T9 F- A4 T7 C
            return 1
      f! \$ [2 J% W: Y- v    else:             # 递归条件& F9 r. Z$ m0 ?+ M
            return n * factorial(n-1)7 \4 O" Y2 c6 t; N2 ?2 K
    执行过程(以计算 3! 为例):6 l: s  r  ~0 I* Y1 J5 q( S0 L
    factorial(3)
    / b2 {/ e0 V. ?  r2 G3 * factorial(2)
    ! [" L) T  D7 N8 z0 z3 * (2 * factorial(1))2 C- A0 _8 u; ]
    3 * (2 * (1 * factorial(0)))
    - `: v. t5 x$ {; p3 * (2 * (1 * 1)) = 6  U) ?. o3 l8 I5 l; W( E

    & r4 e* I0 k& f0 V9 X4 S, v 递归思维要点
    5 g  z5 o, p8 U6 u% I& x1. **信任递归**:假设子问题已经解决,专注当前层逻辑) M9 z) q+ W1 N9 c$ a$ Y& X1 r
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    . ~; ^# K/ m% w& D# P) y" j3. **递推过程**:不断向下分解问题(递): }' Y: F. u- p. e2 J6 ~
    4. **回溯过程**:组合子问题结果返回(归)/ y! c0 F5 v8 }6 |

    0 g) ]) {  M! x( r 注意事项
    8 r" }6 v1 b& z# M6 Q必须要有终止条件
    0 Y4 c' M% {% Q: f2 G, g( W& L递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    / i! n  b4 D) Y: b某些问题用递归更直观(如树遍历),但效率可能不如迭代4 ~1 ]% R0 g# Y" G( K3 j5 [$ Y1 i
    尾递归优化可以提升效率(但Python不支持)5 s9 ^! H3 m" |; ^& {9 p0 H

    ; m8 A+ A+ s+ Z1 j 递归 vs 迭代
    - t8 C+ G8 j/ _3 z|          | 递归                          | 迭代               |4 p$ _) i- q" i3 \  z
    |----------|-----------------------------|------------------|- p1 {* p# I; R% q
    | 实现方式    | 函数自调用                        | 循环结构            |
    3 `, D7 t* W- {9 I: p2 E6 B# ]| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |& O) s; Q! M# L5 g7 t- x
    | 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |; v/ R# ]0 m( {- M# {1 ^  r: T
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |$ K; i& l, o+ j: I( d, r; g8 E
    1 ^2 K+ F. O4 \. h
    经典递归应用场景, J# _, y1 w1 V8 n% k4 A
    1. 文件系统遍历(目录树结构)
    3 L, e& W4 b7 G% l, a2 W2 L2. 快速排序/归并排序算法
    3 t6 V0 R: `. K6 Z) Z3. 汉诺塔问题
    0 s/ h0 c* L  m/ h2 t; D- \4. 二叉树遍历(前序/中序/后序)5 Y8 q8 \& h0 p& q' F8 g9 r" J3 N
    5. 生成所有可能的组合(回溯算法)
    ' j% K* V" U! u* E4 R
    " ^5 f+ Y* @" i" U试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

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

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,7 _# i4 y$ g, w$ \6 `/ ^
    我推理机的核心算法应该是二叉树遍历的变种。
    ( o1 J/ x% f- `) C5 ?- a% T另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:2 c) F* |5 f- X$ a8 ?1 s
    Key Idea of Recursion5 h# Q+ v0 m' R  D( Z; t' @9 z

    : v" k) {0 h+ s. {* _9 OA recursive function solves a problem by:' P+ Z4 Z: I, R8 m

    2 J2 J) x, ?8 E    Breaking the problem into smaller instances of the same problem.
    ' O3 |) ?! `6 f$ Z1 H. w2 V* O& Y- W- a7 S
        Solving the smallest instance directly (base case).
    7 \1 T& b1 R+ x; I" o
    / W8 f5 {) E3 x% U. O    Combining the results of smaller instances to solve the larger problem.( y! t4 T, S3 k/ J! `/ m  V

    7 f/ Q5 N) g; `Components of a Recursive Function" a8 w6 A- F# o

    % Y6 x- l, ]  a! \, K3 n" Z2 o    Base Case:
    8 h) [1 ^3 P- j, \
    2 d- |/ f5 C8 g        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    6 {6 l% i" W, a$ O2 {1 [; e( D3 B0 o
            It acts as the stopping condition to prevent infinite recursion.0 J3 V, H6 {' t0 g1 _& _, {8 C3 a

    / P# w/ z9 p, t# C5 k$ \1 d7 n        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.8 h6 R) H( A" l" b
    . n/ e% }+ W* m
        Recursive Case:
    9 o' x- D" r5 @$ U
    $ H0 i/ S0 A( e. E( w+ E% g9 w) G  Z        This is where the function calls itself with a smaller or simpler version of the problem.3 L" {7 z3 v# J) y5 f% y$ Y; t

    ' w, Z7 g( s% n5 a( N4 y        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    7 p$ ?! ^5 O1 c1 P% h' y$ c
    " ?6 z" h2 h/ o4 DExample: Factorial Calculation
    0 R) ~! a5 _+ e8 O& M5 J6 g/ {4 _: U2 s% ^* H! {* C
    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:
    0 R/ H. b' f* A; |; p; u
    ! a: W6 ^5 G9 @    Base case: 0! = 1
    % r, g; [# g  Y
    0 a. {+ U8 s- Q- W/ |: R/ R. u* B    Recursive case: n! = n * (n-1)!& ^9 V/ L# G% j6 O. y2 B4 ~

    0 N/ M" h, }& @1 y& P, O# zHere’s how it looks in code (Python):& ]" y8 C) z' C- p8 u* f# X( ~
    python
    - ?. `0 K  D; @! F0 i% b7 j& d, O3 s3 C4 z  g, i; c2 B
    ! K& p) N8 V3 I
    def factorial(n):
    ; E1 G! _$ m: B; e    # Base case
    + }( n+ t5 D; Z    if n == 0:
    - y9 Q# ]) w1 q2 l        return 1
    ! j5 J  @, i  x' e! x; c' c) a    # Recursive case$ S6 v. c4 ~3 O
        else:9 }$ X1 J4 K# N! G2 H
            return n * factorial(n - 1)3 Z: {, G" o/ k

    . G  ~2 o! C8 Y! @1 W# Example usage
    # k; O" Q" A) C5 N+ b6 }* ~print(factorial(5))  # Output: 120
    ( W3 ~2 f9 z( o  P
    / ]. ?+ G2 m% C# _1 VHow Recursion Works' ?0 G" Z0 l1 N
    % `' r( [# v! N/ M
        The function keeps calling itself with smaller inputs until it reaches the base case.- M2 h' r' C! h2 f0 ~

    9 M/ ^; X! e: r, S    Once the base case is reached, the function starts returning values back up the call stack.3 d/ f6 z! V( y4 s  f" @+ o6 Z7 m
    # n3 n3 X% L3 T$ g( a4 V
        These returned values are combined to produce the final result.
    3 L" e0 T1 u) @& A) ]. M5 O0 a  G
    + t) Y. s: o& b( Q1 jFor factorial(5):5 q6 \$ Y8 P+ k4 V3 C
    8 v7 U& }: i  m& `6 w
    5 D. H  E2 [( J4 m
    factorial(5) = 5 * factorial(4)
    : C2 R/ C# [4 G2 Sfactorial(4) = 4 * factorial(3)3 N! @$ H6 ?: L" _* U
    factorial(3) = 3 * factorial(2)
    ( i4 N$ X" k5 Vfactorial(2) = 2 * factorial(1)
    . U1 H; R! i3 N" [1 Z+ @& _; dfactorial(1) = 1 * factorial(0)
    / m( E/ \; x( x; D. Rfactorial(0) = 1  # Base case' M: i: M0 }1 ~2 V- |
    ) t6 d! a. ~' g6 _7 R! g
    Then, the results are combined:
    9 E5 N8 a" {7 O7 ^# p, Q" C3 g
    1 A3 @4 g: h3 Y! e
    $ j- r1 ]/ p, e6 y! |5 I1 z8 D3 `! Mfactorial(1) = 1 * 1 = 14 p" e5 t% F: T; T9 ]
    factorial(2) = 2 * 1 = 2
    1 [: z5 f6 x% n% ]factorial(3) = 3 * 2 = 6
    - l3 g  ]: L- x* O; i1 C7 zfactorial(4) = 4 * 6 = 24
    1 M! t' i" z% a! @& W9 hfactorial(5) = 5 * 24 = 120+ i  E) e* A! q  t0 `

    3 P$ u( l7 I, r7 b& cAdvantages of Recursion5 r, d( p: W, a. a* q* C0 t
    & l* @3 U5 a, F7 y2 f2 \
        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).8 {) x6 w. \; s+ U. K
    6 V- k& v+ s7 X! W* q
        Readability: Recursive code can be more readable and concise compared to iterative solutions./ s' j+ a9 O+ u  w7 m
    1 i/ `" u$ L4 ?  x
    Disadvantages of Recursion9 ?$ v7 q: I) \

    ! ]- u; W% ?( e/ L; c: x- Q  C7 [5 O    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.
    ( p9 N5 g8 \+ s5 U+ N/ m& y
    3 e6 j0 O3 C+ U8 t( T, W9 T* u7 o/ ~    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    ! ~  s- s- U1 \0 z; f* i, r& J
    1 Q" V0 `3 j( R- \, Z! JWhen to Use Recursion4 F( c8 c# t- A. q" r% _

    ; H. u* t! }: U. f6 o. D. E    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort)." F: h0 C1 E  l4 S

    6 `+ I6 }' X7 Q    Problems with a clear base case and recursive case.
    7 m) s7 e! k7 k( A! n
    7 q# G( i, }% D) F+ oExample: Fibonacci Sequence
    % P# Q  o4 A! {( E0 v: [: q8 F0 ^5 N# `7 r
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    . a6 U  W! a3 K# P- P2 K; _0 ?, d$ Z. b/ q; Z! s# r0 G1 x4 J
        Base case: fib(0) = 0, fib(1) = 1
      }4 `4 C. ?  I5 `3 W, c( |
    6 P/ s" o1 M/ P    Recursive case: fib(n) = fib(n-1) + fib(n-2)1 c, T: [: b" K
    9 |+ P$ b% `* Q: n+ O
    python
    ' T- r# m+ u# o5 u! q" \$ L* }  c* \( C

    , M1 p6 q; Q# C+ J2 ]' ?. Tdef fibonacci(n):
    4 y' @# M9 b2 V    # Base cases- Z8 ?+ n  v5 g! T
        if n == 0:& o* B& }0 A6 A( K( a
            return 0
    6 W: ~! n0 e! F( \    elif n == 1:3 O1 l- X( @5 L2 l( Z* f
            return 1
    & x8 x* G5 }3 t( i# `    # Recursive case2 ?6 z$ u7 D6 z. y8 v
        else:6 X1 k% H2 T6 u2 Q% p% h( P5 d; @
            return fibonacci(n - 1) + fibonacci(n - 2)
    + D8 X. l: h( v+ C2 U5 g! X3 Y+ T; X4 S2 z  A0 H4 A
    # Example usage+ s* p3 \) R2 K0 N
    print(fibonacci(6))  # Output: 8
    7 o6 h5 k8 W4 T8 {7 }. e; ]) S' c' a3 R* E1 U' ~
    Tail Recursion% R& V* j" P" {
    ' E& y  L5 O/ c! m4 M
    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).! U5 V: I* N9 j7 U" t

    & P, O- F$ L6 O4 R& c: hIn 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-6-18 18:49 , Processed in 0.035451 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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