本文和大家分享的主要是python的遞歸函數(shù)及二分查找算法相關(guān)內(nèi)容,一起來(lái)看看吧,希望對(duì)大家學(xué)習(xí)python有所幫助。
一、遞歸的定義
def story():
s = """
從前有個(gè)山,山里有座廟,廟里老和尚講故事,
講的什么呢?
"""
print(s)
story()
story()
老和尚講故事
遞歸的定義 —— 在一個(gè)函數(shù)里再調(diào)用這個(gè)函數(shù)本身。這種魔性的使用函數(shù)的方式就叫做 遞歸 。
遞歸的最大深度:997
1、python遞歸最大層數(shù)限制 997
2、最大層數(shù)限制是python默認(rèn)的,可以做修改
3、但是我們不建議你修改
n = 0def f():
global n
n += 1
print(n)
f()
f()
測(cè)試遞歸最大深度
如何修改遞歸最大深度:
import sys #所有和python相關(guān)的設(shè)置和方法
sys.setrecursionlimit(10000000)
n = 0def f():
global n
n += 1
print(n)
f()
f()
修改遞歸最大深度
遞歸的小實(shí)踐:
1、猜年齡:
#猜e的年齡#e比d大兩歲#d比c大兩歲#c比b大兩歲#b比a大兩歲 #a 40了
# 1.a age(1) = 40# 2.b age(1) + 2# 3.c age(2) + 2# 4.d age(3) + 2# 5.e age(4) + 2
def age(n):
if n == 1:
return 40
else:
ret = age(n-1)
return ret + 2
age(5)
猜年齡
2 、 一個(gè)數(shù),除2到不能整除2為止:
#一個(gè)數(shù),除2到不能整除2為止(以8為例)def cal(num):
if num % 2 == 0:
num = num // 2
return cal(num)
else:
return num
print(cal(8))
數(shù)字整除類1
3、整除類2
#如果一個(gè)數(shù) 可以整除2 就整除#不能整除就*3+1def func(num):
print(num)
if num == 1:
return
if num %2 == 0:
num = num //2
else:
num = num * 3 + 1
func(num)
func(5)
數(shù)字整除類2
遞歸函數(shù)與三級(jí)菜單
遞歸函數(shù)實(shí)現(xiàn)三級(jí)菜單
二、二分查找算法
給你一個(gè)數(shù)列讓你找出其中一個(gè)數(shù)的位置你怎么找?index?這是python給我們的內(nèi)置函數(shù)。那他內(nèi)部是怎么實(shí)現(xiàn)的呢?現(xiàn)在要求我們自己設(shè)計(jì)函數(shù)來(lái)實(shí)現(xiàn)這個(gè)功能。
數(shù)列例如: 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]
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]
i = 0for num in l:
if num == 66:
print(i)
i+=1
是不是感覺(jué)這個(gè)函數(shù)so easy但是我們所用的方法是循環(huán)列表然后一個(gè)一個(gè)對(duì)比。這個(gè)方法固然可以可是也只是適用于小的數(shù)組。如果這個(gè)數(shù)列很長(zhǎng)里面上萬(wàn)甚至更多,一個(gè)一個(gè)找效率太低。必須有一個(gè)新的算法來(lái)解決這個(gè)問(wèn)題。這就引出了今天另一個(gè)知識(shí)點(diǎn) 二分查找
二分查找算法:
算法:計(jì)算的方法
二分查找前提:有序的遞增列表
圖示:
這就是二分查找算法
簡(jiǎn)單二分法:
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 func(l,aim):
mid = (len(l)-1)//2
if l:
if aim > l[mid]:
func(l[mid+1:],aim)
elif aim < l[mid]:
func(l[:mid],aim)
elif aim == l[mid]:
print("bingo",mid)
else:
print('找不到')func(l,66)func(l,6)
二分法基礎(chǔ)版
二分法升級(jí):
def func(l, aim,start = 0,end = len(l)-1 ):
mid = (start+end)//2
if not l[start:end+1]:
return
elif aim > l[mid]:
return func(l,aim,mid+1,end)
elif aim < l[mid]:
return func(l,aim,start,mid-1)
elif aim == l[mid]:
print("bingo")
return mid
index = func(l,68)
print(index)
二分法查找升級(jí)版
小結(jié):
遞歸解決的問(wèn)題:
就是通過(guò)參數(shù),來(lái)控制每一次調(diào)用縮小計(jì)算的規(guī)模
適合的場(chǎng)景:
數(shù)據(jù)的規(guī)模在減小,但是解決問(wèn)題的思路沒(méi)有改變
結(jié)束遞歸的標(biāo)志:return
來(lái)源:博客園