# Find nth Fibonacci Number, using iteration and recursion

I'm a beginner programmer and I came upon this problem which is to find the n​th number in the Fibonacci series.

I used to solve the problem using a for loop; today I learned about recursion but there is a problem: when I pass 40 or 41 to the recursive function, it takes a bit of time to calculate it, while in the iterative method it would instantly give me the answers.

I have these questions:

1. Why do most people (on the Internet) recommend using recursion? Because it's simpler and easier to write the program? (Logically I thought that we should write it in a way that is fast and simple)
2. Here are the 2 methods that a beginner like me can handle writing at the moment. Is there a better way than these two methods? And are these methods complex?

Here is the recursive method:

    #include <iostream>
using namespace std;

unsigned long long fibonacci(unsigned long long n);

unsigned long long fibonacci(unsigned long long n){
if(n<=1)
return n;                                //base case
return fibonacci(n-1) + fibonacci(n-2);      //recursive case
}

int main(){
unsigned int a {};
cout << "Enter number: ";
cin >> a;
cout << fibonacci(a) << endl;
return 0;
}


And here is the iterative (looping) method:

#include <iostream>
using namespace std;
int main() {
int n{};
unsigned long long t1{0}, t2{1};
unsigned long long sum{};
cout << "Enter the number of terms: ";
cin >> n;
cout << "Fibonacci Series: ";
for (int i{2}; i < n; ++i) {
sum = t1 + t2;
t1 = t2;
t2 = sum;
}
cout << t2;
return 0;
}


Note: I know that using namespace std is a bad idea but I have also tried the same thing without the namespace and still I get the delay, so I did it here because it's easy to understand.

Edit1: First of all I would like to thank everyone who commented and answered my question...To be honest I didn't think that this question would bring a lot of attention to the community so I appreciate the time you put on this and it means a lot to me.

Edit2: Let me demonstrate some of the things that might have been a little odd to you.

Q: What do you mean by better when you say if there is a better way than these two methods?
A: By better, I meant that the code shall be simple and also takes less time to execute or perform the calculations

Q: What do you mean when you say most people (on the internet) use recursion?
A: I've seen code out there that uses recursion to solve problems. The two common problems I've seen are Fibonacci and Factorial of a number. For factorial, I have also tried both methods (iteration and recursion) but I didn't get a delay for both of them when I type large numbers like 40 or 50. The common problem I saw with recursion is that eventually, you may run out of memory space because it is calling itself multiple times which results in a stack overflow (because stack as a part of memory will be filled). Although this problem doesn't occur in this example. So this raises another question here:

When should we use recursion?

