用遞歸函數掙扎，我做錯了什麼

我對python相當陌生，並且明白遞歸是一個重要的概念。我一直在涉足各種腳本以運用我的知識，並且提出了以下腳本來模擬彩票抽獎，您只需從49個數字中抽出6個數字，並與另外6個數字進行比較，看看您是否贏了。儘管使用遞歸函數取得了另一個函數的值，但我仍在掙扎。用遞歸函數掙扎，我做錯了什麼

我敢肯定，這將是直截了當的，但無法自己摸索。

這裏是到目前爲止我的代碼：

from random import randint 

def drawSix(): 
    six = [] 
    while len(six) < 6: 
     a = randint(1,49) 
     if a not in six: 
      six.append(a) 
    return sorted(six) 

def lottery(draw,ticket): 
    if draw == ticket: 
     return 'win' 
    return lottery(drawSix(),drawSix())

我調用函數與彩票（drawSix（），drawSix（））

，並得到遞歸以下。

Traceback (most recent call last): 
    File "<pyshell#0>", line 1, in <module> 
    lottery(drawSix(),drawSix()) 
    File "/Users/johnhopkins/Desktop/lottery.py", line 14, in lottery 
    return lottery(drawSix(),drawSix())

來源

2014-02-19 Hoppo

究竟是什麼問題？ – thefourtheye

我不斷收到遞歸錯誤請參閱原始帖子中的編輯 – Hoppo

@hivert查看最後一行.... –

def lottery(draw,ticket): 
    if draw == ticket: 
     return 'win' 
    return lottery(drawSix(),drawSix())

的你實際上產生兩個相同的門票的機率是相當大的，遠遠超過1000是Python中的最大堆棧大小。

您需要迭代執行此操作以避免吹動堆疊。

def lottery(draw,ticket): 
    while draw != ticket: 
     draw, ticket = drawSix(), drawSix() 
    return "win"

注意這有一個非常難看的O(inf)你可能最終，如果你是不吉利的運行下去這一點，仍然沒有找到一個成功的對

來源

2014-02-19 09:09:35

我不會匆忙買彩票！ ;） – Hoppo

是O(n) - 的lottery功能將繼續自稱，每個將自己的新版本放到調用堆棧中，直到有兩個匹配的數字時，它們會越陷越深。

這可能需要很長時間，Python最終會說「oi！stop it！」並崩潰。

一些編程語言有一個名爲「尾調用優化」功能，這意味着如果你試圖return相同功能的結果，而不是使一個新調用當前內部的功能，它只是替換本身在堆棧中。

Python不這樣做。

def lottery(): 
    while (drawSix() != drawSix()): 
     continue 
    return 'win!'

將具有與遞歸版本相同的效果，但不會因遞歸錯誤而死亡。

來源

2014-02-19 09:13:15 Daniel

那麼，你的問題已被回答，但我會建議改變你的drawSix函數。就目前而言，它可以在技術上永遠運行。 random有一個sample方法來生成唯一的號碼。

def drawSix(): 
    return sorted(random.sample(range(1, 50), 6))

來源

2014-02-19 09:16:51

您沒有犯任何編程錯誤。但是，獲得彩票的可能性非常小，因此您需要生成很多彩票。簡單的遞歸添加一些東西到堆棧中。

樂透門票的數量可以通過公式的組合與重複發現：

(49+6-1)!/(6! * (49-1)!) = 25827165

這是很多...減少數字6或49，添加一些調試行，你會看到代碼工作正常！

來源

2014-02-19 09:25:12 IPV3001

用遞歸函數掙扎，我做錯了什麼

回答

相關問題