「函数」递归与迭代

| 2019-05-17

1. 百度百科解释

递归：

程序调用自身的编程技巧称为递归（ recursion）。递归作为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

迭代：

迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。

重复执行一系列运算步骤，从前面的量依次求出后面的量的过程。此过程的每一次结果，都是由对前一次所得结果施行相同的运算步骤得到的。例如利用迭代法求某一数学问题的解。

对计算机特定程序中需要反复执行的子程序(一组指令)，进行一次重复，即重复执行程序中的循环，直到满足某条件为止，亦称为迭代。

2. 其他解释

递归（recursion）：递归常被用来描述以自相似方法重复事物的过程，在数学和计算机科学中，指的是在函数定义中使用函数自身的方法。（A调用A）

迭代（iteration）：重复反馈过程的活动，每一次迭代的结果会作为下一次迭代的初始值。（A重复调用B）

递归，就是在运行的过程中调用自己。

构成递归需具备的条件：

1.子问题须与原始问题为同样的事，且更为简单；

2.不能无限制地调用本身，须有个出口，化简为非递归状况处理。

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。

3. 两者对比

递归是一个树结构，从字面可以其理解为重复“递推”和“回归”的过程，当“递推”到达底部时就会开始“回归”，其过程相当于树的深度优先遍历。

迭代是一个环结构，从初始状态开始，每次迭代都遍历这个环，并更新状态，多次迭代直到到达结束状态。

理论上递归和迭代时间复杂度方面是一样的，但实际应用中（函数调用和函数调用堆栈的开销）递归比迭代效率要低。

相同点：

递归和迭代都是循环的一种。

不同点：

1、程序结构不同

递归是重复调用函数自身实现循环。

迭代是函数内某段代码实现循环。

其中，迭代与普通循环的区别是：迭代时，循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。

递归与普通循环的区别是：循环是有去无回，而递归则是有去有回(因为存在终止条件)。

2、算法结束方式不同

递归循环中，遇到满足终止条件的情况时逐层返回来结束。

迭代则使用计数器结束循环。

3、效率不同

在循环的次数较大的时候，迭代的效率明显高于递归。

4. 实例

分别用递归和迭代实现斐波那契数列

# -*- coding: utf-8 -*-
# @File : 递归
# @Author : axyzdong
# @Time : 2021/12/22
# @Description :用递归实现斐波那契数列
def recursion_fab(n):
    if n < 1:
        print('输入有误！')
        return -1
    if n == 1 or n == 2:
        return 1
    else:
        return recursion_fab(n - 1) + recursion_fab(n - 2)


recursion_month = int(input('请输入所经过的月数：'))
recursion_num = recursion_fab(recursion_month)
if recursion_num != -1:
    print('递归法：经过%d月后，兔子的总数为：%d' % (recursion_month, recursion_num))

# -*- coding: utf-8 -*-
# @File : 迭代
# @Author : axyzdong
# @Time : 2021/12/22
# @Description :用迭代实现斐波那契数列
def iteration_fab(n):
    n1 = 1
    n2 = 1
    n3 = 2
    if n < 1:
        print('输入有误！')
        return -1
    if n == 1 or n == 2:
        return 1
    while (n - 2) > 0:
        n3 = n1 + n2
        n1 = n2
        n2 = n3
        n = n - 1
    return n3


iteration_month = int(input('请输入所经过的月数：'))
iteration_num = iteration_fab(iteration_month)
if iteration_num != -1:
    print('迭代法：经过%d月后，兔子的总数为：%d' % (iteration_month, iteration_num))

5. 总结

递归与迭代都是函数实现的一种方式，包含了不同的逻辑思想；

递归反复调用自身函数，编程思路比较清晰；

迭代从变量最初的值开始，不断用变量旧值递推出新值

编辑：航网科技来源：腾讯云本文版权归原作者所有转载请注明出处

关注我们

微信扫一扫关注我们