10
\$\begingroup\$

A Fibonacci sequence is the integer sequence of 0, 1, 1, 2, 3, 5, 8.....

The first two terms are 0 and 1. All the other terms are obtained by adding the preceding two terms.

Here is my code:

def recur_fibonacci(n):
   if n <= 1:
       return n
   else:
       return(recur_fibonacci(n - 1) + recur_fibonacci(n - 2))

nterms = int(input("How many terms? "))

if nterms <= 0:
   print("Please enter a positive integer!")
else:
   print("Fibonacci sequence:")
   for i in range(nterms):
       print(recur_fibonacci(i))

So I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

\$\endgroup\$
  • 2
    \$\begingroup\$ Your biggest issue here is algorithmic, but several of the answers comment on code style/PEP (and yet leave the fundamental problem unaddressed). This un-memoised algorithm solves the same subproblem many times; in fact try fib(1000) and you will see you will not be able to run it. You need to cache the results of subproblems. \$\endgroup\$ – Tommy May 21 at 19:27
  • 1
    \$\begingroup\$ I will also note that you are talking about computing the Fibonacci sequence recursively, but you actually compute Fibonacci numbers recursively and use a loop to compute the Fibonacci sequence. \$\endgroup\$ – Jörg W Mittag May 21 at 22:04
  • 1
    \$\begingroup\$ @Tommy There are un-memoised fibonacci implementations that run in O(n). They just don’t use the naïve algorithm. \$\endgroup\$ – Konrad Rudolph May 22 at 9:04
  • 1
    \$\begingroup\$ For people viewing this question, take a look at Konrad Rudolph's answer, which provides a very good answer to my question (alongside other questions), too. \$\endgroup\$ – Justin May 22 at 11:36
  • 1
    \$\begingroup\$ @Justin, uptonogood's answer is the best by far. The others focus in on the trees and don't see the forest. \$\endgroup\$ – Peter Taylor May 22 at 11:42
14
\$\begingroup\$

Since other answers have focused on the code quality itself, I'll focus on performance.

Recursive Fibonacci by itself is \$O(2^n)\$ time.

Memoized fibonacci is linear time (check out functools.lru_cache for a quick and easy one). This is because fibonacci only sees a linear number of inputs, but each one gets seen many times, so caching old input/output pairs helps a lot.

Golden-ratio based solutions are approximately \$O(\log(n))\$, using \$\text{Fib}(n) = \frac{\phi^n - (1 - \phi)^n}{\sqrt 5}\$, where \$\phi\$ is the golden number. Note that without arbitrary precision numbers, this approach becomes inaccurate at large values of n. With increased precision, note that the cost of a multiplication increases as well, making the whole process a bit slower than log(n).

\$\endgroup\$
  • 4
    \$\begingroup\$ Since \$(1 - \phi) < 0.5\$ the second term can be ignored. You can just round \$\frac{\phi^n}{\sqrt 5}\$ to the nearest integer. \$\endgroup\$ – Florian F May 21 at 21:06
11
\$\begingroup\$

Some ideas:

  • A recursive solution is only as efficient as the equivalent iterative solution if the compiler/interpreter is smart enough to unroll it into an iterative solution. I'd love to be corrected, but I don't believe the Python interpreter is able to unroll recursive algorithms such as this one. If that is so, an iterative solution will be more efficient. An intermediate solution would be to create a cache of values returned so far to avoid having to recompute every value at every step.
  • This code, like basically any Python code, could benefit from a run through Black, flake8 and mypy with a strict configuration like this:

    [flake8]
    exclude =
        .git,
        __pycache__
    max-complexity = 4
    ignore = W503,E203
    
    [mypy]
    check_untyped_defs = true
    disallow_untyped_defs = true
    ignore_missing_imports = true
    no_implicit_optional = true
    warn_redundant_casts = true
    warn_return_any = true
    warn_unused_ignores = true
    
  • Taking user input interactively is bad, because it means your code can't be included in non-interactive code. Use argparse to get a value when starting the program.
