Question

递归算法的弊端与改进

Answer 1

递归一直给人的感觉是简洁且优雅，但是在面对较大规模的问题时，递归的弊端就渐渐暴露出来了。因为大量栈的使用导致程序运行速度变得很慢，所以递归算法需要改进。

1.尾递归：函数返回之前的最后一个操作若是递归调用，则该函数进行了尾递归。

但是我发现尾递归貌似并没有很显著的作用？？？（值得深究）

2.递归改递推，举例斐波拉切数列

递归算法大于40之后就会变得很慢，甚至算不出来。而递推算法可以算更大的数而且算得更快（ 即使用了long，但是超过50还是会溢出gg ）。

所以面额拼凑问题就需要使用 递推法 ，一个一个算，看似非常傻但是却比递归好用，或许这就是 大智若愚 吧。

比较难理解的可能是 m[j]+=m[j-den[i]];其等价于之前提到的递推式（1020,100）=（1020-100,100）+（1020,50），但是我们发现（1020,50）没了，这是因为之前已经加上去了。

在这个两层循环中，第一层就是以不同的面额做循环，例如（5,5）=（0,5）+（5,1），之所以省略掉了（5,1）是因为在之前就已经将（5,1）加上去了（ m[j]=1 ）,所以可以直接 m[j]+=m[j-den[i]] .当面额为5循环完毕之后，就可以开始面额为10的循环了。（10,10）=（5,10）+（10，1）=（5,5）+（10,1），由于之前（10,1）已经加上去了，所以直接加上（5,5）就可以了。一次类推直到面额100循环完毕，结果就出来了。（感觉没有讲清楚）

碰到的问题：

1.10000的时候出现溢出。原因：之前在intellij（java）中写的时候用long（64位）没问题，但是 C语言（dev c++和VS）long是32位的 ，所以使用long long

2.dev c++使用的是gcc编译器支持 动态数组 ，VS不支持所以一开始报错。改为 long long *m=new long long[money+1];