迭代法
迭代法的基本思想是基于当前的值来推导新的值
迭代法的应用,举例:
1、求数值的精确解或者近似解,如二分法
2、在一定范围内查找目标值,如二分搜索
数学归纳法
一般步骤:
1、证明基本情况(通常是n=1的时候)是否成立
2、假设n=k-1时成立,再证明n=k时也是成立的(k为任意大于1的自然数)
和使用迭代法的计算相比,数学归纳法最大的特点,就在于“归纳”二字。它已经总结出了规律。只要我们能够证明这个规律是正确的,就没有必要进行逐步的推算,可以节省很多时间和资源。
递归调用的代码和数学归纳法的逻辑是一致的。
从n, n-1, …, 2, 1的嵌套调用过程,体现了数学归纳法的核心思想,我们将其成为逆向递推。
从1, 2, …, n-1, n的返回过程,和之前的基于循环的迭代是一致的,我们将其成为正向递推。
递归
在递归中,每次嵌套调用都会让函数体生成自己的局部变量,正好可以用来保存不同状态下的数值,为我们省去了大量的中间变量的操作,极大地方便了设计和编程。
总结
递归和循环其实都是迭代法的实现
在编程中,我们所提到的迭代是一种具体的编程实现,是指使用循环来实现的正向递推,而递归是指使用函数的嵌套调用来实现的逆向递推。