python小球落地問題及解決(遞歸函數)

Posted on by

問題

一個球從 100 米高的自由落下，每次落地後反跳回原高度的一半。求第10次彈起的高度與途徑的總路程

什麼是遞歸函數

函數的遞歸調用是函數嵌套調用的一種特殊形式,在調用一個函數的過程中又直接或者間接地調用該函數本身,稱之為函數的遞歸調用

遞歸死循環是沒有意義的

遞歸調用必須有兩個明確的階段:

1. 回溯: 一次次遞歸調用下去,說白瞭就一個重復的過程,

  • 但需要註意的是每一次重復問題的規模都應該有所減少,
  • 直到逼近一個最終的結果,即回溯階段一定要有一個明確的結束條件

2. 遞推: 往回一層一層推算出結果

例子

假設有5個人，第五個人的年齡是第四個年齡+，以此類推

'''
age(5) = age(4) + 2
age(4) = age(3) + 2
age(3) = age(2) + 2
age(2) = age(1) + 2
age(1) = 18
'''

我們可以將第幾個人定義成n，然後形成一個數學格式：

age(n) = age(n-1) + 2     # n>1
age(n) = 18               # n=1

這時候隻需要創建函數，把這兩塊寫入，即可完成遞歸函數的創建：

def age(n):
    if n == 1:
        return 18
    if n > 1:
        return age(n-1) + 2
print(age(5))

小球落地解題思路

首先我們需要註意三個點

1、小球從100米高度落下，所以小球在第一次彈起的過程中就已經行走瞭100m

2、小球最後一次彈起並沒有下落

3、每次彈起的高度需要*2才是此次彈起的距離

far = [100]
def jump(n):     
    if n == 1:
        far.append(100)
        return 50
    else:
        b = jump(n-1) / 2
        far.append(b*2)    
        return b
print(jump(10))
print(far)
print(sum(far)-jump(10))

python遞歸函數介紹

1、代碼

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
print([fibonacci(x) for x in range(10)])

2、運行截圖

在這裡插入圖片描述

3、補充說明

【1】遞歸必須有終止條件

【2】遞歸的規模要比上次的小

【3】遞歸的效率很低，可以通過程序調試看出，進去是幾層出來又得幾層，使得存儲空間變大。

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。

推薦閱讀：