设为首页收藏本站

爱吱声

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

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

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

    [LV.2]筑基

    跳转到指定楼层
    楼主
     楼主| 发表于 2025-1-29 14:16:55 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    本帖最后由 密银 于 2025-1-29 14:19 编辑 * h) j! z, g6 Y5 b

    8 I) d4 r# ?2 U, ]/ P解释的不错; h% f& M# h# Q2 Y# Z
      a, v6 F. M6 d$ T! K* r
    递归是一种通过将问题分解为更小的同类子问题来解决问题的方法。它的核心思想是:**函数直接或间接地调用自身**,直到满足终止条件。
    + G- O; U% w4 Z! K
    * D: D* @; y" Y2 X 关键要素
    : f. ]; m$ |# Y1. **基线条件(Base Case)**
    / A! p9 s: M5 o; m8 G   - 递归终止的条件,防止无限循环6 G3 s  K) [2 N
       - 例如:计算阶乘时 n == 0 或 n == 1 时返回 1
    2 x$ ~/ e& ?( w8 b  s8 O! o: H( L
    3 e. Z7 M" Y; Y  s7 q2. **递归条件(Recursive Case)**
    8 n# t& m- D  q( v9 Q   - 将原问题分解为更小的子问题
    9 I# ?. S! @; O   - 例如:n! = n × (n-1)!
    2 e; p, |( G. U7 c$ I) i, R! F' A
      x: j1 q+ J; p5 W, W" L1 a$ t 经典示例:计算阶乘9 r& B% c0 k7 y  z! ?
    python
    & O+ N0 c0 v% s/ S+ c6 Y7 ^def factorial(n):$ n) ]$ f; G- a+ Z. N
        if n == 0:        # 基线条件
    6 D: |" ?* w5 s9 j" h9 \        return 1
    + }1 f7 i* {4 P" {+ G8 r; C    else:             # 递归条件
    4 `! p" I0 B0 ^! q        return n * factorial(n-1)
    ( X! O% b+ x8 Z; b9 k0 ~& p执行过程(以计算 3! 为例):, ?  k6 Z8 M! A2 y% N0 Z
    factorial(3)
    0 A7 I: k4 M" w: }9 S( n5 ~3 * factorial(2). O. N1 z, S; m& B) m
    3 * (2 * factorial(1))3 j3 y# t7 q: c- V
    3 * (2 * (1 * factorial(0)))/ u2 g0 r; P4 w* F( w
    3 * (2 * (1 * 1)) = 6
    . s% s4 b7 m% h" @0 t, {& G9 `# T+ `: v5 j1 h
    递归思维要点' }# z! b0 N, y% g! b, i& }$ ?2 K% y
    1. **信任递归**:假设子问题已经解决,专注当前层逻辑
    9 {2 U* D' S, u7 S/ g3 r2. **栈结构**:每次调用都会创建新的栈帧(内存空间)/ d+ F( Q/ Q- D: @
    3. **递推过程**:不断向下分解问题(递)+ x( o$ y9 q) @
    4. **回溯过程**:组合子问题结果返回(归)4 p) q! ~7 X& r; U0 ]" [8 ?
    # s3 q7 o, x0 a, K* b" V$ q9 a
    注意事项# O) u* j; j: ~
    必须要有终止条件
    ! s& ^5 E% z% a- G& `# c; W递归深度过大可能导致栈溢出(Python默认递归深度约1000层)- U1 Q7 @0 b- W: P) U0 N8 [
    某些问题用递归更直观(如树遍历),但效率可能不如迭代1 V' F9 F. [+ s: N  V; `* r
    尾递归优化可以提升效率(但Python不支持)
    / j$ r0 b$ D4 {0 T8 B7 n+ {9 L: N5 A, z
    递归 vs 迭代7 Z. U5 r9 }% B
    |          | 递归                          | 迭代               |
    7 L6 q  h$ m) j) L8 C|----------|-----------------------------|------------------|
    3 }2 _( L4 g7 ?* _| 实现方式    | 函数自调用                        | 循环结构            |' r5 t: T# s0 {$ ]5 b
    | 内存消耗    | 需要维护调用栈(可能溢出)               | 通常更节省内存         |
    8 i3 N: G! q4 y! t8 c| 代码可读性  | 对符合递归思维的问题更直观                | 线性流程更直接         |
    ( m8 y) g1 x. M" e9 F' I| 适用场景    | 树结构、分治算法、回溯问题等               | 简单重复操作          |+ F3 R/ q# U8 ~# d, H

    8 c% h* c" `  @8 _  n% R 经典递归应用场景
    ( S; S4 N! z0 ^; n# O1. 文件系统遍历(目录树结构)
    4 H2 d% X% y* Z; K( q" S2. 快速排序/归并排序算法  }' b* Q. ?5 U2 J
    3. 汉诺塔问题% _6 I# D* r* L
    4. 二叉树遍历(前序/中序/后序)
    ' J4 W1 n6 L) D; l! \9 J- {5. 生成所有可能的组合(回溯算法)4 `9 t4 d8 a! e1 ]( B1 D/ y

    0 o: B: I" j5 R试着用递归思维想象:你站在一面镜子前,镜子里有无数个逐渐变小的你在照镜子,这就是递归的直观体现。但记住每个"分身"最终都要有结束的时刻,这就是基线条件的重要性。

    评分

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

    查看全部评分

  • TA的每日心情

    17 小时前
  • 签到天数: 3192 天

    [LV.Master]无

    沙发
    发表于 2025-1-30 00:07:50 | 只看该作者
    挺好,递归思维要点与我能够回忆起来我当时写递归程序的思路很一致,,或者被它唤醒,
    - U+ z1 M5 j! o( L8 I. [我推理机的核心算法应该是二叉树遍历的变种。% [) k3 V# ?8 X4 [
    另外知识系统的推理机搜索深度(递归深度)并不长,没有超过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 x; S/ ]4 T7 l/ Y4 a/ X+ a9 DKey Idea of Recursion
    2 Q. K( n8 Q' l1 R: P* E3 W- _9 l, f1 F
    A recursive function solves a problem by:% a* @( Y8 p3 ?# e

    $ h' j1 b2 h4 N, b5 ~! W- i4 v+ {    Breaking the problem into smaller instances of the same problem.* a8 w2 t& w$ r# ?

    * E* G' \- E- G; X  V6 T8 C; ?    Solving the smallest instance directly (base case).
    * l7 k6 {3 j, }' C4 l  n  T) W3 X5 R$ P& S3 c
        Combining the results of smaller instances to solve the larger problem.
    6 P1 I8 T- G) ]; J
    ( F! i6 l3 {9 R/ w- YComponents of a Recursive Function
    9 S1 |% U4 u& |6 V' A, e, a3 O, P+ s, I3 n6 d
        Base Case:
    % Q% _9 Z' w. o. E$ @: ^' P$ O7 B3 o: T! s0 s' Y7 c7 u
            This is the simplest, smallest instance of the problem that can be solved directly without further recursion.
    # [0 N2 R8 T4 Q" X) o$ u4 m% ?" l! o' i: n  n
            It acts as the stopping condition to prevent infinite recursion.
    9 n, Z  `$ s+ l: G' ]
    6 Z! V$ e+ J' n( ?+ z        Example: In calculating the factorial of a number, the base case is factorial(0) = 1.4 h2 q; X7 o9 ?% u' K7 ]

    , g( W% {' p9 K0 t, b    Recursive Case:
    ' K  m; S! X* u  K, f, [. O; h+ I! I4 ^1 |3 S
            This is where the function calls itself with a smaller or simpler version of the problem.
    - K8 N1 I& V0 l2 S# f+ h" c6 L5 y* H' t- B8 z8 _
            Example: For factorial, the recursive case is factorial(n) = n * factorial(n-1).
    2 i- \% D5 P: V- g; j
    9 e! X% ]* H$ T0 _/ p0 V; OExample: Factorial Calculation$ a) T& ]9 v# r! f$ ^5 G* ~

    0 C% d7 T, O/ J. Z0 r4 \+ z$ ZThe 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 h1 C$ A( c$ g6 T5 N- K6 T& G7 \. w  X

    4 T) M/ i% Z- X/ I; O2 u# X    Base case: 0! = 1
    ; J0 f2 F1 Z; @& T
      |& K( o5 a# z3 t* M  {# ]5 u    Recursive case: n! = n * (n-1)!
    3 h! j8 i' _8 o, `/ p% _+ V- p3 }% K2 ~% g4 ~0 ^3 _
    Here’s how it looks in code (Python):
    $ x1 R8 z8 s; z( }+ g" H' ?5 @5 jpython
      F7 [& a" a$ p- w) D8 P
    , `8 g5 F: c/ [/ E
    $ z$ R! l& a- ?& }$ G5 Z* ndef factorial(n):! H6 L& W; e! T8 m5 `8 w* H
        # Base case
    ) }) j& d8 v$ C9 q, E- G) \    if n == 0:$ E+ U/ g% a7 E, c7 u' r
            return 1
    / v3 t4 `/ _, N; M% v    # Recursive case" M3 P+ ~% {9 m& \6 r, U7 u% j, J
        else:
    ( s1 J7 \! ]9 C% T5 o* M$ N        return n * factorial(n - 1)3 v- t, y$ W! l9 v

    * p2 t+ `5 c1 V1 O; K  |# Example usage) l1 X/ W( Z: u' Y) N
    print(factorial(5))  # Output: 120# ?  C/ e' |. W% V3 n
    8 ?: j9 @! Q: u. w
    How Recursion Works
      m, i* o' g; f5 y! N, A  O$ p* E; z9 d6 T) p0 h# q( ]! X
        The function keeps calling itself with smaller inputs until it reaches the base case.' r+ r  w6 d! x# i7 F& O5 t  q+ V

    * X% [  ]! m; Y4 Q# k$ ]+ t; d8 c    Once the base case is reached, the function starts returning values back up the call stack.+ O) T9 O% h% z

    ! `5 e4 G8 p5 W, G/ W1 H4 I; N: ^    These returned values are combined to produce the final result.  G1 H2 o' g, S- C2 N) J
    / _+ W, n  N  N9 T0 l  E' N
    For factorial(5):
    & G. e5 A- A! t; A2 o, h6 p6 N# h/ m7 n

    4 E& H! I' y3 F# \( b+ e0 Afactorial(5) = 5 * factorial(4)+ h9 I2 e( e5 ^$ R7 K
    factorial(4) = 4 * factorial(3)- Y$ {# K: X/ x* j
    factorial(3) = 3 * factorial(2)
    & r* N4 j1 x( g2 C  }9 U( ?: ifactorial(2) = 2 * factorial(1)' j0 B, D/ k: E% z: v  i
    factorial(1) = 1 * factorial(0)
    ( M% F3 h/ j2 v. P- {8 m2 f# e2 tfactorial(0) = 1  # Base case
    / R/ U# _$ @! M2 S' ^) F' O1 a
    ; `+ p: ?& `; Y6 BThen, the results are combined:& K7 v. z) n  d& f5 u  k' P+ \: [

    ( W$ Q6 x3 H5 \8 E
    4 s9 R+ i3 P" J2 {/ o5 p# Z# Zfactorial(1) = 1 * 1 = 1, _0 H& y; v7 H* p, N$ _6 a( X* M
    factorial(2) = 2 * 1 = 2( B0 G2 {5 ^  n5 V
    factorial(3) = 3 * 2 = 6
    8 K, |9 R& r% B5 \8 m4 j3 ]factorial(4) = 4 * 6 = 24
    6 l5 n- c! x& z1 T! e  n9 Lfactorial(5) = 5 * 24 = 120
    / x' N9 D/ p2 f! f1 _5 k$ J# B4 Q7 K# r. D0 E
    Advantages of Recursion
    4 G2 H: O! x+ J/ J& J& e1 I2 y' o4 w9 U' H: Z" @
        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).
    ; Q5 \1 ?& z% Z* d" C$ \; m5 P$ o+ [! ]2 Q: a  V% F
        Readability: Recursive code can be more readable and concise compared to iterative solutions.7 d0 H. Y. X0 B" I+ F8 a1 x

    % I' N7 s# h' kDisadvantages of Recursion: X! |4 c2 E7 O. l5 c
    8 Z( F1 q) P5 q: L2 V1 p8 j8 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.8 E! M3 ~9 L- ?6 {; T

    9 ^6 E0 l& {+ n7 r8 m: k5 Z% M" u6 f    Inefficiency: Some problems can be solved more efficiently using iteration (e.g., Fibonacci sequence without memoization).) q' a6 o) i* I4 \5 h3 ]

    0 }  T7 S& a" X, N/ k4 fWhen to Use Recursion. t3 p* _- Z1 h, O: Z! G) }. ]

    , l/ W+ U" I" x. w    Problems that can be broken down into smaller, similar subproblems (e.g., tree traversals, sorting algorithms like quicksort and mergesort).; _9 ?: C& R2 @3 N
    1 ^; Y5 a6 ^+ |( W3 z2 O$ K
        Problems with a clear base case and recursive case.# E% @; V+ t6 Z) }: F
    4 ~; t$ n% G/ `9 V' \/ M
    Example: Fibonacci Sequence) D7 U# f$ X; v  }! x- T  ^# N% T. W
    & B1 y/ d7 j8 a, k6 a. F9 u
    The Fibonacci sequence is another classic example of recursion. Each number is the sum of the two preceding ones:
    : h/ `. @- D6 |6 s1 O
    / @/ x  I/ N+ J. n3 V3 y    Base case: fib(0) = 0, fib(1) = 1
    + [) n! }) ]- p( l, ]) D8 p. H, f! l# Y1 i7 `: U  c& K- ]
        Recursive case: fib(n) = fib(n-1) + fib(n-2)
    & \* Y" V& f1 V3 c/ }' Y, T
    ) E( j  u# [% v* q- L8 o% Mpython
    + c# r1 ?( f& n5 y+ Z. U- @; |- W9 X) r6 d$ V
    # G6 \) m* q" E; K8 D: e# P
    def fibonacci(n):
    # W& o1 t$ F3 L" I$ y    # Base cases
    ) g3 t* Y5 R  }$ y    if n == 0:- x& i9 X( N, Y6 K* f  u$ U) v+ G
            return 08 f5 `) e4 G- h' f/ ]
        elif n == 1:" x% a2 c  \' S( s& x
            return 19 B! Q/ I/ `  E& k8 W9 J
        # Recursive case) e7 `9 Z5 p8 S  k) i
        else:9 {1 _2 `. t9 r$ A1 e" y9 t
            return fibonacci(n - 1) + fibonacci(n - 2)
    , ^* X: w- j) x
    5 F' o# |! R* v$ T: F# Example usage- H8 @& \0 r( b1 S# Z( y
    print(fibonacci(6))  # Output: 8
    , I+ J3 j* M: l, T) u, C: t2 [9 U7 ]; v9 x
    Tail Recursion
    4 s/ ~2 b* t! L1 M) M+ v- k
    4 @/ R( D  i0 D% q1 G! _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).
    / O- a" D% F2 q6 N  E3 s
    $ f" W  u" l  g1 G) eIn 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-5 17:45 , Processed in 0.084809 second(s), 18 queries , Gzip On.

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

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