• For most reviewers on the site, it is easier to understand if you done have the using namespace std; statement. Feb 18 '20 at 19:27
• The using namespace std; is not about speed. It is about maintainability. It is a bad habit that in the long run will make your code hard to maintain (and cause bugs (see linked article). That is why it is considered bad practice. Why is “using namespace std;” considered bad practice? Feb 19 '20 at 6:29
• "Iteration or recursion" -- neither, there's a closed form solution Feb 19 '20 at 12:40
• @canton7: The closed form solution will be wrong starting at Fib(70), presuming binary64 doubles are used. The iterative solution will give a correct answer with 64-bit integer arithmetic up to Fib(92) inclusive. Feb 20 '20 at 0:59
• I'm completely not seeing the explanation of why the recursive method is slow in the answers: the reason is that it pretty much builds the Fibonacci number by adding lots of ones together (and therefore will add an exponentially growing number of them) Feb 20 '20 at 14:19

Why do most people (on the internet) recommend using recursion because it's simpler and easier to write the program? Logically I thought that we should write it in a way that is fast and simple.

This is a perceptive question. I wrote an article about exactly this topic in 2004, which you can read here:

https://docs.microsoft.com/en-us/archive/blogs/ericlippert/how-not-to-teach-recursion

Summing up: there are two good reasons to teach people to use recursion to solve Fib:

• First, because it clearly illustrates what you have learned today. A naive translation of a recursive definition into a recursive function can often lead to poor performance. That's an important lesson for beginners to take away. (EXERCISE: How many additions does your naive recursive program execute for a given n? The answer may surprise you.)
• Second, because the first lesson then gives us an opportunity to lead the beginner to learn how to write a recursive algorithm so that it performs well.

Unfortunately, as you have discovered, a great many people on the internet have not internalized that teaching recursion via fib is solely useful as an illustration of bad uses of recursion and how to fix them, and not in itself an example of a good use of recursion.

It would be much better if people attempting to teach recursion did so by providing a mix of good and bad recursive algorithms, and taught how to spot and avoid the bad ones.

Is there a better way than these two methods?

Another lesson you'll quickly learn is that asking "which is better?" is a sure way to get back the reply: "can you describe a clear metric for betterness?"

So: can you describe a clear metric for betterness?

If the goal is to print out the nth fib number, you can do way "better" than either of your solutions:

unsigned long long fibs[] = { 1, 1, 2, 3, 5, 8, ... }
if (0 <= n && n < sizeof(fibs... blah blah blah))
cout << fibs[n];


Done. There are only so many fib numbers that fit into a long. You can look them up on the internet, copy them into your program, and you've got a short, fast fib program with no loops at all. That's "better" to me.

But remember, the point of this exercise is to teach you something about recursion, so by that metric my program is certainly not "better".

are these methods complex?

By "these methods" I think you mean "methods of writing recursively-stated algorithms into code other than naive recursion and unrolling the recursion into a loop".

That's a matter of opinion. Let me put it this way.

I work on a compiler team, and I interview a lot of people. My standard coding question involves writing a simple recursive algorithm on binary trees that is inefficient when written the naive way, but can be made efficient by making a few simple refactorings. If the candidate is unable to write that clear, straightforward, efficient code, that's an easy no-hire.

Where things get interesting is when I ask "suppose you had to remove the left-hand recursion from this tree traversal; how might you do it?"

There are standard techniques for removing recursions. Dynamic programming reduces recursions. You could make an explicit stack and use a loop. You could make the whole algorithm tail recursive and use a language that supports tailcalls. You could use a language with cocalls. You could use continuation passing style and build a "trampoline" execution loop.

Some of these techniques are, from the perspective of the novice, terribly complicated. I ask the question because I want to know what is in the developer's toolbox.

• I also like this as an interview question. Not because of the code (as everybody can write the recursive version and anybody that has looked at any coding test has seen the iterative version). But because it leads into lots of discussions about techniques. Love the article. Feb 19 '20 at 6:38
• "are these methods complex" - there are iterative algorithms specific to Fibonacci unrelated to optimizing recursion, one involves raising a matrix to a power, the other involves a Lucas sequence. I think this is what the OP is asking about. Feb 19 '20 at 8:59
• @DavidPeterson: That's right; in many operating systems, particularly Windows, you only get a fixed amount of stack space and by default, the activation frames for method calls go on the stack. That implies that unbounded or very deep recursions will "blow the stack". One reason for knowing about the techniques I discussed for removing recursions is to prevent stack overflows. Feb 19 '20 at 20:02
• @DavidPeterson: A concept you might want to study is that of continuation. The continuation of a particular piece of code is the thing that will happen when this code is done. The stack is how we reify continuation in "normal" function calls: you call a function, and what happens next? Either the function throws, in which case the continuation is the exception handler, or it never returns normally, or it does return normally; the "normal return" continuation information is stored on the stack. Feb 19 '20 at 20:04
• @DavidPeterson: Since activations of asynchronous calls do not logically form a stack, we do not use the stack to store continuations of async workflows -- or, rather, we use it less. Getting your head around continuations is tricky, but once you do, many facts about programming become much more clear. Feb 19 '20 at 20:05

As other answers state, your iterative algorithm outperforms your recursive algorithm because the former remembers previous intermediate results (or at least one such result) while the latter doesn’t. Of course, one can write recursive algorithms that remember previous results.

For Fibonacci numbers that’s simple enough since you only need to remember one such result. Using the tuple unpacking syntax of C++17 for sake of readability:

#include <utility>

namespace mynamespace {

namespace detail {

std::pair<unsigned long long, unsigned long long>
fibonacci_impl(unsigned long long n)
{
if (n <= 1)
return { n, 0 };

auto [fib1, fib2] = fibonacci_impl(n - 1);
return { fib1 + fib2, fib1 };
}

} // end namespace detail

unsigned long long fibonacci(unsigned long long n)
{
return detail::fibonacci_impl(n).first;
}

} // end namespace mynamespace


detail::fibonacci_impl returns the result of fibonacci(n) and fibonacci(n-1) (as a pair) for reuse by the caller. A sufficiently smart compiler can optimize away the overhead of pair packing and unpacking to leave the function call overhead (see compiler explorer) as the only disadvantage of the recursive algorithm over its iterative counterpart.

I enclosed the function declarations into their own namespace mynamespace and a sub-namespace mynamespace::detail.

If your program is more than trivial you should place your declarations (functions, classes or otherwise) into a separate namespace. For declarations that are meant to be used outside of your own program (e. g. a programming library) it’s highly recommended to do so to avoid name shadowing issues and confusion in general.

If your library declares stuff that is only meant to be used from inside this library, it’s customary to place it inside a sub-namespace whose name indicates its intended nature. Examples that I encountered for such sub-namespace names include: detail, internal, implementation or, shorter, impl.

• Don't define names starting with two underscores. Feb 20 '20 at 1:54
• A single underscore is not as bad as two of them, but still unusual. I don't remember the exact rules for the single underscore, but some of these names are still reserved. Feb 21 '20 at 14:48
• Why are you putting underscores at the start of your function's name? Feb 21 '20 at 19:18
• @RolandIllig: Acknowledged and fixed. I read up on C++ naming styles which recommend (anonymous) sub-namespaces for declarations relating to implementation details. Feb 22 '20 at 20:48
• @theonlygusti: see above Feb 22 '20 at 20:48

In the recursive version of the code you don't need the function prototype unsigned long long fibonacci(unsigned long long n);.

As you mentioned you shouldn't have the using namespace std; statement in the code.

Why do most people (on the internet) recommend using recursion because it's simpler and easier to write the program?(well logically I thought that we should write it in a way that is fast and simple)

Because it is an opinion.

In the iterative version you should also have the fibonacci(unsigned long long n) function to make main() simpler.

• Thank you for your help..and also let's say that if we don't include using namespace std in our code then for every cout we should say std::cout...and so on and so forth for other elements....otherwise we get an error... Feb 18 '20 at 19:43
• @DavidPeterson Yes, and std::cout is clearer than cout because the latter can mean either std::cout or my::obscure::library::cout (which overloads the << operator to print the values in the form of nasal demons), depending on context and ADL, so code readers have to stop and think for a moment. This problem is not so evident with cout, but consider data, arg, visit, etc., none of which I can immediately realize is actually a name from the standard library. using namespace std; also pollutes the global namespace with tons of common identifiers, causing name clashes. Feb 19 '20 at 4:02

Neither nor!

David Foerster's __fibonacci_impl has a matrix representation, where the matrix can be brought into a diagonal shape, evaluating to a difference of two exponential functions, where the absolute value of the latter one is less than one and so may be replaced by a rounding operator.

 const double sqr5 = sqrt(5);
const double phi = 0.5 * (sqr5+1);

double Fn = floor( pow(phi,n) / sqr5 + 0.5); // n<=70

• This fails starting at Fib(71). Feb 20 '20 at 1:05
• @MonicaPolk it just has accuracy limitations due to numerical errors of double. Integer int64 based slower approach will hit integeroverflow around Fib(92) thus failing miserably and not just being inaccurate. Feb 20 '20 at 6:30
• @ALX23z - for unsigned 64 bit integers, the limit is Fib(93). Feb 21 '20 at 8:21
• I just hope this is meant as a joke as this answers almost none of OP's questions and totally misses the point. Feb 22 '20 at 12:36
• @ALX23z: Then by your own analysis the integer version is superior in an apple-to-apples comparison. Explain how the failure of this method starting at Fib(71) is less miserable than the failure of the integer iteration at Fib(93)? Feb 24 '20 at 0:58

Is there a better way than these two methods?And are these methods complex?

There are better methods, and although not that complex, few people would be able to develop such methods (such as Lucas sequence relations) on their own without relying on some reference.

For the recursive version shown in the question, the number of instances (calls) made to fibonacci(n) will be 2 * fibonacci(n+1) - 1.

As for better methods, Fibonacci(n) can be implemented in O(log(n)) time by raising a 2 x 2 matrix = {{1,1},{1,0}} to a power using exponentiation by repeated squaring, but this takes 12 variables. This can be reduced to 5 variables using a method based on Lucas sequence relations.

Example code; c and d are used for the repeated squaring, while a and b are the cumulative results and end up as a = fib(n+1), b = fib(n).

Note: older compilers may be missing <inttypes.h> or <stdint.h>. If <inttypes.h> is not present (Visual Studio 2010), use compiler specific format string for uint64_t. If <stdint.h> is not present (Visual Studio 2005), use typedef ... uint64_t (usually unsigned long long) and the appropriate format string.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

uint64_t fib(uint64_t n)
{
uint64_t a, b, c, d;
a = d = 1;
b = c = 0;
while (1) {
if (n & 1) {
a = ad + a*c + b*d;
}
n >>= 1;
if (n == 0)
break;
{
uint64_t dd = d*d;
d = dd + 2 * d*c;
c = dd + c*c;
}
}
return b;
}

int main(void)
{
uint64_t n;
for (n = 0; n <= 93; n++)
printf("%20" PRIu64 " %20" PRIu64 "\n", n, fib(n));
return 0;
}


The code is based on Lucas sequence relations for Fibonacci numbers.

https://en.wikipedia.org/wiki/Lucas_sequence#Other_relations

Specifically these equations:

F(m)   = F(m-1) + F(m-2)
F(m+n) = F(m+1) F(n) + F(m) F(n-1)
F(2n)  = F(n) L(n) = F(n) (F(n+1) + F(n-1))
= F(n)((F(n) + F(n-1)) + F(n-1))
= F(n) F(n) + 2 F(n) F(n-1)


Initial state:

a = F(1) = 1
b = F(0) = 0
c = F(0) = 0
d = F(1) = 1


n is treated as the sum of powers of 2: 2^a + 2^b + ... for each iteration i (starting from 0), let p = 2^i, then

c = F(p-1)
d = F(p)


To advance to the next iteration, c and d are advanced to F(next power of 2):

d' = F(2p) = F(p) F(p+1) + F(p) F(p-1)
= F(p)(F(p) + F(p-1)) + F(p) F(p-1)
= F(p) F(p) + F(p) F(p-1) + F(p) F(p-1)
= F(p) F(p) + 2 F(p) F(p-1)
= d d + 2 c d

c' = F(2p-1) = F(p+p-1) = F(p+1) F(p-1) + F(p) F(p-2)
= (F(p) + F(p-1)) F(p-1) + F(p) (F(p) - F(p-1))
= F(p) F(p-1) + F(p-1) F(p-1) + F(p) F(p) - F(p) F(p-1)
= F(p) F(p) + F(p-1) F(p-1)
= d d + c c


During the calculation of a and b, let m = current cumulative sum of bits of n:

b = F(m)
a = F(m+1)


To update a and b for 1 bits in n corresponding to p = current power of 2:

a' = F(m+1+p) = F(m+2) F(p) + F(m+1) F(p-1)
= (F(m+1)+F(m)) F(p) + F(m+1) F(p-1)
= F(m+1) F(p) + F(m) F(p) + F(m) F(p-1)
= a d + b d + b c

b' = F(m+p) = F(m+1) F(p) + F(m) F(p-1)
= a d + b c


Note that if b' is the max value for uint64_t, a' will overflow, but it's not an issue. However, the algorithm can be modified so that when completed, a = fib(n-1):

a = fib(-1) = 1
b = fib(0)  = 0

a = fib(m-1)
b = fib(m)

b' = fib(m+p)
= fib(m+1)fib(p) + fib(m)fib(p-1)
= (fib(m) + fib(m-1))fib(p) + fib(m)fib(p-1)
= fib(m)fib(p) + fib(m-1)fib(p) + fib(m)fib(p-1)
= bd           + ad             + bc

a' = fib(m-1+p)
= fib(m)fib(p) + fib(m-1)fib(p-1)
= bd           + ac

uint64_t fib(uint64_t n)
{
uint64_t a, b, c, d;
a = d = 1;
b = c = 0;
while (1) {
if (n & 1) {
uint64_t bd = b*d;
b = bd + a*d + b*c;
a = bd + a*c;
}
n >>= 1;
if (n == 0)
break;
{
uint64_t dd = d*d;
d = dd + 2*d*c;
c = dd + c*c;
}
}
return b;
}

• The #define makes this program needlessly complicated. Plus the bad variable names. And main is missing the return type. We are not in the 1980s anymore. Feb 20 '20 at 1:52
• @RolandIllig - The variable names are the same as those used in other examples of Lucas sequence methods, with the variation that c and d are sometimes named p and q. I don't how the int on main got lost, but it is fixed now. I've been having issues trying to find current examples of this code that clearly state it's a variation of Lucas sequence. I'll update my answer with link(s) if/when I find them. The defines are probably a legacy issue in case a compiler doesn't optimize the two products to a single variable (register). This is an old algorithm. Feb 20 '20 at 2:35
• @RolandIllig - I found a variation of the method using a, b, p, q here, but no reference to Lucas sequence. Feb 20 '20 at 2:50
• @RolandIllig - I haven't been able to find a link for how this code works, so I updated my answer with my own explanation, based on Lucas sequence relations. Feb 20 '20 at 11:03
• @RolandIllig - the defines are gone, replaced by block local variables. Toby Speight updated the printf to use inttypes.h. (Note VS2010 doesn't have inttypes.h, and VS2005 doesn't have stdint.h, which I mentioned in my answer). Feb 20 '20 at 19:22

By using that iterative solution, you are indirectly using Dynamic Programming (DP)

Recursion might be faster in some cases.

For example, let's say you have a 2d road of size n * m. There are blockages in the road, so you can't pass through them.

The objective is to check if there exists any path from the top-left corner to the bottom-right (You can only move right or down).

The recursive solution would win as the iterative solution will take O(N * M) in the best and the worst case, but the recursive solution will take O(N + M) for the best case and O(N * M) for the worst case.

An iterative solution with a detailed explanation is given here, but I can't find any sources for a recursive solution.

The recursive solution of yours is much slower than the iterative one because you are not using memoization.

Memoization is not that hard to understand.

• I don't understand why two people down-voted my answer. Would someone please explain why so that I won't repeat the same mistake in the future? Thanks a lot!
– Sriv
Feb 19 '20 at 11:56
• I fail to see how you answer the questions (why is recursion usually recommended for calculating the Fibonacci sequence? What are possible alternatives to these 2 approach?), it doesn't comment on the code itself, and uses pictures to display text, which is bad form since it cannot be searched and used as a reference in the future. The first 2 points make your answer look like an ad for dynamic programming rather than a code review, and you should use blockquotes and links to the sources for the 3rd point. Feb 19 '20 at 13:35
• A giant purple rectangle is just hideous, and when scrolling down the page just screams "ADVERTISEMENT!" which causes me to just skip way further down fast and get that thing off my screen. There is absolutely NO reason to have that here. If you're going to have a quote, use text to do it. Although that bit seems completely irrelevant to the requested code review (IMHO). Feb 19 '20 at 17:18
• @1201ProgramAlarm 😂 Nice point! I've changed that
– Sriv
Feb 19 '20 at 17:35
• @gazoh You are right. I thought the OP asked for recursion in general and not specifically for Fibonacci. I am quite sorry. I will edit my answer as soon as possible!
– Sriv
Feb 19 '20 at 17:38

Evaluating Asymptotic Complexity e.g. with gmp library, shows that rcgldr's algorithm, implementing efficient matrix powers with O(log(n)) mutlipications, has best performance among presented algorithms.

Below compared for n in range 0 .... 647028207

1. Straight Iteration, n steps, takes O(n^1.60) time.
2. "Golden Ratio", i.e. above called the "Binet's Formula" due to floating arithmetics takes O(n^1.25) time
3. rcgldr's algorithm with O(n^1.029) time.

The diagram shows evaluation time for Fn in seconds over n, both axis logarithmic with base 10,

While this question already has many answers, one of which is accepted, I would like to point out that the (naïve) recursive solution presented by OP has a much worse complexity than the iterative version. However, it is perfectly possible to split up the problem into a main function to be called by the user, and an internal helper function doing the work recursively. The below has the same complexity as the OP's iterative solution (and will, in fact, be compiled into an iterative solution by a good compiler), and essentially consists of two one-liners:

unsigned long long
fibonacci_internal(unsigned long long n,
unsigned long long t1,
unsigned long long t2) {
return (n == 0) ? t1 : fibonacci_internal(n - 1, t2, t2 + t1);
}

unsigned long long fibonacci(unsigned long long n) {
return fibonacci_internal(n, 0, 1);
}


EDIT: Fixed typos in code.

EDIT 2: The reason a sufficiently smart compiler can transform the above into an iterative solution (essentially a loop that uses no extra stack frames) is that the recursive call occurs at the end of a logical branch before returning, with no other operation between the recursive call and the return. This is called tail recursion. Please have a look at https://stackoverflow.com/questions/33923 for more information. The OP's original function has an addition between the recursive call and the return, therefore it is not tail-recursive, the recursive call must use extra stack frames, and the compiler cannot turn it into an iterative solution.

The debate around recursive vs iterative code is endless. Some say that recursive code is more "compact" and simpler to understand.. In both cases (recursion or iteration) there will be some 'load' on the system when the value of n i.e. fib(n) grows large.Thus fib(5) will be calculated instantly but fib(40) will show up after a slight delay. Of course your data type must also be large enough to hold the result.In C I think unsigned long long int on a 64-bit system is the largest that you can get.Beyond that you might want to try to hold the intermediate results in an array.Then the only constraint will be memory.

The equation given by Binet:

fib[n] = (phi^n - (-phi)^(-n)) / sqrt(5) where phi=(1+sqrt(5))/2

will give an accurate answer (unlike the answer above of fib [n] = phi^n / sqrt(5) + 1/2), which breaks down at values of n greater than 70).

