Python之递归函数

Python之递归函数

　递归解决的问题：就是通过参数，来控制每一次调用而缩小的计算规模。

　　适合的场景：数据的规模在减少，但是，解决问题的思路没有改变。

　　结束递归的标志：return

 　　什么叫递归：在一个函数里再调用这个函数本身

　　　　比如老和尚讲故事：从前有个山，山里有个庙，庙里有个老和尚讲故事。这就是一个死循环的递归。

while True:
    print('老和尚讲故事。。。。')

　　但因为已经了解了函数，就用函数的模式去实现。还可以顺便将这个功能解耦。

def story():
    s = ‘老和尚讲故事。。。’
    print(s)

while True:
    story()

　　这是可以将story函数与while循环解开。说白了就是讲打印功能独立出来。

　　但是也可以这样写：　

def story():
    s = """
    从前有个山，山里有座庙，庙里老和尚讲故事，
    讲的什么呢？
    """
    print(s)
    story()
    
story()

　　这样写和上一段写的结构其实是一直的。但是会有区别。第二种写法会报错。

RecursionError: maximum recursion depth exceeded while calling a Python object

　　因为函数本身调用本身的话，这个函数是执行不完的，说白了就是一个while。不停的自己调自己玩。

　　恰好第二种写法就是一个标准的递归函数，自己玩自己了。递归函数如果不受外力的阻止会一直执行下去。但是我们之前已经说过关于函数调用的问题，每一次函数调用都会产生一个属于它自己的名称空间，如果一直调用下去，就会造成名称空间占用太多内存的问题，所以Python为了杜绝这种现象，强制的将递归层数控制在只有997层。没错，997，你买不了吃亏，买不了上当。

　　下面这种方法可以测试递归的深度:　

n = 0
def f():
    global n
    n +=1
    print(n)
    f()

f()

　　但是，既然深度是Python定的，那就可以更改。

import sys #所有和python相关的设置和方法
sys.setrecursionlimit(10000000)
n = 0
def f():
    global n
    n += 1
    print(n)
    f()

f()

　　我的电脑low，最深只有2万多一点点，大家可以自己试试自己的。

　　不过咱还是不推荐修改这个默认的递归深度，因为如果用997层递归都没有解决的问题要么是不适合使用递归来解决要么是你代码写的太烂了～～～

　　递归实例：

　　　　猜年龄：

　　　　　　猜A的年龄：

　　　　　　　　A比B大二岁

　　　　　　　　B比C大二岁

　　　　　　　　C比D大二岁

　　　　　　　　D比E大二岁

　　　　　　　　今天E，二十六岁高龄。

　　　　　　我们在这个猜年龄里可以发现规律，每人都比后一个大二岁，那么做一个N += 2不就好咯吗？

def age(a):
    if a == 1:
        return 26
    else:
        return age(a-1) + 2

age = age(5)
print(age)

　　　　　　#结束递归的标志：return

递归函数与三级菜单

　　三级菜单：

　　　　菜单：

menu = {
    '北京': {
        '海淀': {
            '五道口': {
                'soho': {},
                '网易': {},
                'google': {}
            },
            '中关村': {
                '爱奇艺': {},
                '汽车之家': {},
                'youku': {},
            },
            '上地': {
                '百度': {},
            },
        },
        '昌平': {
            '沙河': {
                '老男孩': {},
                '北航': {},
            },
            '天通苑': {},
            '回龙观': {},
        },
        '朝阳': {},
        '东城': {},
    },
    '上海': {
        '闵行': {
            "人民广场": {
                '炸鸡店': {}
            }
        },
        '闸北': {
            '火车战': {
                '携程': {}
            }
        },
        '浦东': {},
    },
    '山东': {},
}

　　　　三级菜单初级版本：　　　

def ThreeLMenu(menu):
    for key in menu:
        print(key)
    k = input(">>>menu:")
    if k in menu:
        ThreeLMenu(menu[k])

ThreeLMenu(menu)

 　　　　三级菜单完整版：

