Python Higher Order Function: New way to find Fibonacci Numbers

Question

I am given a question to write a higher order function to find fibonacci numbers. First, I am defined the combine function below:

def combine(f, op ,n):
    result = f(0)
    for i in range(n):
        result = op(result, f(i))
return result

For example, new_fib(10) = 55

The function I'm supposed to define is thus to find the nth fibonacci number:

def new_fib(n):
    def f(x):
        ...
    def op(x, y):
        ...
    return combine(f, op, n+1)

The idea I have to solve this question is simply to chuck the fibonacci sequence into the f(x) function, but I've been facing a lot of problems. Here's what I have now:

def new_fib(n):
    def op(x,y):
        return x+y
    def f(x):
        a,b = 0, 1
        fibs = ()
        for i in range(n+1):
            a, b = b, a+b
            fibs += (a,)
        return fibs[x]
    return combine(f, op, n+1)

But that's wrong because it accumulates too fast. I can picture why in my head, but cannot figure a way out to get around it. Does anyone have any advice? It would be greatly appreciated! Thank you!

Answer 1

The operation should just be a, b => b, a+b, and you iterate it.

Code could be:

def new_fib(n):
    def op(a, b):
        return b, a+b
    def combine(initial, op, n):
        a, b = initial
        for i in range(n):
            a, b = op(a, b)
        return b
    if n == 0:                # special processing for 0 and 1
        return 0
    if n == 1:
        return 1
    return combine((0,1), op, n - 1)

It correctly gives 55 for new_fib(10)