使用一個遞歸調用

實現遞歸給定一個功能如下：F（N）= F（N-1）+ F（N-3）+ F（N-4）使用一個遞歸調用

f(0) = 1 
f(1) = 2 
f(2) = 3 
f(3) = 4

我知道到在一個函數內使用遞歸調用三次遞歸調用來實現它。但我想在函數內部只進行一次遞歸調用。如何做到這一點？

實現在此使用3個遞歸調用是我的代碼：

def recur(n): 
    if n == 0: 
    return 1 
    elif n == 1: 
    return 2 
    elif n == 2: 
    return 3 
    elif n == 3: 
    return 4 
    else: 
    return recur(n-1) + recur(n-3) + recur(n-4) #this breaks the rule because there are 3 calls to recur

來源

2015-06-01 ms8

你的嘗試是在正確的方向，但它需要一個略有變化：

def main(): 
    while True: 
    n = input("Enter number : ") 
    recur(1,2,3,4,1,int(n)) 

def recur(firstNum,secondNum,thirdNum,fourthNum,counter,n): 
    if counter==n: 
    print (firstNum) 
    return 
    elif counter < n: 
     recur (secondNum,thirdNum,fourthNum,firstNum+secondNum+fourthNum,counter+1,n)

來源

2015-06-01 05:45:05 sgp

它只給出1作爲輸出..：/。原因是1總是那麼任何n，所以它總是會顯示1 – ms8

@python_slayer糟糕。檢查編輯。現在好嗎？ – sgp

這answer在C＃中可能會給你一個提示如何做你想要什麼。

Fibbonacci使用Python一個遞歸調用如下：

def main(): 
    while True: 
    n = input("Enter number : ") 
    recur(0,1,1,int(n)) 

def recur(firstNum,secondNum,counter,n): 
    if counter==n : 
    print (firstNum) 
    return 
    elif counter < n 
     recur (secondNum,secondNum+firstNum,counter+1,n)

來源

2015-06-01 04:41:15

我做類似的東西，但對於n = 5得到14。這裏是我的代碼：http：//ideone.com/8zk4kI – ms8

我不想要斐波那契數字。請參閱問題：/ – ms8

哦，我很抱歉，我誤解了。 –

乍一看，這看起來像一個dynamic programming問題。對於這樣的問題，我非常喜歡memoization，因爲它使代碼保持良好可讀性，同時也提供了非常好的性能。使用python3.2 +你可以做這樣的事情（你可以用老的python版本做同樣的事情，但是你需要實現你自己的lru_cache或者安裝許多擁有類似工具的第三方之一）：

import functools 

@functools.lru_cache(128) 
def recur(n): 
    print("computing recur for {}".format(n)) 
    if n == 0: 
    return 1 
    elif n == 1: 
    return 2 
    elif n == 2: 
    return 3 
    elif n == 3: 
    return 4 
    else: 
    return recur(n-1) + recur(n-3) + recur(n-4)

注意該功能只被調用各n一次：

recur(6) 
# computing recur for 6 
# computing recur for 5 
# computing recur for 4 
# computing recur for 3 
# computing recur for 1 
# computing recur for 0 
# computing recur for 2

來源

2015-06-01 06:43:47

使用一個遞歸調用

回答

相關問題