《Hello算法》开卷有益——迭代和递归算法

aramy

《Hello算法》开卷有益——迭代和递归算法 [复制链接]

 

 
计算机中算法是个奇怪的东西。首先是极其重要，生活中各种问题的解决都需要使用到算法，计算机软件就是一个由算法构成的庞大工程，但另一方面，它又暗暗隐藏，平时能看见的各种软件都已经将算法隐藏在其中了，可以无需了解算法的实现，而且使用各种软件。不了解算法也可以编程，但是想编写出优秀的程序，必须了解算法。

关于迭代和递归，书中给了个例子：给定一个斐波那契数列 0,1,1,2,3,5,8,13,… ，求该数列的第N个数字。

使用递归的例子：对于递归来说，终止条件至关重要，如果没有终止条件，则会陷入“鸡生蛋，蛋生鸡”的无限循环之中……

def fib(n: int) -> int:
    """斐波那契数列：递归"""
    # 终止条件 f(1) = 0, f(2) = 1
    if n == 1 or n == 2:
        return n - 1
    # 递归调用 f(n) = f(n-1) + f(n-2)
    res = fib(n - 1) + fib(n - 2)
    # 返回结果 f(n)
    return res

使用迭代则比较好理解，从初始条件出发，一直计算到满足终止条件即可。日常中解决问题的思路以迭代居多。

---

书中给出了迭代和递归的比较图。

迭代与递归特点对比

	迭代	递归
实现方式	循环结构	函数调用自身
时间效率	效率通常较高，无函数调用开销	每次函数调用都会产生开销
内存使用	通常使用固定大小的内存空间	累积函数调用可能使用大量的栈帧空间
适用问题	适用于简单循环任务，代码直观、可读性好	适用于子问题分解，如树、图、分治、回溯等，代码结构简洁、清晰

通过对比可以看出，递归在时间效率和内存使用是都劣于迭代，但是迭代处理的问题，通常会在处理前对问题有清晰的路径和方法，算法中使用循环去解决问题。而递归则通常对问题只有收敛的条件，具体解决过程负责或冗长，使用递归不停地对函数自身进行调用，直至解决完问题，对于复杂问题有着优势。