What should I do? I have a recursive function that returns the mth item of a n-bonacci sequence. It-CodePudding

I have the following recursive function to get the mth term of a n-bonacci sequence as shown below this question. My problem is that the use of for and while loops is totally banned from the code, so I need to get rid off

for i in range(1, n 1): 
    temp  = n_bonacci(n,m-i)

and convert the code into something that is not a loop but nevertheless achieves the same effect. Among the things I can use, but this is not an exclusive enumeration, is: (1) use built-in functions like sum() and .join() and (2) use list comprehensions.

The full code is as follows:

def n_bonacci(n,m):  #n is the number of n initial terms; m is the mth term.
    if (m < n-1):
        return 0
    elif (m == n-1):
        return 1
    else:
        temp = 0
        #[temp  = n_bonacci(n,m-i) for i in range(n)] #this is an attempt at using list comprehension
        for i in range(1, n 1):
            temp  = n_bonacci(n,m-i)
        return temp

print("n_bonacci:",n_bonacci(2,10))
print("n_bonacci:",n_bonacci(7,20))

CodePudding user response：

Here's a solution that avoids any type of loop, including loops hidden inside comprehensions:

def n_bonacci_loopless(n, m):
    def inner(i, c):
        if i == m:
            return sum(c)
        else:
            return inner(i 1, c[-(n-1):]   [sum(c)])

    if m < n-1:
        return 0
    elif (m == n-1):
        return 1
    else:
        return inner(n, [0] * (n-1)   [1])

The base cases are the same, but for recursive cases it initialises a list of collected results c with n-1 zeroes, followed by a one, the sum of which would be the correct answer for m == n.

For m > n, the inner function is called again as long as i < m, summing the list and appending the result to the end of the last n-1 elements of the list so far.

If you are allowed to use comprehensions, the answer is trivial:

def n_bonacci(n,m):
    if (m < n-1):
        return 0
    elif (m == n-1):
        return 1
    else:
        return sum(n_bonacci(n, m-i) for i in range(1, n 1))

CodePudding user response：

You can rewrite the code as follows using list comprehensions:

def n_bonacci(n,m):  #n is the number of n initial terms; m is the mth term.
    if (m < n-1):
        return 0
    elif (m == n-1):
        return 1
    else:
        return sum(n_bonacci(n, m-i) for i in range(1, n   1))

print("n_bonacci:",n_bonacci(2,10))
print("n_bonacci:",n_bonacci(7,20))

To go beyond @Grismar 's answer you can write your own version of sum which doesn't use loops.

def n_bonacci_loopless(n, m):
    def recsum(l, s=0):
        return recsum(l[1:], s   l[0])

    def inner(i, c):
        if i == m:
            return recsum(c)
        else:
            return inner(i 1, c[-(n-1):]   [recsum(c)])

    if m < n-1:
        return 0
    elif (m == n-1):
        return 1
    else:
        return inner(n, [0] * (n-1)   [1])