\$\endgroup\$
  • 1
    \$\begingroup\$ @Jasper It's not tail recursion. The compiler has to a) call recur_fibonacci(n - 1) and save the return value; b) call recur_fibonacci(n - 2); c) add the saved value from the previous call to the returned value from this call; d) return the sum. The need for the addition after both calls means there is no opportunity for tail recursion. \$\endgroup\$ – Martin Bonner May 21 at 15:58
  • 4
    \$\begingroup\$ @Jasper Python doesn't and will never optimize tail recursion: stackoverflow.com/questions/13591970/… \$\endgroup\$ – mephistolotl May 21 at 16:06
  • 1
    \$\begingroup\$ @Jasper: an easy way to spot tail calls and tail recursion is to write the return expression in function call form. (Kind of like Lisp.) In this case, it would look something like this: plus(recur_fibonacci(n - 1), recur_fibonacci(n - 2)). Now, it becomes immediately obvious that the tail call is to plus and not to recur_fibonacci, and thus recur_fibonacci is not tail-recursive. Also, as was pointed out in another comment, Guido van Rossum has more or less explicitly forbidden TCO for any Python implementation. (Which makes zero sense, but that's how it is.) \$\endgroup\$ – Jörg W Mittag May 21 at 16:26
  • 2
    \$\begingroup\$ I would never recommend argparse or optparse anymore. click is vastly simpler. \$\endgroup\$ – jpmc26 May 22 at 2:51
  • 1
    \$\begingroup\$ @MartinBonner Good catch. It has been too long since I was taught about tail recursion and I was thinking about it too simply. \$\endgroup\$ – Jasper May 22 at 7:38
6
\$\begingroup\$

Building on @Snakes and Coffee's answer a bit:

The purpose of the program is to print out the sequence fib(0) to fib(n) - in which case, I would argue that a recursive solution is not the most appropriate.

Currently, when the code goes to calculate fib(5), it starts by calculating the value fib(4) - it actually did this already when it printed out fib(4) in the previous iteration, but this value is not reused and so the work is done again needlessly.

An alternative solution could be to build the list [fib(0), fib(1), fib(2) ... fib(n)]. This is not wasteful as every item in the list is used for calculation, as well as printed out. It also means that once fib(x) has been calculated, the value can be reused for free.

Were the Fibonacci function only being used a handful of times, a recursive solution would make more sense in terms of memory and elegance.

\$\endgroup\$
  • 2
    \$\begingroup\$ In terms of implementation, a generator would be appropriate for this use case. \$\endgroup\$ – Peter Taylor May 22 at 11:44
5
\$\begingroup\$

After a quick pass, this is what I have for you:

If/Else:

For a recursive function, you don't usually need to specify the else. Just return if the base case is true.

Validating User Input

To make sure the user enters the correct input, have it in a while True: loop. Then you can break when the user enters an input that satisfies the program.

Main

Use if __name__ == __main__. This ensures that it can't be run externally, and only from that file.

Updated Code, should you choose to use it:

def recur_fibonacci(n):
   if n <= 1:
       return n
   return(recur_fibonacci(n-1) + recur_fibonacci(n-2))

def main():
    while True:
        nterms = int(input("How many terms? "))

        if nterms <= 0:
            print("Please enter a positive integer!")
        else:
            print("Fibonacci sequence:")
            for i in range(nterms):
                print(recur_fibonacci(i))
            break

if __name__ == '__main__':
    main()
\$\endgroup\$
  • 5
    \$\begingroup\$ Since you already recommended using a while True loop, why not add a try...except ValeuError to catch the user entering a string that cannot be interpreted as an integer? \$\endgroup\$ – Graipher May 21 at 13:12
4
\$\begingroup\$

A few people mentioned that your implementation is inefficient. To emphasise just how inefficient it is, try calculating recur_fibonacci(35), and then recur_fibonacci(40):

On my computer, the former takes about a second, while the latter takes almost a minute. recur_fibonacci(41) will take more than twice as long.

However, contrary to what some people think recursion is not the problem here. Rather, the problem is algorithmic: For every Fibonacci number you calculate, you first calculate all previous Fibonacci numbers, and you do this again for each previous number, without remembering intermediate results.

This can be fixed by maintaining a “memory” of previous results — a process called memoisation. However, an alternative way of calculating Fibonacci numbers doesn’t require memoisation, and instead calculates a pair of adjacent Fibonacci numbers, rather than a single Fibonacci number. By doing this, the function never needs to re-calculate previous terms, it only need to calculate each pair once. This makes the algorithm’s runtime linear.

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


def fib(n):
    return fib_pair(n)[0]

This runs in microseconds even for large n (although it will at some point overflow the stack).

You might be reluctant to write two functions since you probably never actually need a pair of Fibonacci numbers. A trick is to store this pair as function arguments instead of the return value:1

def fib2(n, current = 0, next = 1):
    if n == 0: return current
    return fib2(n - 1, next, current + next)

1 A nice side-effect of this is that it results in a tail recursive function, which is a desirable property in recursive functions because it is isomorphic to iteration (to the point that some computer scientists call this type of recursion “iteration”), and can be trivially transformed, either via trampolines or by optimising compilers (Python implementations don’t currently do this).

\$\endgroup\$
  • 2
    \$\begingroup\$ I never thought I would see a good way to optimize a recursive fibonacci implementation. Very nice! \$\endgroup\$ – Lasse Vågsæther Karlsen May 22 at 12:49
  • 1
    \$\begingroup\$ I would suggest splitting pair into a, b. I think it would make it a little nicer to read. a, b = fib_pair(n - 1) return b, a + b \$\endgroup\$ – spyr03 May 23 at 15:06
  • \$\begingroup\$ @spyr03 That was my first version and I agree that it’s better but unfortunately pylint doesn’t like it and posting code that fails linting on a review site is a bit questionable. That said, I think we can agree that pylint is wrong here, and even the name n fails it. \$\endgroup\$ – Konrad Rudolph May 23 at 15:16
3
\$\begingroup\$

So I would like to know whether I could make this program shorter and more efficient.

Others have addressed style, but I will address algorithm.

The memoized recursion is a decent solution:

import functools

@functools.lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    else:
       return fib(n-1) + fib(n-2).

This memoization method allows you basically type in the recurrence relation \$F_n = F_{n-1} + F_{n-2}\$ and all of the work of organizing the order of evaluating the functions is automatically done for you.

However, in the case of Fibonacci, you really only need to be storing two values, because you can always use the pair \$(F_{n-1}, F_n)\$ to compute the "next" pair \$(F_n, F_{n+1})\$. For this reason, the following solution works, and is faster than above (fewer function calls). It also has the advantage of never causing stack overflows and using a constant amount of memory.

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a+b
    return a

Now, if you are computing some seriously huge numbers, you can exploit some interesting properties of matrix algebra to get an even faster solution. The basic property that we want to exploit is that \$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}. \$

