当前位置: 首页>前端>正文

有哪些思路可以构建递归的基例Python python递归程序一定要有基例

示例1:计算阶乘是递归程序设计的一个经典示例

def fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n-1)

print(fact(5))   #res = 120

 

这里,当n == 1 时 非常重要,因为,这个条件是该递归程序的边界,也就是结束往下递归的条件。

可见,只要初始值大于零,这个函数就能够终止。停止的位置称为 基线条件(base case)基线条件是递归程序的 最底层位置,在此位置时没有必要再进行操作,可以直接返回一个结果。所有递归程序都必须至少拥有一个基线条件,而且 必须确保它们最终会达到某个基线条件;否则,程序将永远运行下去,直到程序缺少内存或者栈空间。

递归程序的基本步骤

每一个递归程序都遵循相同的基本步骤:

  1. 初始化算法。递归程序通常需要一个开始时使用的种子值(seed value)。要完成此任务,可以向函数传递参数,或者提供一个入口函数, 这个函数是非递归的,但可以为递归计算设置种子值。
  2. 检查要处理的当前值是否已经与基线条件相匹配。如果匹配,则进行处理并返回值。
  3. 使用更小的或更简单的子问题(或多个子问题)来重新定义答案。
  4. 对子问题运行算法。
  5. 将结果合并入答案的表达式。
  6. 返回结果。

循环和递归函数对比

特性

循环

递归函数

重复

为了获得结果,反复执行同一代码块;以完成代码块或者执行 continue 命令信号而实现重复执行。

为了获得结果,反复执行同一代码块;以反复调用自己为信号而实现重复执行。

终止条件

为了确保能够终止,循环必须要有一个或多个能够使其终止的条件,而且必须保证它能在某种情况下满足这些条件的其中之一。

为了确保能够终止,递归函数需要有一个基线条件,令函数停止递归。

状态

循环进行时更新当前状态。

当前状态作为参数传递。

 

 

 

 

 

 

  

 

可见,递归函数与循环有很多类似之处。实际上,可以认为循环和递归函数是能够相互转换的。 区别在于,使用递归函数极少被迫修改任何一个变量 —— 只需要将新值作为参数传递给下一次函数调用。 这就使得您可以获得避免使用可更新变量的所有益处,同时能够进行重复的、有状态的行为。

 

递归函数

  递归(Recursion),在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。

在使用递归时,需要注意以下几点:

  • 递归就是在过程或函数里调用自身
  • 必须有一个明确的递归结束条件,称为递归出口。

注意: 切勿忘记递归出口,避免函数无限调用。

def fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n-1)

print(fact(5))   #res = 120

 

为了明确递归步骤,对 5! 进行过程分解:

factorial(5)                        # 第 1 次调用使用 5
5 * factorial(4)                    # 第 2 次调用使用 4
5 * (4 * factorial(3))              # 第 3 次调用使用 3
5 * (4 * (3 * factorial(2)))        # 第 4 次调用使用 2
5 * (4 * (3 * (2 * factorial(1))))  # 第 5 次调用使用 1 
5 * (4 * (3 * (2 * 1)))             # 从第 5 次调用返回
5 * (4 * (3 * 2))                   # 从第 4 次调用返回
5 * (4 * 6)                         # 从第 3次调用返回
5 * 24                              # 从第 2 次调用返回
120                                 # 从第 1 次调用返回

当数字减少到 1 时,递归结束。

递归的优缺点

从“编程之美”的角度来看,引用一句伟大的计算机编程名言:

To iterate is human,to recurse divine. 
迭代者为人,递归者为神。 
– L. Peter Deutsch

 

优点:

  • 递归使代码看起来更加整洁、优雅
  • 可以用递归将复杂任务分解成更简单的子问题
  • 使用递归比使用一些嵌套迭代更容易

缺点:

  • 递归的逻辑很难调试、跟进
  • 递归调用的代价高昂(效率低),因为占用了大量的内存和时间。

 




https://www.xamrdz.com/web/2kz1960169.html

相关文章: