April 7, 2019 · 数据结构与算法 本文字数: 1.6k 阅读时长:5 min 全站字数:361.8k

递归与迭代

  1. 迭代
  2. 递归
  3. 总结

递归和迭代可以说是在计算机编程中最终要的两种方法了。现代的编程语言对递归和迭代都有非常好的支持。本文将对递归和迭代的内容进行总结。

迭代

所谓迭代就是,不断用旧的值,通过递推计算出新的值,依次循环往复,直到计算出结果。

迭代很容易使用编程语言中的循环进行实现。由于计算机非常适合进行重复性的计算,可以让计算机重复执行递推的步骤,最后推导出变量的最终值。

在计算机应用中,迭代法常用于解决下面几类问题:

第一个是求数值的精确解或者近似解。如使用二分法或者牛顿迭代法求一个数的根,以及通过无穷次的逼近,求解方程的精确或者近似的根。

第二类是在一定范围内查找目标值,典型的应用就是二分查找。

第三类就是机器学习算法中的各种迭代算法。如k-means clustering,PageRank,gradient descent等。

一般情况下,如果一个问题能够通过不断的更新变量的值或者缩小搜索的区间范围就能得到最终的解,就可以尝试使用迭代法来解决。

使用迭代法的一般步骤:

  1. 确定用于迭代的变量。
  2. 建立迭代变量之间的递推关系。
  3. 控制迭代的过程。

下面就以使用迭代法求正整数n的平方根这个问题来演示如何使用迭代法求解数值的近似解的问题。

如果n是正整数,这个平方根一定小于n本身,并且大于1。问题可以进一步转化为在1到n之间找一个数字等于n的平方根。最常见的就是使用二分查找,每次查找区间内的中间值,检查是否符合标准。如求10的平方根的过程如下:

1-10的中间值是5.5,其平方大于10,所以在1-5.5这个区间查找,其中间值是3.25,3.25平方大于10,继续在1-3.25区间的中间值,即2.125,依次按照这个步骤计算,最终发现某个数的平方正好等于10。

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* 二分法求一个证书的平方根。
*
* @param n 待求平方根的正整数
* @param deltaThreshold 误差的阈值,或精度,近似解即可,否则需要耗费大量的时间和计算资源
* @param maxTry 最大查找次数,防止死循环
* @return 该正整数的平方根
*/
public static double sqrt(int n, double deltaThreshold, int maxTry) {
if (n <= 1) {
throw new IllegalArgumentException("n must greater than 1");
}

if (maxTry <= 0) {
throw new IllegalArgumentException("maxTry must greater than 0");
}

double lo = 1.0, hi = (double) n;
for (int i = 0; i < maxTry; i++) {
double mid = (lo + hi) / 2;
double square = mid * mid;
// (square - n) / n
double delta = Math.abs((square / n) - 1);

if (delta <= deltaThreshold) {
return mid;
} else {
if (square > n) {
hi = mid;
} else {
lo = mid;
}
}
}
return -1.0;
}

上述代码中,迭代的变量值就是mid, 在迭代过程中,我们通过计算(square - n) / n来衡量精度,以及使用maxTry来控制最大循环次数。

递归

假设有这样一个问题:有四种面额的钱币,1元,2元,5元和10元,给定一个总额n,求解可以进行找零的方式。如对于5元,可以直接使用1张5元,也可以使用2张2元1张1元,还可以使用5张1元。

这个问题虽然可以使用迭代法实现,但是需要保存大量的中间状态,如第一次使用了1元,下面就要好几种选择,每种选择都需要记录下来。那有没有更好的解决方法呢?

答案是有的,那就是递归。递归其实也是一种迭代,只不过迭代不是通过普通的循环来实现,而是通过函数调用来实现。函数调用过程会保存函数中的局部变量,正好可以保存上述问题中的中间状态,从而省去了大量中间变量的操作,极大的方便了设计和编程。

递归,从字面意思可以分为“递“和“归”两部分。“递”的过程就是将问题分解为子问题,子问题在问题规模上比原问题要小,但是解决思路却和原问题一模一样。当子问题不断划分,划分到不能再分,并且可以直接求解后,“递”的过程结束,开始进行“归”,合并子问题的结果,最终返回最终的结果。

下面是使用递归的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static long[] REWARDS = {1, 2, 5, 10};

public static void getRewardMethod(long totalReward, ArrayList result) {
if (totalReward == 0) {
// 递归结束,输出结果
System.out.println(result);
return;
}

if (totalReward < 0) {
return;
}

for (int i = 0; i < REWARDS.length; i++) {
ArrayList newResult = (ArrayList)(result.clone());
newResult.add(REWARDS[i]);// 记录当前选择
// 解决子问题
getRewardMethod(totalReward - REWARDS[i], newResult);
}
}

从上面的解法可以总结出递归的代码模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def recursion(level, param1, param2):
# 递归终止条件
if leval > MAX_LEVEL:
print_result
return

// 处理当前层的逻辑
process_data(level, data...)

// 下钻
recursion(level + 1, p1, ...)

// 如果需要恢复当前层的状态
reverse_state(level)

由于递归本身就是基于操作系统中的栈来进行实现,所以,在理论上,如果在递归实现中手动引入栈,手动模拟入栈和出栈过程,这样上述的递归代码也可以改造成为循环实现的方式。可以根据问题的规模和具体的场景来进行选择。

总结

本文介绍了迭代和递归,其实递归也是广义上的迭代,只不过其迭代的方式是通过函数调用来实现,而函数调用本身是通过栈来实现。

迭代和递归最关键的就是要写出递推公式或者递推关系,然后通过循环或者函数调用去实现,从而求得最终的解。