设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 * O, k- `* O2 U1 ~5 D' b; M

    8 D3 @6 m9 G) _' f4 I: E解释的不错+ n5 I5 g$ O+ _( K" `. r3 F

    8 I8 U1 `$ L& m3 w# v递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    7 p: ?/ }6 e2 Z; i) C) ]$ A
    2 s0 g- |. J8 @% k! M# \& \% S 关键要素* K8 I$ J4 I0 q1 c4 H$ {
    1. **基线条件(Base Case)**& c; m" S" K& j/ c$ A  K! ^# o& Z% }
       - 递归终止的条件,防止无限循环7 H; t% C* s2 g, s% `1 l
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    + g- P2 k1 S) H0 v" ]# m  B. p+ m* V9 M, A. M" O4 Y
    2. **递归条件(Recursive Case)**2 }  Q& y$ s6 q# t) Y# m5 [
       - 将原问题分解为更小的子问题# g% h" n- E6 A* ]
       - 例如:n! = n × (n-1)!
    0 h3 x5 {$ P0 k. A" Q3 @0 s' H9 H5 l' D# m5 e3 Q
    经典示例:计算阶乘4 b. C& J/ b, I& {2 c! i- f
    python0 X: ^5 j  o* r5 Z
    def factorial(n):* h7 @: Z  H$ |" B5 ?% u" u
        if n == 0:        # 基线条件" p6 R4 B1 H7 X, L
            return 1  s. u& l. j4 R" ?" A
        else:             # 递归条件
    5 r) l! x" o9 T1 p        return n * factorial(n-1)# n2 {/ m- Z$ _" P% C- S. b# c
    执行过程(以计算 3! 为例):
    3 I7 P7 X# G( `! E4 tfactorial(3)
    0 u8 o9 t8 D( j( }, I2 @+ ^& m+ H3 * factorial(2)
    9 s% v9 x. n, E# _; G& U+ T1 t3 * (2 * factorial(1))# W1 H- ]) a  I) B' \2 e
    3 * (2 * (1 * factorial(0)))
    ; K& M" r6 K$ a1 f2 {% K1 }3 * (2 * (1 * 1)) = 65 p+ f6 ^; j+ y+ u9 H9 ?$ w0 N
    3 |1 y8 T" \3 Z8 x' R. z& Q
    递归思维要点6 K7 ^7 `" x) U0 V. G0 I
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑  |3 ~$ M" }# e+ Y' ^$ ]
    2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    5 @, V' Z! b) ]9 f6 J3. **递推过程**:不断向下分解问题(递)$ V/ Z! j2 U8 C5 U6 e8 n
    4. **回溯过程**:组合子问题结果返回(归)
    + }* S- h2 r5 B# v
    * ^8 a  S, S! @/ k: I, m 注意事项9 u4 o. m" s( j5 d: Q; I' P
    必须要有终止条件  H, G) V  @/ u3 ]( ~* q6 Q
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    ( m9 U" w, M! x1 X$ k$ E某些问题用递归更直观(如树遍历),但效率可能不如迭代2 P' o5 S  U8 o& W
    尾递归优化可以提升效率(但Python不支持)
    9 O8 x, q( w4 p7 E. q9 A9 \/ T5 @% g  F/ `8 ^
    递归 vs 迭代/ Q% Y$ H7 O: i4 n! ^' m
    |          | 递归                          | 迭代               |
    9 b5 E- p1 \0 S% s/ r/ `|----------|-----------------------------|------------------|0 ]  u+ m8 |& h
    | 实现方式    | 函数自调用                        | 循环结构            |. ?) }; y# ]# w# p5 t7 q( Y
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    6 {2 d% a3 O2 H$ h| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    0 n+ ^( O. H/ \/ {  H* h& f& U$ H7 U( S| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |6 a& Q' M! T& u$ u$ q- d

    ; ~% i& G+ o) J" \7 y+ B- Y 经典递归应用场景
    " M2 C( ?, Q5 E" ~& G+ M1. 文件系统遍历(目录树结构)6 ], r- c7 a8 H
    2. 快速排序/归并排序算法* k5 p( ]2 w% x" U. W0 z6 k
    3. 汉诺塔问题
    : c, i0 ~& l0 s" S4. 二叉树遍历(前序/中序/后序)
    # o' V, a- ?+ Z- T' z! Y5 L2 x9 M6 o5. 生成所有可能的组合(回溯算法)/ F4 [1 i# ^% Q+ }3 t

    6 m3 n! v5 `: ~" o, s1 n$ m5 Z- L试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    无聊
    3 小时前
  • 签到天数: 3191 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,! l5 S1 [7 C/ d( r
    我推理机的核心算法应该是二叉树遍历的变种。
    # z$ S) r  X8 t& f另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    * H& y$ I$ b5 @2 @. bKey Idea of Recursion' o) x; o: Q& r7 O: N
    $ k% Y$ G7 _  G4 `, i. C* b
    A recursive function solves a problem by:
    ! }4 a- F  i' b" B. r& t8 k$ q+ `- a) _" o% Z1 f7 E& m# V
        Breaking the problem into smaller instances of the same problem.& a2 G( K& q) `
    ( l3 B3 Q% L9 R8 H$ h
        Solving the smallest instance directly (base case).
    7 q1 p- G5 o1 X/ H. j# x( g; G  G7 A8 {
        Combining the results of smaller instances to solve the larger problem.
    ' e4 f1 l1 A" `" d& t+ y
    4 m7 |2 e' j: FComponents of a Recursive Function' \, F$ c- ~6 W; m3 p; G
    & B' k- g3 |! D5 C/ {* V8 h. L
        Base Case:, ~% E3 \5 i4 _- w  u+ B5 g
    3 `# M: G+ Q2 y
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.' ^9 j4 y5 f6 m8 N$ y7 b

    7 D, O2 h- f+ i        It acts as the stopping condition to prevent infinite recursion.
    8 n' J7 ^; k' q" N6 x: i: E* `; Y+ K4 y' }$ y/ `; H0 Y
            Example: In calculating the factorial of a number, the base case is factorial(0) = 1.& y9 t1 e% G0 k( s- j! C

    0 B( ^$ `5 W' O, m# T    Recursive Case:
    $ |& H5 [" R3 l$ v& p- O- O3 v. q/ e" ]& j( j
            This is where the function calls itself with a smaller or simpler version of the problem.
    2 I% n( P5 f9 H1 x5 v% m/ l+ I1 H1 r* W& x0 b
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).+ o  L; Z& |9 c/ x7 V/ p

    ' w5 I4 f4 i, _/ d% h6 L" ]Example: Factorial Calculation
    3 n1 p" F. V  w+ D: E
    ' ?; ~1 U/ G, }3 WThe 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:" S" E- Y$ n, R/ Y

      ]* f8 a5 c8 ^! f    Base case: 0! = 1
    $ h! u/ Y+ s8 H* ]3 _
    , m1 `4 R) c& @4 l' ]    Recursive case: n! = n * (n-1)!4 f3 p+ ^* q8 Z, X

    , i( X. L+ x7 LHere’s how it looks in code (Python):
    - C( Z$ N7 \6 ?python8 P6 F5 h: G/ [. ^8 e- B- I+ z
    & V6 s! F9 @4 a- D" v" T

    ( X3 m, T" h/ K% {7 o/ Udef factorial(n):
    ) g2 X7 _1 \' y  Y" M7 x( Y& L# ]    # Base case% Z- E0 T8 [; Y- f2 c1 y
        if n == 0:8 y4 v$ f! J4 X) Y! Q( q9 z7 ^1 C$ j
            return 1' @* P# e* w/ ^! f; ~# i3 X
        # Recursive case
    ! D6 j- I& b# s    else:
    ) I7 A7 l, o% X' R: a* {4 _+ o        return n * factorial(n - 1)
    # I1 O+ G6 o* H% ^: X
    # Y6 m, B. m( B' Y, ]- b% l# Example usage5 O% N& O, O8 B5 _' d) t; O
    print(factorial(5))  # Output: 1203 n' Z2 R' j: C! ]4 n
    # S, z! c9 d* c$ |) \! G
    How Recursion Works2 |2 z* H1 b: z! _" o

    6 Y: t/ P6 P+ t6 x% M# i$ R: b    The function keeps calling itself with smaller inputs until it reaches the base case.
    9 Y( D( K; \6 s9 H- B9 h) P5 u: o7 ^; ~; z! a$ _
        Once the base case is reached, the function starts returning values back up the call stack.
    + x( ]3 a1 y: }4 w
    1 S1 ^/ `5 S, i3 q' @    These returned values are combined to produce the final result.- w5 V% |; [: z* E4 b/ X
    $ @3 Q6 ~$ e( ~; m4 B: k
    For factorial(5):
    / P" h8 V8 K$ v) L! b0 \0 e
    ! E1 r# ]: t, [* D; C8 W! b8 b4 B' ~, b) J
    factorial(5) = 5 * factorial(4)
    ; [  ^. h9 J& Z9 i  Cfactorial(4) = 4 * factorial(3)5 K7 B% Z; z/ a4 t" U
    factorial(3) = 3 * factorial(2)
    # V( F. c  X) ]( V, O7 `' t) C) i& jfactorial(2) = 2 * factorial(1)
    , ?$ S# K) N' Z- Nfactorial(1) = 1 * factorial(0)
    ' @" }" d: g6 J% t* Z- T2 zfactorial(0) = 1  # Base case* }" r' |5 U% y8 I/ ~4 b
    - e$ v8 n3 P" E! H- l5 z6 Z. j2 {# j+ \! [
    Then, the results are combined:/ i% y& V: |; |. `: u. r' f
    ! ^' l4 I5 k5 w1 \- q) `1 e

    " [+ M. }8 b' D/ h: `factorial(1) = 1 * 1 = 1% ^% D6 p" B7 I5 [
    factorial(2) = 2 * 1 = 2
    + l; y2 q/ b2 k: @factorial(3) = 3 * 2 = 6! l1 {! m* @* D: _
    factorial(4) = 4 * 6 = 24
    $ T; f5 a1 _# r6 y" Wfactorial(5) = 5 * 24 = 1203 H4 H( h7 r- C- a; P9 Y! n

    ; m- [' C' I" L/ R" cAdvantages of Recursion, f: q' ?" M( B2 @5 w( O8 {
    8 I. f( f* ?# `
        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).
    # w; S6 L% j0 K% B" l3 f0 S, B- n- W+ y" O# ]2 x
        Readability: Recursive code can be more readable and concise compared to iterative solutions.
    % k7 O& w$ i5 ?$ x/ e1 B9 y1 K0 E; `0 B7 F3 b" f8 l( q% L  Y
    Disadvantages of Recursion
    # r! e2 r: n; w) D8 k8 F  K7 K
    5 j5 e0 m& [$ k2 e! {( F    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.5 I! B# T1 ?( R! |; R7 K5 i
    % K9 p* C5 c) j2 B# I
        Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).3 Z; V( f: w  _! o3 t! E6 R  b) m
    $ w6 Y9 W+ R# a" f
    When to Use Recursion3 J( t! _9 m  \. w

    6 c# f9 L% E  }/ c. n5 w7 s( m6 F    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).
    : e. j- C: L, m# U% P+ y/ t/ w' f
    8 Z, h7 m: O  z    Problems with a clear base case and recursive case.
    ! @* H& K5 }) _; }: Y1 k& F% G' J: R
    Example: Fibonacci Sequence
    9 g: I2 c* l1 W% k3 a0 G7 k/ n1 C& h2 w) N8 M8 A1 _9 I
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    . v* }( O0 |4 e4 _5 u
    / f# g8 [0 i% i# Y1 Y    Base case: fib(0) = 0, fib(1) = 1
    4 o% W/ `$ L" D1 s/ p2 `
    # H- N5 H: g% \2 C; a    Recursive case: fib(n) = fib(n-1) + fib(n-2); S( w* _6 H: p) p9 q. a

    1 O5 o/ ^9 m3 qpython
    - q3 F7 a1 z: A/ @" u
    9 u0 b. p, Z5 P+ n9 J6 `) |
    3 K+ ]" r) R0 pdef fibonacci(n):! K; _, d8 V, P
        # Base cases
    9 A. O% r  \( i4 Z; X/ ?6 F& D    if n == 0:$ a/ ?; X  t2 F$ P- J
            return 0& z/ ?; i, ~6 i2 N4 l4 x
        elif n == 1:; l/ \5 c4 @2 Q6 g/ @6 z* q/ t
            return 1
    5 B$ r4 C2 s0 k    # Recursive case
    9 L8 e; H1 D: X    else:
    5 {: w0 u$ I# F" {* R3 F        return fibonacci(n - 1) + fibonacci(n - 2)! ?; O: h# O  U) R: @
    # D6 R. P0 `, J* t7 H- E# M: v
    # Example usage0 J2 y  R) P" b
    print(fibonacci(6))  # Output: 8
    $ O' e4 A! I8 k) ^0 {
    & ^0 C6 A0 a. X, m- E4 qTail Recursion
    ; W1 y8 o* {. ?% R+ T
    1 Q8 P+ e7 d  PTail 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).
    1 {% P+ l2 ?+ X2 e$ s% v) g- i
    - \/ L" x. ]* {2 ~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-3-4 11:50 , Processed in 0.057245 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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