递归函数
在一个函数里在调用这个函数本身.
递归的默认最大深度: 998
修改默认最大深度
- import sys
- print(sys.setrecursionlimit(100000))
- import sys
- sys.setrecursionlimit(1000000)
- count = 1
- def my_func():
- global count
- print(count)
- count += 1
- my_func()
- my_func()
- ===========================
- def my_age(n,start=23):
- if n == 2:
- return start
- elif 0 <n < 2:
- return my_age(n + 1) - 2
- elif n> 2 :
- return my_age(n - 1) + 2
- else:
- return '不存在.'
- print(eval('my_age')(2))
二分查找算法
一个偶然的机会, 我想起以前还在谷歌上班的时候, 有时候大家会在饭桌上讨论最新想出来的一些面试题. 在众多有趣又有难度的题目中, 有一道老题却是大家都纷纷选择避开的, 那就是去实现二分查找.
因为它很好写, 却很难写对. 可以想象问了这道题后, 在 5 分钟之内面试的同学会相当自信的将那一小段代码交给我们, 剩下的就是考验面试官能否在更短的时间内看出这段代码的 bug 了.
二分查找是什么呢, 这个不只程序员, 其他很多非技术人员也会. 比如我想一个 1 到 100 以内的数, 你来猜, 我告诉你每次猜的是大了还是小了, 你会先猜 50, 然后 25, 然后... 用不了几个问题就猜出来了. 1 到 100 范围太小的话, 我们放大点猜个人名, 你问中国人外国人, 古代人现代人, 男的女的, 用不了几个问题也问出来了. 在计算机里, 则是在一个有序数组里面, 不断通过二分的方法缩小关键字的可能下标范围. 当然了, 我们不一定在一个有序数组里查找, 也可以在一个很大的状态空间里, 去查找一个单调函数的取值. 这样的做法, 似乎编个程序很容易实现, 但是,
D.Knuth 大神说了: Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky 虽然二分查找的基本思想相对来说很直接, 但具体实现起来有特别多的坑.
另一位大神, 编程珠玑的作者 Jon Bentley, 他做了我们在文章开头不敢做的事, 他布置作业让他的学生们写二分查找, 然后他一个个来看. 结果呢, 他发现 90% 是错的. 因此在他的编程珠玑这本书中, 专门有一章讲解了二分查找, 虽然他的范例仍然是错的, 见下面的 Java Bug. 埋下这个 bug 的人, 也正式 Jon Bentley 的学生.
还有好事者, 更是找了许多教科书, 发现 20 本教科书里面, 只有 5 本是写对了的, 于是他发了一篇文章到 ACM. 当然这是早在 1988 年的时候.
如果有这样一个列表, 让你从这个列表中找到 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]
- def search(num,l,start=None,end=None):
- start = start if start else 0
- end = end if end else len(l) - 1
- mid = (end - start)//2 + start
- if start> end:
- return None
- elif l[mid]> num :
- return search(num,l,start,mid-1)
- elif l[mid] < num:
- return search(num,l,mid+1,end)
- elif l[mid] == num:
- return mid
- Python Day 15 (递归函数, 二分查找算法)
来源: http://www.bubuko.com/infodetail-2606956.html