问题描述
上一篇通过递归算法实现整数n从100逐渐递减到1,然后将每一个递减的整数累加到变量sum中,这是一种单向的递减操作,如图:
单向的递减最主要的问题在于下降速度过慢,是否有更快的遍历速度呢?相信聪明的您可能已经发现,那就是使用双向的速度来遍历。
思路已经有了,那接下来如何利用代码编程实现呢?需要注意的地方有哪些呢?
解决方案
单向递减我们的做法是:
void foo(int n){
if( n==0) return ;
foo(n-1);
}
为描述方便,其余部分略过。要想实现双向,就必须得有两个控制变量。
void foo(int i, int j){
foo(i+1, j-1);
}
让变量i实现自增,变量j实现自减,但是什么时候递归结束呢?答案就是i超过j的时候,得出代码为:
void foo(int i, int j){
if( i > j) return ;
foo(i+1, j-1);
}
注:在使用递归函数的时候,切记不要忘记递归结束的条件。
学会了变量i和变量j的双向控制,最后将每一次递减后的变量i和变量j累加到sum即可。
结语
本文为大家介绍了一种新的思维方式来实现递归,可能大家在阅读本文的时候觉得很简单,但是这种思维却是今后解决复杂递归问题的基础,如果缺乏这种思维方式,复杂的问题一定难以解决。这也是本系列文章要为大家传达的核心理念:透过简单的问题来学习复杂的算法思维,帮助大家更好的理解复杂问题。