Sum of range(1,n,2) values using recursion

Question

I'm trying to translate a loop to a recursive algorithm. Fairly simple, I've just hadn't been able to make it ignore the n value when summing up the values, like range does.

This is the iterative function:

def function(n):
    total=0
    for i in range(1,n,2):
        total += i
    print(total)

function(5) # Output: 4

This is the recursive I've tried:

def function1(n):
    if n==1:
        return n
    else:
        return n+function1(n-2)
function(5) # Output: 9

So function1 does sum the n when it should be ignored. Cause range() does not include the stop number.

Then, I tried:

def f1(n):
    def f_recursive(n):
        if n==1 or n==2:
            return 1
        elif n==0:
            return 0
        else:
            return n + f_recursive(n - 2)

    return f_recursive(n) - n 

print(f1(5)) # Output: 4 Yeiii!!

But then I realised, that only works for odd numbers. Not for even. If f1(6) then you get 4 when it should be 9, because it ends up being 11-6= 9.

So silly me I tried:

def f1(n):
    def f_recursive(n):
        if n==1 or n==2:
            return 1
        elif n==0:
            return 0
        elif n%2 == 0:
            return n + f_recursive(n - 3)

        elif n%2 == 1:
            return n + f_recursive(n - 2)

    return f_recursive(n) - n 

print(f1(6))

Which of course also did not work. Am I not understanding recursion properly here?

Answer 1

The tricky part is excluding the upper bound. If the upper bound is your only parameter n, you have to know when it's the first call, and when it's an intermediate (recursive) call. Alternatively, if inner functions are okay, you could instead just count from 1 up until you hit n:

def function1(n):
    def inner(i):
        return 0 if i >= n else i + inner(i + 2)
    return inner(1)

Answer 2

You want to compute the sum of all odd integers from 1 up to, but not including, n.

This leaves 2 possibilities:

1. If n is <= 1, there are no numbers to sum, so the sum is 0.
2. The highest number that might be included in the list is n-1, but only if it is odd. Either way, the rest of the sum is "the sum of all odd integers from 1 up to, but not including, n-1" (sound familiar?)

This translates to:

def f1(n):
    if n <= 1:
        return 0
    else:
        isOdd = (n-1)%2==1
        return f1(n-1) + (n-1 if isOdd else 0)

Answer 3

The problem with your recursion is that you're returning n rather than the value in the range (list) that you're currently on, this poses a problem since n is not inclusive within the range and should not be added to the final total

Ideally you need to reverse the logic and traverse it the same way your range does

def func(start,end, step):
    if(start >= end):
        return 0

    return start + func(start + step, end, step)