什么叫做递归函数
如果一个函数在内部调用了自身,这个函数就被称为递归函数。
但是自己调用自己,会不会进入死循环呢,永远停止不了呢,所有一个函数要满足以下几个条件才能算作递归函数
- 函数自身调用自身
- 每一次递归相对于上一次递归来说,查询或者搜索的范围都应该相应的减少
- 要有明确的结束条件(不然一直死循环,程序停止不了)
1到100求和,不使用递归
def sum_number(n):
total = 0
for i in range(1, n + 1):
total += i
return total
sum_number(100)
1到100求和,使用递归
def sum_number(n):
if n <= 0:
return 0
return n+sum_number(n-1)
sum_number(100)
递归实现二分算法(面试常问)
二分算法的前提是,列表里面的元素必须是排好序的
如果有这样一个列表,让你从这个列表中找到66的位置,你要怎么做?
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]
1.简单版本
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 f(l, aim):
mid = len(l) // 2
if l[mid] > aim:
return f(l[0:mid], aim)
elif l[mid] < aim:
return f(l[mid + 1:], aim)
else:
return l[mid]
print(f(l, 66))
2.升级版本,找到位置
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 f(l, aim, start, end):
mid = (start + end) // 2
if l[mid] > aim:
return f(l, aim, start, mid - 1)
elif l[mid] < aim:
return f(l, aim, mid + 1, end)
elif l[mid] == aim:
return mid
else:
print("找不到")
print(f(l, 66, 0, len(l) - 1))