递归是非常基本的算法，虽然非常好用，但是也非常耗费空间资源，所以编程中在保证代码简洁性和可读性的前提下，如果可以不使用递归则尽量不使用递归。而尾递归则是一种可以在不使用其他辅助空间的情况下被消除的递归：如果一个函数的递归调用和调用的返回值总是在函数的末尾，且返回值不包括在表达式中，则这种递归通常称之为尾递归。尾递归是可以通过循环来达到相同目的的，平常开发的时候如果没有注意这种情况的话，很容易踩到这个坑。
尾递归示例
使用二分查找算法实现查找一个列表中是否包含指定元素。
使用递归实现（尾递归）：
def binary_search(data, item, low, high):
mid = (low + high) // 2
if low > high:
return False
elif item == data[mid]:
return True
elif item < data[mid]:
return binary_search(data, item, low, mid - 1)
else:
return binary_search(data, item, mid + 1, high)
使用循环实现（消除尾递归）：
def binary_search(data, item):
low = 0
high = len(data) - 1
while low <= high:
mid = (low + high) // 2
if item == data[mid]:
return True
elif item < data[mid]:
high = mid - 1
else:
low = mid + 1
return False
注意，虽然递归调用的返回值在函数最后且返回了，但调用本身的返回值属于表达式的一部分，那这种递归就不属于尾递归了（虽然不属于尾递归，如果可以不用递归实现，也可以考虑其他更好的方法）。
# 求一个正整数的阶乘
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/235392.html
