1、递归函数

0x01：什么是递归函数

通过前面的学习知道一个函数可以调用其他函数。
如果一个函数在内部不调用其它的函数，而是自己本身的话，这个函数就是递归函数。
函数里面调用函数（调用自己），必须注意一个结束的条件，不然将永远递归下去

（就像while true 开头，不包含 break 和 return 语句的循环），因为他从理论上来说永远不会结束。 你想要的是能对你有帮助的递归函数，这样的递归函数分为两类：

• 基线条件（针对最小的问题） ： 满足这种条件是函数将直接返回一个值。
• 递归条件：包含一个或多个调用，这些调用旨在解决问题的一部分。

这里的关键是：可以将问题分解为较小的部分，可以避免递归没完没了，因为问题会被分为成基线条件可以解决最小问题。

0x02：递归函数的作用

举个例子，我们来计算阶乘 n! = 1 * 2 * 3 * ... * n
解决办法1:使用循环来完成

def cal(num):
    result,i = 1,1
    while i <= num:  # 根据值来进行一个判断
        result *= i
        i+= 1
    return result
print(cal(3))

看阶乘的规律

1! = 1
2! = 2 × 1 = 2 × 1!
3! = 3 × 2 × 1 = 3 × 2!
4! = 4 × 3 × 2 × 1 = 4 × 3!
...
n! = n × (n-1)!

解决办法2:使用递归来实现

def factorail(n):
  if n == 0:   # 定义 n=0 的时候返回的值，因为 0 的阶乘 = 1
    return 1
  return  n * factorail(n -1 )


print(factorail(6))

原理

# 使用递归求斐波那契数列的第 n 个数字， 我们把第一个和第二个的值都为1 ，就一直递归到第一个和第二个的值，在进行相加即可
#  1,1,2,3,5,8,13,21,34,55,89,144
'''
def  fibonaccei(n):
  if n == 2 or n == 1:
    return 1
  return fibonaccei(n - 2)  + fibonaccei(n -1 )
print(fibonaccei(9))

'''

0x03：二分查找案例：

二分查找案例：
def binary_seach(alist,item):
    if len(alist) == 0:
        return False
    else:
        mid = len(alist) // 2   # middle 记录中间位置索引
        if item == alist[mid]:  # 如果查找元素与中间位置元素相等 则返回真
            return True
        elif item < alist[mid]:  # 如果查找元素小于中间位置元素，则进行列表切片缩小列表范围
            return binary_seach(alist[:mid],item)
        else:
            return bin6ary_seach(alist[mid+1:],item)

if __name__ == '__main__':
    alist = [5, 10, 15, 18, 35, 55, 65, 75, 99]
    print(binary_seach(alist,200))   # 查找列表中不存在的数据
    print("__________________")
    print(binary_seach(alist,15))     # 查找列表中存在的数据