CODEWITHSUNDEEP
pythonrecursion
LegendWK
LegendWK

Reputation: 194

Recursion with memory vs loop

I've made two functions for computing the Fibonacci Sequence, one using recursion with memory and one using a loop;

def fib_rec(n, dic = {0 : 0, 1 : 1}):
    if n in dic:
        return dic[n]
    else:
        fib = fib_rec(n - 2, dic) + fib_rec(n - 1, dic)
        dic[n] = fib
        return fib
    


def fib_loop(n):
    if n == 0 or n == 1:
        return n
    else:
        smaller = 0
        larger = 1
        for i in range(1, n):
            smaller, larger = larger, smaller + larger
        return larger

I've heard that the Fibonacci Sequence often is solved using recursion, but I'm wondering why. Both my algorithms are of linear time complexity, but the one using a loop will not have to carry a dictionary of all past Fibonacci numbers, it also won't exceed Python's recursion depth.

Is this problem solved using recursion only to teach recursion or am I missing something?

Upvotes: 0

Views: 108

Answers (1)

Jasmijn
Jasmijn

Reputation: 10452

The usual recursive O(N) Fibonacci implementation is more like this:

def fib(n, a=0, b=1):
    if n == 0: return a
    if n == 1: return b
    return fib(n - 1, b, a + b)

The advantage with this approach (aside from the fact that it uses O(1) memory) is that it is tail-recursive: some compilers and/or runtimes can take advantage of that to secretly convert it to a simple JUMP instruction. This is called tail-call optimization.

Python, sadly, doesn't use this strategy, so it will use extra memory for the call stack, which as you noted quickly runs into Python's recursion depth limit.

The Fibonacci sequence is mostly a toy problem, used for teaching people how to write algorithms and about big Oh notation. It has elegant functional solutions as well as showing the strengths of dynamic programming (basically your dictionary-based solution), but it's also practically a solved problem.

We can also go a lot faster. The page https://www.nayuki.io/page/fast-fibonacci-algorithms describes how. It includes a fast doubling algorithm written in Python:

# 
# Fast doubling Fibonacci algorithm (Python)
# by Project Nayuki, 2015. Public domain.
# https://www.nayuki.io/page/fast-fibonacci-algorithms
# 


# (Public) Returns F(n).
def fibonacci(n):
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    return _fib(n)[0]


# (Private) Returns the tuple (F(n), F(n+1)).
def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n // 2)
        c = a * (b * 2 - a)
        d = a * a + b * b
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

Upvotes: 2

Related Questions