5

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.

Dale Steyn
  • 95
  • 1
  • 2
  • 10
  • If you use ints or longs you won't go much further than 60 or 70 recursions so it does not really matter. And you could cache results with the recursive method too. – assylias Aug 14 '13 at 07:29
  • Also: [recursion-or-looping?](http://stackoverflow.com/questions/13346424/recursion-or-looping?lq=1) – nawfal Dec 14 '13 at 07:33

4 Answers4

5

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.

Community
  • 1
  • 1
rocketboy
  • 9,573
  • 2
  • 34
  • 36
  • 2
    Just as a remark: recursion isn't always stack based. Some compilers will optimise tail recursion so it actually becomes an iteration. But ofcourse you cannot always rely on this. – MrP Aug 14 '13 at 07:08
  • @MrP right but like you said: a) "some" compilers - not all, and b) even a compiler that supports tail recursion optimization can't implement it for ANY recursion. Good comment! – Nir Alfasi Aug 14 '13 at 07:14
  • Thank you. I just found the series for first 7 terms. So I didn't find much difference in the difficulty of the two methods. But if you wish, can you explain me on your point, that "recursion code is compact and elegant" – Dale Steyn Aug 14 '13 at 07:41
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.

Nir Alfasi
  • 53,191
  • 11
  • 86
  • 129
2

I would suggest you to follow the link http://nptel.iitm.ac.in/courses.php?disciplineId=106 and find some lectures of Design and Analysis of Algorithms. Its very basic concept of designing algorithms.Good luck.

Jatin Malwal
  • 5,133
  • 2
  • 23
  • 26
1

The biggest problem with the fibonacci series is the time complexity of the algorithm, when you use simple recursion, you will be recalculating everything and doing a lot of double work. This is because when you calculate fib(n) using

int fib(int n) {
  if (n < 2) { return 1; }
  return fib(n-1) + fib(n-2)
}

you will be calculating fib(n-1), which calculates fib(n-2) and fib(n-3). But for calculating fib(n), you will already calculate fib(n-2). In order to improve this, you would need to store the temporary results. This is usually easier using iteration and starting from i = 0 going up to n. This way you can easily store the last two results and avoid calculating the same values over and over.

An easy way to see if an algorithm is efficient is to try and solve it for a few increasingly harder examples. You can also calculate it more accurately. Take the fibonacci example above. Calling fib(n) would take the complexity O(fib(n)) = O(fib(n-1)) +O(fib(n-2)) + 1 (let's just take 1 for the addition). Let's assume that O(fib(0)) = O(fib(1)) = 1. This means O(fib(2)) = 3, O(fib((3)) = 5, O(fib(4)) = 9. As you can see, this series would go up faster than the fibonacci series itself! This means a huge amount of increasing complexity. When you would have an iterative algorithm with a for loop from 0 to n, your complexity would scale in the order of n, which would be way better.

For more information, check out the big-o notation.

MrP
  • 1,291
  • 1
  • 9
  • 18
  • Well. Thank you, could you suggest any link or ref to read about the big o notation? – Dale Steyn Aug 14 '13 at 07:37
  • I found the wiki article. May i know any source for Algorithm design and analysis tech? – Dale Steyn Aug 14 '13 at 07:43
  • 1
    Steven S. Skiena's The Algorithm Design Manual is quite good as well as Introduction to Algorithms by Thomas H. Cormen. They contain information about good algorithm design and performance issues. – MrP Aug 19 '13 at 06:44