Python 递归

1. 斐波那契数列的传统方法：

>>> def fib(n):
...     if n < 1:
...         return False       
...     if n == 1 or n == 2:   
...         return 1
...     else:
...         start, nextn = 1, 1
...         while n > 2:       
...             start, nextn = nextn, start + nextn
...             n -= 1
...         return nextn
... 
>>> fib(3)
2   
>>> fib(17)
1597
>>> fib(-1)
False
>>>

递归的方法一：

>>> def fib(n):
...     if n < 1:
...         return False
...     elif n == 1 or n == 2:
...         return 1
...     else:
...         return fib(n - 1) + fib(n - 2)
... 
>>> fib(1)
1
>>> fib(2)
1
>>> fib(17)
1597
>>>

这个方法的缺点是计算的速度很慢，因为返回调用了两次递归，当递归的数字较大的时候，这时候的递归函数将是指数倍增加。

递归的方法二：

>>> def fib(n, ret = [0]):
...     ret[0] += 1
...     if n == 1 or n == 2:
...         ret[0] -= 1
...         return 1, 1
...     else:
...         a, b = fib(n - 1)
...         ret[0] -= 1
...         if ret[0] == 0:
...             return a + b
...         return b, a + b
... 
>>> fib(1)
(1, 1)
>>> fib(2)
(1, 1)
>>> fib(3)
2
>>> fib(4)
3
>>> fib(17)
1597

2. 二分法查找

方法一，不返回索引，只返回存在与否：

>>> def findData(mylist, num):      
...     length = len(mylist)
...     if length < 1:
...         return False
...     if mylist[length // 2] == num:
...         return True
...     elif mylist[length // 2] > num:
...         return findData(mylist[0:length // 2], num)
...     else:
...         return findData(mylist[length // 2 + 1:], num)
... 
>>> findData(aa, 10)
False
>>> findData(aa, 9)
True
>>> findData(aa, -1)
False
>>> findData(aa, -9)
False
>>>

Python 基础教程的算法：

def search(sequence, number, start = 0, end = None):
    if end == None: end = len(sequence) - 1
    if start == end:
        assert number == sequence[end]
        return end
    else:
        middle = (start + end) // 2
        if number > sequence[middle]:
            return search(sequence, number, middle + 1, end)
        else:
            return search(sequence, number, start, middle)