设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑
    & _' m; X+ }3 K" M8 u: b5 j% k6 n& d: p; s+ ~# f
    解释的不错
    ' }* Q" _& p. I. ?
    $ z4 n4 ~2 e1 W& K" z递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。, z$ @6 M' I1 V& j# R3 T' J& i

    2 i7 J8 Z& T0 E, \: u2 Z1 C 关键要素
    & l+ {- n3 @! |; @, l9 S1. **基线条件(Base Case)**+ p; P) I4 B2 M8 [) d( ~. `
       - 递归终止的条件,防止无限循环
    / h! a( U5 Y0 u. o   - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    # H# ~/ E9 u4 _) u& E, s, c! \3 I, i% M# ~3 d/ R% C' ?5 u
    2. **递归条件(Recursive Case)**
    0 d6 ^9 n# G0 P, F) i   - 将原问题分解为更小的子问题( Q, x. i2 y& I3 E8 x3 B( F
       - 例如:n! = n × (n-1)!
    9 u* Y( B7 y) u- v
    6 T/ G! L0 v6 y9 ^6 [' c! X 经典示例:计算阶乘
    % k$ G1 i+ v& D# A. rpython5 K" _. ?+ ?6 R8 }: L4 C& G4 r
    def factorial(n):
    ) o, [, M/ Z3 o    if n == 0:        # 基线条件( S8 L' p( r% c' e
            return 1
    2 e& P9 |4 O$ G: V- L    else:             # 递归条件: V. @7 t, x) w5 r5 }. O* F/ v$ h
            return n * factorial(n-1)
    1 T/ V3 `$ ^1 v* p+ K, U7 @% M执行过程(以计算 3! 为例):
    5 _: F  y. v6 ~factorial(3)& N' W- B1 t1 I5 g
    3 * factorial(2)9 |4 n4 k, R' |: b9 w6 b) j
    3 * (2 * factorial(1))
    7 b" o2 f( Z- P  ^' Y5 ~6 d3 * (2 * (1 * factorial(0)))1 N! W4 m+ ?' [( D7 E/ z+ t0 M- l
    3 * (2 * (1 * 1)) = 6
    5 H& l% `: Y) d3 H; q: c; ^& ]: a  {& r9 S, c* c( U; |3 l
    递归思维要点1 u6 m$ {6 }! t% }2 f, U3 M
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    . {( A- D5 \, z1 C9 ^& O2. **栈结构**:每次调用都会创建新的栈帧(内存空间)
    / m4 L' q; t; E' Q3. **递推过程**:不断向下分解问题(递)+ c; b3 |# {+ a
    4. **回溯过程**:组合子问题结果返回(归)
    7 Q+ u" `% H  f7 B8 i' b0 i( ^& ]$ t$ p! Q/ n( o; f0 c3 ?! u% C4 Y
    注意事项$ \( N# G+ _5 E- U# N- t9 R
    必须要有终止条件$ X: [; X) X0 \$ j) L! l9 }
    递归深度过大可能导致栈溢出(Python默认递归深度约1000层)
    : V( i; @. L4 w某些问题用递归更直观(如树遍历),但效率可能不如迭代) g; |+ z+ X# G+ |4 l
    尾递归优化可以提升效率(但Python不支持); I/ {, z8 t) M/ t
    8 H9 F. q% T8 |7 t& x  T" A2 }$ X* ~
    递归 vs 迭代0 a4 m: L2 g1 u
    |          | 递归                          | 迭代               |" S2 E5 J' O4 S0 K% L$ r
    |----------|-----------------------------|------------------|
    3 k5 _  J9 P. c" O| 实现方式    | 函数自调用                        | 循环结构            |
    % _# E% s4 f/ V, V| 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    # P2 ~- j# n0 I; k0 ~7 a/ v) b  \| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |+ E. q' I8 G, i& u; N: ?
    | 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |
    / M: s/ o& y7 ?  i5 J) F/ D4 M. J, ~* K6 J9 K9 V# H" P0 v
    经典递归应用场景
    7 z; @& I/ C1 y9 {4 m1. 文件系统遍历(目录树结构)
    . L9 i7 R6 k6 n( `) Z) I2. 快速排序/归并排序算法
    9 R+ N9 {  D# F+ N4 T3. 汉诺塔问题
    + Q4 i7 a8 e6 K$ t) o4. 二叉树遍历(前序/中序/后序)6 k7 X5 b/ d; V9 J! d
    5. 生成所有可能的组合(回溯算法)% D- f6 F5 z9 B  \
      L) q# u8 U( t) J2 ^1 P. z) F9 U
    试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情
    擦汗
    昨天 06:27
  • 签到天数: 3147 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,, G/ ]# v" l1 b: h6 f: I
    我推理机的核心算法应该是二叉树遍历的变种。# @; Q$ J" s; _, `- W
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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:
    8 ^  b% ^4 Q- P6 v9 pKey Idea of Recursion& R" H) u" I- e0 P
    . R9 x4 w9 W6 X8 S" p
    A recursive function solves a problem by:8 j; L8 j' K' f+ v0 b

    ; O( ]1 A& G4 m4 y) r! Y    Breaking the problem into smaller instances of the same problem.
    4 n; D) B2 x% K
    7 d& ]/ Y  Y4 G8 |7 f# c$ Z    Solving the smallest instance directly (base case).8 L% e1 L( o$ B5 `7 X0 I: X) a9 D  H

    6 M) d+ O- {1 S0 t3 r. g8 o    Combining the results of smaller instances to solve the larger problem.
    1 x5 g2 U. d, X* {7 _3 N( {/ e5 e. Z) S9 K$ p% E6 b) P
    Components of a Recursive Function
    ' D0 B1 ?! V# r, }* q9 z1 W# d5 ^* V- w5 q- h( y/ m! ^, l4 F
        Base Case:
    3 C$ \1 \+ I- C  e' t4 M7 c$ x4 G5 M
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.$ {' N. Y+ y" l& Z+ i% z, E. z/ F

    6 [' \' L( l; k6 x  Z        It acts as the stopping condition to prevent infinite recursion.& k) Q0 o$ ]# `: \, x' m

    9 {' [6 B5 f( L0 I+ Z# b1 a        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.
    ! Y2 ?4 N* d  k9 E; h' b# B% D1 a) F* k4 |2 w; H0 p
        Recursive Case:2 ]% T2 W" Y" f/ M
    , R+ P8 ^! u! M3 r7 ~
            This is where the function calls itself with a smaller or simpler version of the problem.
    / d3 }7 Q7 E% C/ V0 v' L
    + R2 M9 U; M  [! |8 U        Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).. Y( K1 k$ H# W; M3 F3 K% P1 w+ l
    + V5 P0 l0 _. C, b2 N3 A8 I
    Example: Factorial Calculation
    * ~, t( }* A5 n  `* P  A& z$ L/ P3 [6 s
    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:2 |9 [' _! y+ q( R0 s

    7 }9 ^. K, f* Z  K7 O0 E: Q% Q1 j    Base case: 0! = 1* f, H. W$ p. g% U
    * x5 h# I+ `, i
        Recursive case: n! = n * (n-1)!
    ( k/ W% ?: y8 b+ j5 z1 [  P3 ^% Q1 A$ a
    Here’s how it looks in code (Python):
    : W( a% x* z, \% w6 t" `python
    4 ?/ B' ?/ `% A' Z! l# k
    7 y! k7 j1 U: F5 t8 p% o* q3 ^/ v4 ]! K8 _, q9 W# G
    def factorial(n):6 r% B  L$ G" O: V, W- @
        # Base case
    3 T$ I0 W3 k1 I  Y" J- B    if n == 0:8 y; q7 ?4 g/ P7 M2 D
            return 18 p" h& b+ g% M. l' Q* {* z3 n! R
        # Recursive case; o! |0 ~  @) D* g# g  _. c6 m- a( i) Q
        else:$ X; {  [! Y' K! w8 u
            return n * factorial(n - 1); I) u* a( {' x. m

    % W& j* z* U0 N7 _) S# Example usage8 u4 Q$ E" e8 g& U
    print(factorial(5))  # Output: 120
    + T. U9 Z' j" X! F; H* P
    # d# {) e$ N7 @How Recursion Works6 x8 {! ?9 @& J, Y: [

    # z6 ]" Q# _- \  ~0 ~    The function keeps calling itself with smaller inputs until it reaches the base case.
    ! D; d( h2 e) X+ O
    8 F) b! e# @4 i" a4 ]+ s    Once the base case is reached, the function starts returning values back up the call stack.
    3 p7 }0 g9 |' B6 }% c# |' r' u* v+ Y/ U# w
        These returned values are combined to produce the final result.6 J7 f  o+ F- j9 {7 B5 ]

    9 A0 D: _' [. w5 V! e6 zFor factorial(5):2 B) z/ M- ^$ X' a+ B
    # e0 C( v8 |( T* J: h) t! s4 h1 S7 i
    ' _$ e, Y; X: w* i1 ]
    factorial(5) = 5 * factorial(4)1 n) r/ @: r3 s5 }6 D- K; F$ O4 o4 K
    factorial(4) = 4 * factorial(3)
    9 C' r2 S9 a. g# o  q) ifactorial(3) = 3 * factorial(2)
    3 V7 N3 r; w$ I% K+ _factorial(2) = 2 * factorial(1)/ q- R, \1 M1 U
    factorial(1) = 1 * factorial(0)0 O; m; H0 a+ J% x$ q% I2 |
    factorial(0) = 1  # Base case: b4 ~8 W  Q) V
    9 ?8 [; e2 k( }2 Y$ y
    Then, the results are combined:
    - I; w5 M$ e/ u# ~1 t) R: |# d1 o
    ) c0 |) p+ T: ]
    " a1 U# h( l0 u; g# Xfactorial(1) = 1 * 1 = 1
    ! |, C5 h8 ^6 |factorial(2) = 2 * 1 = 2
    4 y. p0 u& O1 u3 p" r, f" @- e7 |factorial(3) = 3 * 2 = 6* G( L' ~2 i; \6 ~$ K) P. m' c
    factorial(4) = 4 * 6 = 245 r) r+ Y: Y- J: s. E1 c
    factorial(5) = 5 * 24 = 120& B6 \) Z- X3 Z

    9 V/ c  v) l% F, x5 w7 rAdvantages of Recursion  P+ k, ~3 H, F) F, I% \2 c

    9 I6 r" S& S! R* x9 d$ M: \    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).
    % R. X0 {( e: K
    2 {' s# i5 b& l* N3 i( W    Readability: Recursive code can be more readable and concise compared to iterative solutions.6 \; U' |' |2 ]0 M; B5 J  f

    % }, @4 A2 ^1 bDisadvantages of Recursion
    ! Q- p7 U5 p! k% |& y
    & O/ b% l  |% N. N' J& l    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.
    , Y4 p: i8 ]# ^* T
    $ u0 p' t2 E; V7 j; K/ i5 N    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).
    9 _& Y- R# ]& f% a, M
    - x3 n0 P( w" N5 J" M) XWhen to Use Recursion9 R9 t. R) \# s% A+ F

    0 b/ g5 {# \+ ^) H4 O+ ^    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).6 l2 P. o: P* w4 Y0 V9 @

    / _: K8 \$ Y. _, m; D% E    Problems with a clear base case and recursive case.
    - }9 z% ~' r: U2 D! E* D# S+ l* ~1 M
    9 G+ G7 N& Q: ^5 i$ U: g+ WExample: Fibonacci Sequence2 ~7 a/ O- C- r1 q

    . a6 n  I4 G4 P  B6 D5 XThe Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:5 g' o, t( g/ Z2 U
    9 _3 e& q) E* ?( O
        Base case: fib(0) = 0, fib(1) = 1- M7 ~- v, A$ t: Z& u

    ! j+ y( a9 M3 C( D! Z% t    Recursive case: fib(n) = fib(n-1) + fib(n-2)
    ! X3 T' u8 [" t- j5 n$ S5 W
    % @3 K) Q! x4 F2 S$ Gpython$ A4 R1 ^- H, K6 G% u
    - L" g/ h, g8 {- f* Z" A; I+ `% u
    ; K6 F/ {+ F2 }. |" }
    def fibonacci(n):' H: C5 \/ E* K; W. F/ I
        # Base cases  w8 F  I- J/ f6 A+ j9 ]
        if n == 0:9 s) I# `7 F) `
            return 0; P3 s" G- p, F0 i. F% r& W
        elif n == 1:
    , R5 c+ Q5 l7 O' z/ n        return 1
    3 V, _; P2 P" p' \  {    # Recursive case
    . g! q( _" P  U; J    else:
    ! L3 E& h0 H1 \3 {' X$ L        return fibonacci(n - 1) + fibonacci(n - 2)$ ~: {7 [/ t! i8 Y  C! L
    ( h. K, @% @" G
    # Example usage
    8 A0 e5 C, ^6 v3 R) w& a8 g& eprint(fibonacci(6))  # Output: 86 W3 \. h" a* ^( x0 j

    3 I$ k& {$ X2 H7 z+ oTail Recursion. N; }1 l3 j+ U) @
    * [: @3 {& q- E# ^5 V. z; e$ E
    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).
    7 |0 F2 c8 @5 q' l) }4 Q1 Y
    - a$ Q$ B1 W0 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-18 06:38 , Processed in 0.030743 second(s), 19 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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