图解是什么意思呀。
这个算法 那么简单没必要搞得那么复杂吧。
an = an-1 + 1;
你明白这个等式的意义吗。
这个等式已经包含了递归算法的全部含义。
an 表示 n个数的和,an-1 表示n-1个数的和 ,an = an-1 + 1;表示n个数的和可以通过n-1个数的和来求的。
上述说明哪些情况可以使用递归呢。
那就是:已知前一个步骤可以求得后一个步骤的结果的情况,并且前一个步骤和后一个步骤是有规律过度的。
比如汉诺塔问题:
移n个盘是已移n-1个盘为条件的,两者的共同点是移盘。所以可以用f(n)表示移n个盘,f(n-1)表示移n-1个盘,那么移n个盘和移n-1个盘有什么关系呢。
这就需要预先分析问题才能得出具体的关系
在这个问题中,把n个盘从a移到c需要三个步骤来完成。
1.n-1个盘从a移到b
2 1个盘从a移到c
3 n-1个盘从b移到c
已知n-1个盘从a移到b是可行的,为什么。
因为移1个盘是可行,那么移2个盘也是可行,移 3个盘是已移2个盘为条件的,所以移3个盘也是可行的,所以移n个 盘是可行的。
所以根据已知条件可以解得:
设f(n, a, b,c) 表示 把n个盘从a移到c 借助b --------------------------这里很关键,这是搞懂递归的关键关键。
那么把n-1个盘从a移到b 借助c 怎样表示呢。
很明显是:f(n-1, a, c,b)
那么把1个盘从a移到c怎样表示呢?
很明显是:f(1, a, b,c)
那么把n-1个盘从b移到c 借助a 怎样表示呢。
很明显是:f(n-1, b, a,c)
所以f(n, a, b,c) = ( f(n-1, a,c,b) , f(1, a, b,c), f(n-1, b,a,c))
这和等差等比数列一个原理。
没有什么 特别的。
记住是问题有这样递推关系才可以使用这种方法。
如果要你计算1+2+8+22 的结果 你就不能使用递归。
因为该问题的后一步骤与前一步骤不具有规律性,所以已知前一个步骤并不能求的后一个步骤的值
1+2+3+4 ...+ 111111111111111111111111111111
这个问题就可以使用递归
原因你懂了吧。
至于爬楼梯问题,无限级分类 问题等一些递归问题,那不过时小菜一碟。
一句话:后一步骤依赖前一步骤并且二者联系具有规律性,运用递归必然成功。
2019-07-17 22:54:56