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:


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)
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 &lt;iostream&gt;
    using namespace std;

    unsigned long long fibonacci(unsigned long long n);

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

    int main(){
        unsigned int a {};
        cout &lt;&lt; "Enter number: ";
        cin &gt;&gt; a;
        cout &lt;&lt; fibonacci(a) &lt;&lt; endl;
        return 0;
    }


And here is the iterative (looping) method:

#include &lt;iostream&gt;
using namespace std;
int main() {
    int n{};
    unsigned long long t1{0}, t2{1};
    unsigned long long sum{};
    cout &lt;&lt; "Enter the number of terms: ";
    cin &gt;&gt; n;
    cout &lt;&lt; "Fibonacci Series: ";
    for (int i{2}; i &lt; n; ++i) {
        sum = t1 + t2;
        t1 = t2;
        t2 = sum;
    }
    cout &lt;&lt; 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?
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 &lt;= n &amp;&amp; n &lt; sizeof(fibs... blah blah blah))
   cout &lt;&lt; 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.