python 递归函数

前言：本篇关于递归基本借鉴下面博客讲解加入自己理解。

http://www.cnblogs.com/alex3714/articles/5740985.html）

1.递归函数定义

如果一个函数在函数内部调用自己，那这个函数就是递归函数。如：

def sum(arg,stop):
    print(arg)
    if arg<stop:
        arg+=arg
        sum(arg,stop)

sum(1,20)

2.递归的特性

1） 必须有一个明确的结束条件，不然进入了死循环。

2） 每次进入更深一层递归时，问题规模相比上次递归都应有所减少

3） 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

如把上例中return返回值，返回的是最初的栈值：

def sum(arg,stop):
    print(arg)
    if arg<stop:
        arg+=arg
        sum(arg,stop)
    return arg

print(sum(1,20))

#运行结果
1
2
4
8
16
32
2          #返回值一层一层返回arg的值，最后返回最初的栈值

3.应用递归获取斐波那契数列

斐波那契数列是指前两个数加起组成第三个数规律的一组数列，如：0,1,1,2,3,5,8,13.

def func(arg1,arg2,stop):
    if arg1==0:
        print(arg1,arg2)
    arg3 =arg1+arg2
    print(arg3)
    if arg3<stop:
        func(arg2,arg3,stop)

func(0,1,10)

#运行结果
0 1
1
2
3
5
8
13

4.应用递归实现二分法查找

当数据量很大时查找，适宜采用二分法。采用二分法查找时，数据需是排好序的，取中间值与查找值比较而取舍一半数据，这样可以缩减查找时间。

def binary_search(data_source,find_n):
    mid=int(len(data_source)/2)
    if len(data_source)>1:
        if data_source[mid] > find_n:    #data in left
            print('data in left of [%s]'%data_source[mid])
            binary_search(data_source[:mid],find_n)
        elif data_source[mid] < find_n:    #data in right
            print('data in left of [%s]'%data_source[mid])
            binary_search(data_source[mid:],find_n)
        else:
            print('found find_s:',data_source[mid])
    else:
        print('cannot find ....')

if __name__=='__main__':
    data = list(range(1,50000))
    binary_search(data,36378)

#运行结果
data in left of [25000]
data in left of [37500]
data in left of [31250]
data in left of [34375]
data in left of [35937]
data in left of [36718]
data in left of [36327]
data in left of [36522]
data in left of [36424]
data in left of [36375]
data in left of [36399]
data in left of [36387]
data in left of [36381]
found find_s: 36378