北屋教程网

专注编程知识分享,从入门到精通的编程学习平台

python递归_python递归函数

什么叫做递归函数

如果一个函数在内部调用了自身,这个函数就被称为递归函数。

但是自己调用自己,会不会进入死循环呢,永远停止不了呢,所有一个函数要满足以下几个条件才能算作递归函数

  1. 函数自身调用自身
  2. 每一次递归相对于上一次递归来说,查询或者搜索的范围都应该相应的减少
  3. 要有明确的结束条件(不然一直死循环,程序停止不了)


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))
控制面板
您好,欢迎到访网站!
  查看权限
网站分类
最新留言