Since you can calculate it directly, iteration and recursion are unnecessary.

• 1. Please cite correctly: "[phi^n / sqrt(5) + 1/2]" comes with Gaussian brackets! 2. It is an accurate simplification of your "Binet"-formula, if you follow the math above, valid for all natural numbers, including zero. 3. Inaccurate is the C++-double-power function for larger exponents. The Binet-formula has same dependency and limits in C++ runtime with IEEE doubles. Feb 22 '20 at 23:21
• Thanks for correcting my misunderstanding, Sam, about the Gaussian brackets. I see you are right about the simplification, due to taking the integer part, since the first part of Binet's Formula, i.e. phi^n/sqrt(5), alternates just above and just under the integer result that is adjusted to by the second part, i.e. -(-phi)^(-n)/sqrt(5). In other words, my comment was unnecessary, so I humbly withdraw. :) Feb 25 '20 at 4:10

Finally tribute to

## When should we use recursion?

In view of formal verification of an algorithm you would write an invariant, which is a mathematical model of your algorithm, valid for any variables and arguments, which you prove then. When your result is anyway defined as recursion, as we have it for Fibonacci or Factorial series, proof may be performed by complete induction, where the induction step is trivially the recursive definition.

Investigating the asymptotic complexity, i.e. with large numbers, overhead for instantiating a function many times does not carry.

