递归：未创建 for 中每个元素的多个函数实例

Question

我有一个递归问题。 http://www.geeksforgeeks.org/print-increasing-sequences-length-k-first-n-natural-numbers/ 但是我看到没有发生对函数的递归调用。以下代码可能有什么问题：

def wrapper(n,k):
    list=[]
    for i in range(1,n+1):
        list.append(str(i))

    print rec_seq(list,k,0,'')

def rec_seq(list,k,i,prefix):
    #base case
    if k==0:
        return prefix

    else:
        for c in list[i:None]:
            newPrefix=prefix+c
            return rec_seq(list,k-1,i+1,newPrefix)

if __name__=='__main__':
    wrapper (5,3)

输出：123

Expected output :
            1 2 3
            1 2 4
            1 2 5
            1 3 4
            1 3 5
            1 4 5
            2 3 4
            2 3 5
            2 4 5
            3 4 5

Answer 1

在 for 循环中，如果您使用 return，则只会返回该奇异值。在您的情况下，它是这样的。

第一次调用rec_seq

for c in list[i:None]: #i=0, c='1'
    newPrefix=prefix+c #newPrefix = '' + '1'
    return rec_seq(list,k-1,i+1,newPrefix) #k-1 = 2, i+1 = 1

第二次通话

for c in list[i:None]: #i=1, c='2'
    newPrefix=prefix+c #newPrefix = '1' + '2'
    return rec_seq(list,k-1,i+1,newPrefix) #k-1 = 1, i+1 = 2

第三次通话

for c in list[i:None]: #i=2, c='3'
    newPrefix=prefix+c #newPrefix = '12' + '3'
    return rec_seq(list,k-1,i+1,newPrefix) #k-1 = 0, i+1 = 3

上次通话

if k==0: #True
    return prefix #prefix = '123'

所以回到链上，最后一个调用将“123”传递给第三个调用，第三个调用将它传递给第二个调用，一直回到原始调用 returns '123'

Answer 2

def wrapper(n,k):
    list=[]
    for i in range(1,n+1):
        list.append(str(i))

    rec_seq(list,k,0,'')

def rec_seq(list,k,i,prefix):
    #base case
    if k==0:
        print prefix
        return 

    else:
        for c in list[i:None]:
            if prefix=='':
                newPrefix=prefix+c
                rec_seq(list,k-1,i+1,newPrefix)
            else:
                if int(c)>int(prefix[-1]):
                    newPrefix=prefix+c
                    rec_seq(list,k-1,i+1,newPrefix)
        return    

if __name__=='__main__':
    wrapper (5,3)

递归：未创建 for 中每个元素的多个函数实例

Recursion : multiple instances of function for each element in for is not created

python

recursion

tail-recursion