设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 " r6 z, I6 O3 c- ]" ~/ Z$ _- T& s( G; Q
    : r3 n) x  s) K& ~! O! S0 J& @
    解释的不错
    + L$ y2 b) W  f( n; u+ Z/ W8 A- }, R) L
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    / }% t5 P+ s- D# A4 k, H
    ) @, R0 u, y2 D2 \$ {' F 关键要素
    9 j( O. |7 S5 ^5 ~2 ~1. **基线条件(Base Case)**% L8 {& r" @9 l, q7 C% J. _& C! t
       - 递归终止的条件,防止无限循环
    0 h  S$ z& `; _8 g6 x; Q9 J- ^* o- w   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    . M5 F/ h% s7 ]5 C6 E& E- c" ]$ X; v! H9 {
    2. **递归条件(Recursive Case)**
    " v1 |; a- \9 f; z7 F' j, Z   - 将原问题分解为更小的子问题. c5 c; x$ r* I% v4 z  B4 W& e. s
       - 例如:n! = n × (n-1)!
    * X/ c8 P% J3 \* h& P3 ^8 Z  l' @
    . N6 I1 Y* Z2 d( d7 _  P" R" n% T  { 经典示例:计算阶乘2 H. @0 x+ Q1 I
    python
    ; {( |7 k, A) ?) S8 C3 Pdef factorial(n):
    : R0 O5 ^$ S5 x' M4 p; B3 u    if n == 0:        # 基线条件& `! d8 I% o2 m' Q  w8 D2 _
            return 1
      m$ X, g2 ?4 @5 l7 i    else:             # 递归条件
    9 D% D5 ~3 i" e5 }) J2 K8 E        return n * factorial(n-1)/ f7 A3 b% L5 H( h- D8 E
    执行过程(以计算 3! 为例):0 o3 @3 c6 Y1 r1 O
    factorial(3)
    % h+ Q+ ]6 k7 G! U7 N  T& a+ p3 H8 i3 * factorial(2)& f+ B+ _6 @, P- E! g( y
    3 * (2 * factorial(1))1 ]0 i3 f; n7 C
    3 * (2 * (1 * factorial(0)))5 {; m  z, V/ g% R
    3 * (2 * (1 * 1)) = 6
    ! H: |) K4 U& j9 e& N) \! Q) B  g; i- r( L
    递归思维要点
    ' N# t) _, o+ [* x3 _! @' @/ l1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    / n. V8 P0 w& w3 E, O- y2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    - h4 N! j" b' p7 f3. **递推过程**:不断向下分解问题(递)" P' w5 m9 }' T+ y; i+ G- g- N
    4. **回溯过程**:组合子问题结果返回(归)( ~, \! B; q7 p
    7 e" @9 ]: B* L9 i
    注意事项
    % B/ I0 M2 ~$ ~) A" u& T& A必须要有终止条件* W! s9 ^, d; E+ |( Y$ @' B/ n6 B
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)* g' A4 a% i( J5 Z
    某些问题用递归更直观(如树遍历),但效率可能不如迭代
    6 `8 p) i* M' z% l尾递归优化可以提升效率(但Python不支持)
    4 I* ?0 A0 e2 F3 x$ h2 n: _/ ]4 F) S/ Z- s# s" Q4 d9 ?
    递归 vs 迭代" Y( @' j* Y4 d' U. Z
    |          | 递归                          | 迭代               |  l1 Y5 j4 z6 @$ b: w* [
    |----------|-----------------------------|------------------|
    9 X* Y# Y/ I. R/ k' S9 C| 实现方式    | 函数自调用                        | 循环结构            |" S3 X9 L+ [; z' s+ P9 ?* R
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    4 S. f! D$ }! w# e5 T| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    3 r. G' a2 h  H- _% J1 R( i$ ]| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    6 I( F. i/ V$ V8 f: m) y$ G$ k: ^6 Y# g3 W5 @- C: J
    经典递归应用场景
    / b5 l/ N8 l2 c! d  [5 e. b1. 文件系统遍历(目录树结构)0 L. G& Z# j9 e& H/ \5 c
    2. 快速排序/归并排序算法) r+ V! E, Q% I  w' E$ l2 W3 I) J0 \
    3. 汉诺塔问题
    ( w/ i3 m+ J- x7 Q  N/ _! N2 ^4. 二叉树遍历(前序/中序/后序)8 A2 G, K" v" i+ i( |, O2 ~
    5. 生成所有可能的组合(回溯算法). V4 b/ {- u  l) P/ U

    2 q. v+ V9 _( \: w试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    慵懒
    昨天 09:26
  • 签到天数: 3225 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,% S4 P- ~2 r3 L0 l# I, @
    我推理机的核心算法应该是二叉树遍历的变种。* h& Q; K. v& \# a' g" b
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:3 C8 {( ]$ r3 X: T+ N2 C% V% o/ q4 E
    Key Idea of Recursion! ?' D" h, I8 l1 m( p3 G  s1 G3 `

    1 S8 Y5 e5 V$ E9 C: xA recursive function solves a problem by:
    0 C8 B0 ^1 U! m3 @8 A6 v
    . n3 L) U, G4 U+ ^0 u    Breaking the problem into smaller instances of the same problem.
    / U' K5 V0 h$ c# K, X% C7 l3 j9 j+ ^$ l" w  s& ^7 H8 A4 X% g
        Solving the smallest instance directly (base case).
    ( p2 \; V8 h3 ?# b; ?
    # D1 h- v! w6 q! D2 s- P" _    Combining the results of smaller instances to solve the larger problem.
    # L, M+ v8 q. G2 u2 O$ ~
    3 \3 _' ^" t1 ?6 {+ IComponents of a Recursive Function
    : ^3 }1 ^$ _; E
    , {( B, b, I2 K6 i8 M% s    Base Case:/ H7 }9 h  y: ~7 m

    / k! M/ K% ?$ j. r. ]4 _; v' b        This is the simplest, smallest instance of the problem that can be solved directly without further recursion.+ L: B$ \3 Z4 ?0 ^4 N; g4 m' i
      }8 L, o% T& w9 G: J# N6 m$ ]3 [
            It acts as the stopping condition to prevent infinite recursion.: X' D) s( S  F  M8 D- }+ Z
    # s) U: x0 P4 T' J2 m. V/ R8 J1 Q
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.3 O4 K$ v+ p" R5 R/ {

    ! `. F2 M$ v% u' @  y0 }& R# [* k. z) K, h    Recursive Case:
    4 n7 h, k; g9 [, H
    % g5 ~2 w' w) V/ i$ u2 u* z4 D        This is where the function calls itself with a smaller or simpler version of the problem.
    . V. o9 z3 p! G' F
    6 \1 c: g& {/ Y1 A- Q) ~# ~        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1)./ i& h, T; M5 }6 U! q6 C
    ' X" n1 r1 y& z, G, U/ L9 C
    Example: Factorial Calculation
    . C; d( d# c8 M  R; u. x4 ?
    * {( Q, Q) o. b* z- K, Y  qThe 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:+ W) J' H" I$ q+ H  E
    9 D% Z2 v; U9 u
        Base case: 0! = 1
    1 P& g: i/ v0 p( v. u
    $ t2 }& ^- l: I2 n: s    Recursive case: n! = n * (n-1)!
    & ~8 M5 P! B- Z: Q1 k- J
    / Q' M) e" ?* [. nHere’s how it looks in code (Python):. C& W, @1 h% E. }' \1 Z* o
    python. C8 c# v6 H4 b* k( A+ ~

    : d8 m- Q8 L$ O9 g) l* w5 g2 `9 }" o$ y% I, Y
    def factorial(n):
      k" M# ?- M- N- g8 p  B2 X% ?    # Base case9 D. u; [( h* k! u
        if n == 0:
    & F% q& k9 _' n0 h- I        return 11 o: s6 \; ?' R
        # Recursive case  ?3 H. N8 t+ `! H! f. r" y
        else:9 o- p9 ^+ j0 Q7 b/ U- {4 O9 s
            return n * factorial(n - 1)$ R# L$ H8 ~) f- s+ A. A( e

    ; B, d- ~' Z( x; s- v9 j- X9 {# Example usage
      {# f+ h+ x6 P+ ^8 O+ p6 Aprint(factorial(5))  # Output: 120
    / [9 v' u0 F# a- x0 g
    ; B; `1 L3 T8 A1 P  XHow Recursion Works( A0 v3 Z7 n4 z7 S" c5 B. H& X3 d! b

    8 N) l" Y$ m. X    The function keeps calling itself with smaller inputs until it reaches the base case.1 B8 Q. M7 \4 J  ?! a/ L9 s

    ( ~9 F# ^1 @1 |; @. S4 a! e5 B    Once the base case is reached, the function starts returning values back up the call stack.2 v7 g9 s5 D2 v7 m, k/ H3 A" m% t8 W

    ! n1 x$ g2 W7 d5 ^% f: a    These returned values are combined to produce the final result.( P' G2 U" l: L1 ~: S0 R
    ' N8 v' x# `. I" N1 e
    For factorial(5):
    * m/ [" {! \. O0 s$ [* X3 k2 p# M  A$ e/ V

    - e5 E5 \9 S  t; C$ Qfactorial(5) = 5 * factorial(4)
    6 \/ ^. V' j& Q$ mfactorial(4) = 4 * factorial(3)
    6 P; w1 s" a* m# f. V! Lfactorial(3) = 3 * factorial(2)( p& {% P( ?  D
    factorial(2) = 2 * factorial(1)
    ! n1 w- K5 F2 Y' [: K. R5 ]factorial(1) = 1 * factorial(0)8 s6 H, R4 ]' {! V# {2 O, P
    factorial(0) = 1  # Base case
    1 Y7 a3 P$ M" E1 D: u9 b7 V8 |; e7 }# q6 `2 i) {
    Then, the results are combined:
    2 I3 K% `* Q) i+ U% o9 x1 s, r4 Y- w$ y9 E( p. |5 y

    + T* Z2 N  v, Q$ N, b- sfactorial(1) = 1 * 1 = 1
    # d4 a8 W0 T6 r* e! I; T* `9 P' Wfactorial(2) = 2 * 1 = 2
    9 B8 p: c7 _0 Wfactorial(3) = 3 * 2 = 6+ ^. q1 F' r3 Q- K
    factorial(4) = 4 * 6 = 24
    " N& S3 o0 Z3 n( Wfactorial(5) = 5 * 24 = 1202 x& L! y( ~' Q: I' m! G
    . J; n" O2 N' `
    Advantages of Recursion, _* i  Y2 Z( U/ @; D7 g6 f+ e2 v1 P
    7 d/ V- z; c7 t+ P, O
        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).* a: d; I6 j/ i5 }; R$ w0 @0 l
    : O  ?0 R7 H) l( u- V
        Readability: Recursive code can be more readable and concise compared to iterative solutions.: h5 A' K0 e8 k, h. t

    + t8 Q3 v# _$ ~- P3 U- E6 {! D4 E& S: }9 \Disadvantages of Recursion: Q+ U* E8 y& N! J) J4 C
    0 ?; F* |9 d: M' x$ @  }
        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 G# q, l7 L7 J% m# L3 S. U8 s* E
    4 N# ?. ]( X' D+ C8 o    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    0 ]/ Z* s& e9 b! h+ d% d
    3 s' m" ~! p* f) o$ bWhen to Use Recursion
    0 ^2 a$ R: {; M% c7 e1 b/ I' [' c& ~, l3 L& }- ^
        Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).4 B. V" `/ k! e# \
    & D3 c0 N9 T+ [- E
        Problems with a clear base case and recursive case.; Z/ V. ^# Q; n
      V' O; ~/ i1 N  ?
    Example: Fibonacci Sequence
    - k, V0 G% W4 b
    : \' a+ L" G* _: M0 B: o2 o1 ~The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    7 E2 C$ L  l( c
    8 e* l, Q- O3 K% ^+ K+ C& N    Base case: fib(0) = 0, fib(1) = 12 E, E. T8 a3 n, M+ C

    $ A7 c' n5 E+ F    Recursive case: fib(n) = fib(n-1) + fib(n-2)# ]0 |4 [1 ~' V: V( g4 P
    8 Z% u5 G, [( F& `9 P# u+ q  v
    python- I2 X, X; f  U$ u& N, j

    ! y* q! {, n. T+ X) R7 y
    " B5 W! R9 \, n6 `$ d' S3 V' Qdef fibonacci(n):
    / Y2 o* a$ [1 o5 X    # Base cases4 i! I! P9 y) b' z: ]' k
        if n == 0:, t- Y% c- b' ?3 i7 Y' X0 z3 y7 T( D* E
            return 0
    2 o" i. L' L$ O9 [    elif n == 1:
    ) b1 h. l" |/ y" l0 v8 n        return 1
    - G$ d" C$ G2 J% x% [. t& A- n& O    # Recursive case
    8 I% P% T# U" V& F( j& E    else:1 {7 |% A: f3 J$ N  p" k5 `
            return fibonacci(n - 1) + fibonacci(n - 2)
    ; \9 k0 }5 D8 S- I
    0 J& H2 S  y: V# R+ z# Example usage
    # v+ }# T  \0 j9 N% w9 dprint(fibonacci(6))  # Output: 8' \6 I; H% C4 J# e! N/ [5 O+ w

    * |2 o3 @7 V; ^+ s9 ]8 L/ PTail Recursion0 R( d; p- c+ E5 L
    2 P" Q; x& t8 u
    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).
    : m6 H% H7 ~0 _4 ^1 g1 o0 D5 O' O1 `+ A: n' g. n' t
    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-4-29 07:15 , Processed in 0.069337 second(s), 20 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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