def threeLM(dic):
    while True:
        for k in dic:print(k)
        key = input('input>>').strip()
        if key == 'b' or key == 'q':return key
        elif key in dic.keys() and dic[key]:
            ret = threeLM(dic[key])
            if ret == 'q': return 'q'

threeLM(menu)

　　递归实现：

l = [menu]
while l:
    for key in l[-1]:print(key)
    k = input('input>>').strip()   # 北京
    if k in l[-1].keys() and l[-1][k]:l.append(l[-1][k])
    elif k == 'b':l.pop()
    elif k == 'q':break

 递归总结：

　　1. 必须有一个明确的结束条件，return

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

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

递归实现二分查找

　　在列表中找到需要的数据

#列表操作
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]
# 在l中找到66的位置print(l.index(66))

　　自己也可以写一个方法达到列表index的查找的功能：

#列表操作
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]
# 在l中找到66的位置
# print(l.index(66))

num = 0
for i in l:
    if i == 66:
        print(num)
    num += 1

　　但是，在查找中，我们发现，无论是列表的index还是自己写的方法，都是将列表从起始位置开始遍历的。

　　就好比上面的例子。我要找66，它的index值是17，那么列表或for循环就要去遍历17次，才能找到我想要的结果。

　　我只想说，慢。

　　所以。在这里，我们聊一下二分查找。

　　在有序的递增列表中。

　　二分查找，就好比是树的枝叶，走到一定的位置就左右分开。二分查找也是如此。它将L这个列表在中间一部两半，如果我们要找66，

　　那么在分开后的位置，66会和那个位置的数进行比较。看是大还是小。因为是递增的，所以不要想太多。

　　大的还，就在分开的后半段列表中，继续中间左右分。直至找到我们需要的数值位置。

　　你可能觉得如此这般会更麻烦，其实不然。数据量小的是会不实用。但是在庞大的数据量面前，还是蛮好的。比如我有几十个亿的数据量，我要找一个四十亿伍仟三百万的数值的位置，咱们总不能去遍历40多亿次吧。用二分，也就判断分割不到20次就够了。

　　实现一个二分查找算法：

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 find(l,aim):
    """
    二分查找
    :param l:  列表
    :param aim: 要查找的数值的位置参数
    :return:
    """
    # 取列表的长度在整除计算中点
    mid =  len(l)//2
    # 判断中点的数值和要查找数值的大小
    if l[mid] > aim:
        new_l = l[:mid]
        return find(new_l,aim)
    elif l[mid] < aim:
        new_l = l[mid+1:]
        return find(new_l,aim)
    else:
        return l[mid]

#l 是列表，66是要找的数值，
print(find(l,66))

　　二分查找进阶：

#二分查找进阶,有起始和结束位置
l =[]
for i in range(50):
    if i%2==0:
        l.append(i)
# print(l.index(26))

def func(l,aim,start,end):
    """
    start和end可以限定查找的范围
    :param l: 列表
    :param aim: 要查找的数
    :param start: 列表开始查找的位置，列表的索引值
    :param end: 列表结束结束查找的位置，列表的索引值
    :return: 查找结果
    """
    mid = (start+end)//2
    if start < end:
        if l[mid] > aim:
            end = mid-1
            return func(l,aim,start,end)
        elif l[mid] < aim:
            start = mid+1
            return func(l,aim,start,end)
        else:
            # mid 打印索引值，l[mid]打印索引对应的值
            # return mid
            return l[mid]
    else:
        return "二货，没有这个数，瞎找啥呀！"

here1 = func(l,27,start=0,end=len(l)-1)
here2 = func(l,26,start=0,end=len(l)-1)
print(here1)
print(here2)

小功能：

#一个数，除以2到不能整除2为止

def cal(num):
    if num%2 == 0:
        new_num = num//2
        return cal(new_num)
    else:
        return num
print(cal(8))

 小功能：

#如果一个数除以2，就整除。
#不能被整除，就乘以3加一在除以2。
def func(num):
    print(num)
    if num == 1:
        return
    if num%2 ==0:
        num = num//2
    else:
        num = num*3+1
    func(num)

func(5)