Try this out yourself by computing this matrix times itself, times itself, etc. You should see that it boils down to the previous solution. But now we can apply exponentiation by squaring (with matrices rather than numbers) to get a faster solution. In particular, if we label \$ A = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}, \$

then we known that

\$ A^n = \begin{cases}\left(A^{n/2}\right)^2 &\text{if n is even}\\ A\left(A^{\lfloor n/2\rfloor}\right)^2 &\text{if n is odd}\end{cases} \$

This suggests the following implementation:

def matrix_square(a,b,c,d):
    return a*a+b*c, b*(a+d), c*(a+d), d*d+b*c

def matrix_times_A(a,b,c,d):
    return a+b, a, c+d, c

def fib_matrix(n):
    if n == 0:
        # identity matrix
        return 1, 0, 0, 1
    half_power = fib_matrix(n//2)
    even_power = matrix_square(*half_power)
    if n % 2 == 1:
        return matrix_times_A(*even_power)
    else:
        return even_power

def fib(n):
    return fib_matrix(n)[1]

This is already noticeably faster than the other methods for n=500_000. Plenty of further optimizations can be made here, and I'll leave those as an exercise. You might be able to figure out how to make this iterative rather than recursive.

Even further speed can be gained if you use the "fast doubling" recurrence shown here. That site looks like it also contains some implementations.

The last thing I'd like to add is that if your application does not require exact integer precision, you can use Binet's Formula. In fact, this formula can be derived by diagonalizing the matrix from above (a good exercise if you want to practice some linear algebra). Note that because \$|(1-\sqrt{5})/2|<1\$, the second term becomes insignificant, and is unnecessary to compute.

\$\endgroup\$
2
\$\begingroup\$

If your question is whether the recursive function could be made shorter, then the following is a way to rephrase your function in a more compact form:

def recur_fibonacci(n):
   return n if n <= 1 else recur_fibonacci(n-1) + recur_fibonacci(n-2)

This is assuming you must have a recursive solution. As others have already pointed out, the solution could be made more time-efficient by using a simple linear loop instead of recursion.

\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to Code Review! Users asking for feedback on their code usually want exactly that, feedback. At the moment, your code is a mere alternative solution. Please at least explain your reasoning. I also invite you to read How do I write a good answer?. \$\endgroup\$ – AlexV May 21 at 12:33
  • 2
    \$\begingroup\$ @AlexV: I added some more textual context. \$\endgroup\$ – slingeraap May 21 at 12:51
1
\$\begingroup\$

While memoization can result in impressive performance improvements, it's not really appropriate for this task, when a trivial loop would do what you want

def fib(n):
    res = [0, 1]
    if n < 2:
        return res[0:n]
    for i in range(2, n):
        res.append(res[i - 1] + res[i - 2])

    return res

But the answers all depend on the problem domain. This is linear and has no memory overhead. The memoised ones have memory overhead but if you're repeatedly generating fibonacci sequences, would eventually have improved performance.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.