Though, the recursion depth is crucial as in runtime environments like C++. You must not have a StackOverflow; a recursion depth of O(n) as in the initial example is not acceptable!

So whenever you can control the asymptotic recursion depth and runtime is for the most part in evaluation of your intermediary results, a recursive algorithm is suggested.

Following is an algorithm with digit-wise evaluation of Fibonacci numbers, using two integer series derived from the relationship of Binet's Formula and Hyperbolic Functions; Complexity and recursion depth is O(log(n)).

#include <iostream>

typedef unsigned long long N;

static void FibRec(int n, N& S, N&C)
{
if (n >= 1)
{
N S1, C1;
FibRec(n >> 1, S1, C1);
if ((n >> 1) & 1)
{
C = (5 * C1 * C1 + S1 * S1) >> 1;
}
else
{
C = (C1 * C1 + 5 * S1 * S1) >> 1;
}
S= C1 * S1;
if (n & 1)
{
N Cn0 = C;
C = (C + S) >> 1;
S= (5 * S+ Cn0) >> 1;
}
}
else
{
S = 0;
C = 2;
}
}

N fibonacci(int n)
{
N S, C;
FibRec(n, S,C);
return (n & 1) ? C : S;
}

int main()
{
for (int n = 0; n<=93; n++)
{
std::cout << "Fib[" << n << "] = " << fibonacci(n) << std::endl;
}
}