本文和大家分享的主要是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)源：博客園