How to check if recursion or iteration is the best for a particular program? [duplicate]

Question

In my college, I was asked to write a JAVA program for Fibonacci series. I used recursion to write that program.

But, the asst lecturer said that my algo is not efficient and asked me to analyze. He added that by convention, iteration is suitable in that program than recursion.

How to analyze our algorithm? How to check the space and time complexity in both iteration and recursion ? Just then, i found that these things are as important as the CORRECTNESS OF A PROGRAM.

Answer 1

As a thumbrule:

• Recursion is easy to understand for humans. But it is stack based and stack is always a finite resource.
• Iteration is a sequential, and at the same time is easier to debug. But at times can lead to difficult to understand algorithms which can be easily done via recursion.

So whenever the number of steps is limited to a small manageable number, you can go for recursion. As you will be confident the stack will never overflow and at the same time recursion code is compact and elegant.

If you want to explore more these might help. Recursion vs loops and Recursion or Iteration?

Edit As pointed out by @MrP, some special recursions, can be optimized by some compilers.

Answer 2

It doesn't have anything to do with the complexity of the algorithm: when you use recursion - each call creates a new frame on the stack - so if the recursion is too deep you might run into StackOverflow :)

By using iteration - you're running in a loop (potentially) over the same space (overriding the parameter previous values) which is faster as well as more secure from StackOverflow perspective.