Python递归函数与斐波那契数列

在定义一个函数时候,只需知道其终止的条件,无需知道其执行方法,仅需在函数中调用函数本身即可,这种魔性的写法就叫做递归函数,江湖上有一句:人能理解循环,神能理解递归。python

0x00 递归函数与斐波那契数列

递归函数有时候可以将复杂的问题,变的比较简单,复杂的过程交给计算机去完成。最完美的例子就是斐波那契数列。

#斐波那契
#0, 1, 1, 2, 3, 5, 8, 13,

def fibonacci(n):
    if n <=1:
        return n
    else:
        ret = fibonacci(n-1)+fibonacci(n-2)
        return ret

ret = fibonacci(30)
print(ret)

通过在我们定义的函数中调用函数本身从而来算出过最后我们需要的结果。不过当我们输入一个数字较大的结果时候,发现控制台并不能输出结果。这是因为调用的次数实在是太大了。所以递归次数过多的函数,可能就不太适合用递归来解决了。其主要的缺点就是太过于占用内存,当然不可否他的有点,让我们的代码变的很简单。

0x01 更完美的斐波那契数列

虽然用斐波那契数列可以较为容易的理解了递归函数的使用。之前也说,当需要知道特别靠后的数值的时候,那么递归次数很变的很多,因而不太适合用递归函数来解决,所以可以考虑使用别的方法来完成代码。

def fibonacci(n):
    x,y = 0,1
    count = 0
    while count<n:
        x,y = y,x+y
        count += 1
    return x

ret =fibonacci(70)
print(ret)

使用这个方法来完成斐波那契数列的计算,那么比递归不仅更坚定,而且占用内存较少,即使你的n是一个较大的数值,它也可以很快的帮你算出结果。

当然如果非要用递归函数实现的话,可以从执行效率上来考虑。之前的递归方法来看最后需要条用2次递归方法,因而产生的运算量十分巨大,哪怕fibonacci(40)都无法执行,从而考虑是否可以从单递归的方法来实现。

def fib(n,l = [0]):
    l[0] +=1
    if n ==1 or n == 2:
        l[0] -= 1
        return 1,1
    else:
        a,b = fib(n-1)
        l[0] -= 1
        if l[0] == 0:
            return a+b
        return b,a+b

print(fib(50))  #12586269025

代码很经典,不过略微复杂,在没有关键字传参(l = [0])的情况下,那么返回值为一个(b,b+a)的tuple类型,当然我们只需要我们的结果b+a,因而加入了一个关键字传参,利用关键字传参的“陷阱”来实现最后一次函数的执行只返回我们需要的结果。

0x02 递归最大深度

递归深度过深的情况下,不仅非常的占用计算机资源,而且还会报错(RecursionError: maximum recursion depth exceeded while calling a Python object),错误的原因就是超过了Python内置的递归字数了。

那么来挖掘一下,Python最大的递归次数是多少吧!

n = 0

def recur():
    global n
    print(n)
    n += 1
    recur()

recur()

可以发现在报错之前,打印的最大数字为997,那么因此可以看书997次是Python默认的最大递归次数(第一次不算哈!!不然的话算998吧!不要在意细节)。

设置最大递归次数。可以通过sys模块来完成,但是非常的不推荐你这么做。

import sys
sys.setrecursionlimit(100000)

0x03 二分查找算法

如一个有序列表l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88],为了迅速找到想要值的索引时候,虽然我们可以通过for循环后来比较完成,当需要查找的数字万一在列表的最后,那么就做了很多的无用功,因而,可以通过二分法来完成快速查找。

首先不要忘记二分法的适用为一个有序的对象。

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

def binary_search(lst,aim,start = 0,end = None):
    end = len(lst) if end is None else end
    mid_index = (start + end)//2
    if end >= start:
        if lst[mid_index] < aim: return binary_search(lst,aim,start = mid_index + 1,end = end) elif lst[mid_index] > aim:
            return binary_search(lst,aim,start = start,end = mid_index - 1)
        else:
            return mid_index
    else:
        return 'wrong_number'

print(l.index(22),binary_search(l,22))  #7 7

上面的例子就是通过二分查找法找到的最终结果的索引。

最初的版本,因为需要一个列表的长度(end)来计算,当end写入函数内部时候,怎么都无法定义一个初始变量,所以考虑用关键字传参,虽然不清楚列表的长度,不过可以先默认为None,之后在通过三元运算就可以完成对end的复制,并且函数调用过程中,end的值也是一直动态的变化的。

关于返回值的问题

最初写的样子为只有一个return。

#二分查找法
l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]


def binary_search(lst,aim,start = 0,end = None):
    end = len(lst) if end is None else end
    mid_index = (start + end)//2
    if end >= start:
        if lst[mid_index] < aim: binary_search(lst,aim,start = mid_index + 1,end = end) elif lst[mid_index] > aim:
            binary_search(lst,aim,start = start,end = mid_index - 1)
        else:
            return mid_index
    else:
        return 'wrong_number'

print(l.index(22),binary_search(l,22))  #无结果输出

这样的代码运行后没有结果输出。是为什么呢?因为递归函数,是从最后一次函数,倒着向前运行的,当找到索引后,将mid_index返回给了上一次调用,而在if或者elif中都没有参数去接收,所以返回值就被淹没在了递归的过程中,只有都加上return的时候这样才有返回值。

  • 看返回值的时候,不要只看return就觉得已经返回了,要看返回操作是在递归函数的第几层的时候发生的,然后返回给了谁。
  • 如果不是返回给最外层函数,调用者就收不到返回值。

发表评论