code for the sum of a Fibonacci sequence doesnt give the correct sum

Question

I wrote this code to calculate the sum of any n that I input for the Fibonacci sequence.

def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    elif n==2:
        return 2
    else:
        num = fib(n-1) + fib(n-2)
        return num 
    return sum(num)

fib(7)

This produces an output of 21 when it's supposed to produce an outcome of 20? It always seems to output a sum of one more than the actual sum

Note that `fib(2)` should also be equal to `fib(0) + fib(1)`, which is not the case with your definition. — Thierry Lathuille, Nov 19 '19 at 20:03
Your base cases are wrong. The sequence starts `0, 1, 1, 2, ...`, not `0, 1, 2, ...`. — chepner, Nov 19 '19 at 20:03
Also, your last `return` will (luckily, as it would raise an error) never be reached. — Thierry Lathuille, Nov 19 '19 at 20:04

azro · Answer 1 · 2019-11-19T21:27:04.293

It's because for n=2 the result is f(0)+f(1)= 0+1 =1 and not 2 so return 1 so you can remove that condition, also the sum code is useless and it not reachable, so it becomes :

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

# can be shorten with python if/else inline syntax
def fib(n):
    return n if n <= 1 else fib(n - 1) + fib(n - 2)

You can find others implementations here : How to write the Fibonacci Sequence?

TO get the sum of fibo values, you may store the values, to not count them a lots of time, solution : array. And if you manage to use it several time, get the array out of the function, here is an example of how to use it to be performant

fibonacci_numbers = [0, 1]
def fibo_setup(max_value=10):
    """Compute the values until a limit, and store in a list"""
    for i in range(len(fibonacci_numbers), max_value):
        fibonacci_numbers.append(fibonacci_numbers[i - 1] + fibonacci_numbers[i - 2])

def fibo(n):
    """Retrieve a fibo value using the array, compute if not present"""
    if len(fibonacci_numbers) < n:
        fibo_setup(n + 1)
    return fibonacci_numbers[n]

def fibo_sum(n):
    """Get the sum of fibo values, and before it checks that the array is filled"""
    fibo_setup(n)
    return sum(fibonacci_numbers[:n])

if __name__ == '__main__':
    fibo_setup(10)
    print(fibo(12))
    print(fibo_sum(15))

this works out the fibonacci sequence at n=7 but not the sum of 1-7 — user12386893, Nov 19 '19 at 20:16
@user12386893 I've edit at the bottom with a complete solution — azro, Nov 19 '19 at 21:27

score 0 · Answer 2 · answered Nov 19 '19 at 20:18

0

While it's tempting to write a neat short recursive function, it's usually is a bad idea, specially, when you need to access all the values, e.g. in this case

fib(0) + fib(1) + ... + fib(n)

Instead, employ an array:

def fib_sum(n):
    # edge cases
    if n==0: return 0
    if n<=2: return n-1

    # store first n fibonacci numbers
    fib = [0] * n

    # initialization
    fib[1] = 1

    for i in range(2,n):
        fib[i] = fib[i-1] + fib[i-2]

    return sum(fib)

fib_sum(7)
# 20

answered Nov 19 '19 at 20:18

Quang Hoang

131,600
10
43
63

what does this part of the code do exactly? fibo = [0] * n how does it store the Fibonacci numbers? or is this creating the array to then later store the Fibonacci number? – user12386893 Nov 20 '19 at 10:38
Yes. That’s an array to store the first n Fibonacci numbers. – Quang Hoang Nov 20 '19 at 12:02

code for the sum of a Fibonacci sequence doesnt give the correct sum

2 Answers2