python中递归调用
2024-10-01 03:56:30
递归一个通俗的解释就是,在函数中调用函数本身;伪代码如下:
In [31]: def fun():
....: fun() # 这个递归没有任何作用,只是为了说明什么是递归
递归(Recursion),在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。
在使用递归时,需要注意以下几点:
- 递归就是在过程或函数里调用自身
- 必须有一个明确的递归结束条件,称为递归出口。
注意: 切勿忘记递归出口,避免函数无限调用。
使用递归计算的一些方法
第一个阶乘:
阶乘的定义:
- 1的阶乘是1
- 大于1的树n的阶乘是n乘以(n-1)
def fun(n): #使用递归定义
if n == 1:
return n
else:
return n * fun(n-1) fun(5)
Out[72]: 120 def fun1(n): # 使用非递归
result = n
for i in range(1,n):
result *= i
return result fun1(5)
Out[74]: 120
第二个幂函数的实现
In [38]: def power1(x,y): # 不使用递归
....: result = 1
....: for i in range(y):
....: result *= x
....: return result
....: In [39]: power1(2,5)
Out[39]: 32 In [43]: def power2(x,y): #递归实现
....: if y == 0:
....: return 1
....: else:
....: return x * power2(x, y-1)
....: In [44]: power2(2,5)
Out[44]: 32
二分查找法
二分查找又叫折半查找:
#二分查找的队列必须是有序的
有如下一个列表
[2,5,6,7,21,54,67,76,87,98,100]
列表中有序的,用二分法查找列表中数字87的位置。
列表共有11个元素,首先折半11/2的值取6,第六个元素值为54.
87>54
所以87在列表的后半部分中。
然后再重复以上过程,直到找到数值为止。
二分查找的函数代码:(代码为python2.7的版本)
#!/usr/bin/env python
#*-* coding:utf -8 *-*
#二分法查找数值 import sys
import random def UnsortList(): ###如果没有指定参数,随机生成一个序列
list = []
long = random.randint(0,100)
for i in range(long):
list.append(random.randint(0,10000))
return list def BinarySearch(list, mark, low=0,uplow=None): #二分法查找
if not uplow:
uplow = len(list) -1
if low == uplow:
assert mark == list[uplow]
return uplow
else:
mid = (low + uplow) // 2
if mark > list[mid]:
return BinarySearch(list, mark,mid+1,uplow)
else:
return BinarySearch(list,mark,low,uplow=mid) def SuijiMark(list): ###在列表中随机挑选一个要查找的数据
l = len(list)
mark = list[random.randint(0,l) - 1]
return mark def main(): ####主函数
Ulist = []
print "1:随机产生列表,验证二分法"
print "2:用户自己输入数值生成列表,验证二分法"
answer = input("请输入对应的数字: ")
if answer == 1:
Ulist = UnsortList()
mark = SuijiMark(Ulist)
print "The list is %s" % Ulist
print "The mark is %s" % mark
print "The len of the list is %s " % len(Ulist)
elif answer == 2:
lang = input("请输入列表长度: ") ##根据输入的数值,组成列表
for i in range(lang):
Ulist.append(input("请输入列表第%d个值:" % (i + 1)))
mark = SuijiMark(Ulist)
print "the list is %s" % Ulist
print "the mark is %s" % mark
else:
print "请输入合法的数字"
Ulist.sort()
index = BinarySearch(Ulist, mark)
print "The index %s is %s" % (index, mark) if __name__ == "__main__":
main()
执行结果如下:
[root@mgto7 ~]# python erfen.py
1:随机产生列表,验证二分法
2:用户自己输入数值生成列表,验证二分法
请输入对应的数字: 1
The list is [4204, 3199, 8884, 4555, 4941, 5695, 5730, 7363, 5357, 7193, 532, 8270, 1173, 1526, 3278, 7526, 6461, 6470, 3962, 533, 5816]
The mark is 7526
The len of the list is 21
The index 18 is 7526
[root@mgto7 ~]# python erfen.py
1:随机产生列表,验证二分法
2:用户自己输入数值生成列表,验证二分法
请输入对应的数字: 2
请输入列表长度: 5
请输入列表第1个值:23
请输入列表第2个值:54
请输入列表第3个值:65
请输入列表第4个值:87
请输入列表第5个值:23
the list is [23, 54, 65, 87, 23]
the mark is 65
The index 3 is 65
最新文章
- Vue系列:在vux的popup组件中使用百度地图遇到显示不全的问题
- 查看哪些表的哪些列含有指定字符串(如‘andy’存在哪些表的哪些列中)
- WCF权限控制
- Win7下JDK环境变量的设置
- python判断key是否在字典用in不用has_key
- Javascript高级篇-Function对象
- navagationController 的子控制器如何取消右滑返回
- SpringTest 使用说明 -构建无污染纯绿色事务测试框架 (记录用)
- 在阿里云服务器ubuntu14.04运行netcore
- html5图片标签与属性
- NHibernate中使用memcache二级缓存
- eclipse安装svn插件的多种方式
- git视频教程
- SQLAlchemy表操作和增删改查
- Effective Java 第三版——27. 消除非检查警告
- Sqlserver 2008R2设置数据库只对特定用户可见
- [C][变量作用域]语句块
- nginx配置二级目录,反向代理不同ip+端口
- MySQL比like语句更高效写法locate position instr find_in_set
- layui表单验证