遞歸函數

Question

設S是該組有序對遞歸定義的整數的所述子集由

基礎步驟：（0，0）∈S.

遞歸步驟：如果（A，B）∈ S，

然後（A，b + 1）∈S，（A + 1，b + 1）∈S，和（a + 2，b + 1）∈S.

列表元素S生產的前四款申請

def subset(a,b): 
base=[] 
if base == []: 
    base.append((a,b)) 
    return base 

elif (a,b) in base: 
    base.append(subset(a,b+1)) 
    base.append(subset(a+1,b+1)) 
    base.append(subset(a+2,b+1)) 
    return base 


for number in range(0,5): 
    for number2 in range(0,5): 
     print(*subset(number,number2)) 

輸出是

（0，0） （0，1） （0，2） （0，3） （0，4） （1，0） （1,1 ） （1，2） （1，3） （1，4） （2，0） （2，1） （2,2） （2，3） （2，4） （3,0） （3,1） （3,2） （3,3） （3,4） （4,0） （4,1） （4,2） （4,3） （4,4）

但正確答案是比我得到了更多。 （0,1），（1,1）和（2,1）都在S中。如果我們將遞歸步應用於這些，我們將（0,2），（1,2），（ （2,2），（3,2）和（4,2）。下一輪給我們（0,3），（1,3），（2,3），（3,3），（4,3），（5,3）和（6,3）。第四組應用程序增加了（0,4），（1,4），（2,4），（3,4），（4,4），（5,4），（6,4），（ 7,4）和（8,4）。

我的代碼有什麼問題？

Answer 1

這是你想要的嗎？根據您想要的結果：

def subset(a): 
    #Returns a list that contains all (i, a + 1) from i = 0 to i = (a + 1) * 2 + 1 
    return [(i, a + 1) for i in range((a + 1) * 2 + 1)] 

setList = [] 
for i in range(4): 
    setList += subset(i) #Fill a list with subset result from i = 0 -> 3 

print(setList) 

如果你想使用一個遞歸函數，你也可以這樣做：

def subset(a, b): 
    if a < b * 2: 
    #Returns a list that contains (a, b) and unzipped result of subset(a + 1, b) 
    #Otherwise it would add a list in the list 
    return [(a, b), *subset(a + 1, b)] 
    else: 
    return [(a, b)] #If deepest element of recursion, just return [(a, b)] 

setList = [] 
for i in range(5): 
    setList += subset(0, i) 

print(setList)