Recursion with memory vs loop

Question

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?

It's a good learning problem for learning recursion as well as learning algorithms. Think of solving the same problem using tail recursion — bigbounty
– bigbounty, Commented Aug 3, 2020 at 10:32
in a language with no tail call optimization, you can't ever do efficient recursion anyway — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Aug 3, 2020 at 10:34
Fibonacci is a good example for recursion, as it shown both the elegance but also the limitations, and how to overcome them. The second approach does not need to store all the numbers because it is building the solution "bottom-up" where it only needs the last two values. — tobias_k
– tobias_k, Commented Aug 3, 2020 at 10:40

Jasmijn · Accepted Answer · 2022-06-30 14:01:31Z

2

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)

edited Jun 30, 2022 at 14:01

answered Aug 3, 2020 at 12:14

Jasmijn

10.8k2 gold badges33 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Nayuki Over a year ago

Actually, this piece of code I published is placed in the public domain.

Jasmijn Over a year ago

Ah, I must have missed that. I'll include it in my answer for clarity.

Collectives™ on Stack Overflow

Recursion with memory vs loop

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related