什么是递归算法
移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
这个问题就可以使用递归
原因你懂了吧。
至于爬楼梯问题,无限级分类 问题等一些递归问题,那不过时小菜一碟。
一句话:后一步骤依赖前一步骤并且二者联系具有规律性,运用递归必然成功。
赞0
踩0