python递归函数：求解斐波那契数列问题
编程学习经验的人对于递归函数一定不陌生，我们经常使用递归的方式来解决一系列复杂的问题，递归算法对于大多数问题都是很有效的，而且它也可以优化我们的代码，我们在使用递归的时候有几点需要注意：
1) 递归是在函数本身调用函数本身。
2) 递归的效率比较低，如果有时间限制不建议使用。
3) 递归过程中需要有一个明确的结束条件，即递归出口。
下面我们就来详细的讲解一下递归函数。
1. 递归函数
我们先通过例子来看一下递归的简单使用：
|
1
2
3
4
5
6
7
8
|
m = int(input('输入一个数字：'))def test(x): x += 2 if x <100: test(x) else: print('最后的x为：',x)test(m) |
输出结果为：
|
1
2
|
输入一个数字：20最后的x为： 100 |
我们来分析一下这个例子，首先第一行代码我们输入了一个整数，最后一行把m作为实际参数传递到test()方法，在test()方法中，会先把x进行加2处理，然后进行一个判断，如果x的值小于100，那么就再次调用这个函数，调用的时候当前x的值作为实际参数参加调用，直到满足x>=100的时候结束递归。
看下面示意图：
即如果不满足条件就回到了最外层来调用了这个函数。
2. 斐波那契数列
谈起递归算法中经典的问题，总是离不开斐波那契数列和汉诺塔，我们在这里来讲解一下如果使用递归去求解斐波那契数列。
首先我们要知道斐波那契数列的递推公式为F(n)=F(n-1)+F(n-2)，F(1)、和F(2)为1，我们可以通过递归来求解斐波那契数列中的某一项的值为多少。
求解斐波那契数列问题的时候我们可以采用多种方式。
首先我们使用常用的递归方式来解决这个问题：
|
1
2
3
4
5
6
7
|
N = int(input("输入需要得到的项数："))def fibonacci(n): if n <= 2:#如果小于等于2就把n置1 return 1 else: return fibonacci(n-1) + fibonacci(n-2)print('对应值为',fibonacci(n)) |
输出结果为：
|
1
2
|
输入需要得到的项数：4对应值为 3 |
对于这种递归的调用方式，当我们输入的值4的时候，会在递归中执行下面的操作：
|
1
|
fibonacci(3)+fibonacci(2)=fibonacci(2)+fibonacci(1)+fibonacci(2) |
然后我们可以看出第四项的值为1+1+1=3。
其实这种方式的求解是比较浪费时间的，因为需要进行迭代的次数太多，我们还可以采用空间替代时间的方式来求解这个问题。
代码如下：
|
1
2
3
4
5
|
n = int(input("输入需要得到的项数："))fibonacci = [1,1]for i in range(2,n): fibonacci.append(fibonacci[i-1] + fibonacci[i-2])print('对应值为',fibonacci[n-1]) |
输出结果为：
|
1
2
|
输入需要得到的项数：4对应值为 3 |
这种方式我们首先给列表规定了前2项的值，然后对于我们要求解的项数n，我们直接通过公式把这个斐波那契数列的列表填充到我们需要的那一项，最后根据索引值直接找到对应项输出结果。
3. 总结
关于递归函数就讲到这里，上面所讲到需要注意的几点大家要尤为重要递归出口和时间限制，出口是递归结束的关键，在很多时候，我们使用递归的方法会导致程序超出规定的时间，这时候我们就需要更换思路来求解问题，上面讲的第二种方式可以帮助大家解决问题。
