Difference between Recursion and Iteration

Recursion Vs Iteration: Comparative Analysis

The Fibonacci numbers are an integer sequence with the first two elements being 0 and 1, and each succeeding element being the sum of the two items before it:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ..., n

Recursion

Code of Fibonacci number in a recursive way

Analysis

The result is a neatly constructed function that checks. We return both the given numbers if the given number is equal to either 0 or 1.

If a number is passed that is bigger than 0 and 1, we perform two recursive calls, adding both calls and subtracting 1 and 2 from the nthNumber in each call.

We will most likely quickly receive --> 0, 1, 1, 2, 3, if we pass these integers (0, 1, 2, 3, 4, and 5).

However, what occurs if we pass greater numbers, such as 50, 67, or 100. In your IDE, try running the function with the supplied numbers. You'll realize that this method takes much longer to calculate our Fibonacci number. Due to the fact that this recursive function has many internal workings because it does repeated computation and this issue we will solve by memorizing the value. Heavy push-pop operations on the stack memory with each recursive call are to blame for the performance issues.

A workaround for this would be to memorize and keep each Fibonacci number that has been calculated in this way. However, I'll move on to the Iteration approach for now and explain why it might speed up the computation of the 100th Fibonacci number.

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Iteration

Code of Fibonacci number in an iterative way

Analysis

Because we are keeping the first two Fibonacci numbers in two variables (previousPreviousNumber, previousNumber) and utilizing "CurrentNumber" to store the third Fibonacci number, the Iteration method would be the preferred and faster approach to solving our problem. By storing these values, we can avoid continuously eating up Stack RAM. giving us an $O(n)$ time complexity.

Comparative Analysis

1. Time Complexity

   Depending on whether the technique is applied via recursion or iteration, the method's time complexity may change.

   Recursion: By calculating the value of the nth recursive call in terms of the prior calls, the time complexity of the recursion can be determined. We may therefore estimate the time complexity of recursive equations by determining the destination case in terms of the base case and solving in terms of the base case.

   Iteration: Finding the number of cycles repeated inside the loop will reveal the iteration's time complexity.

2. Usage

   Both of these methods involve a trade-off between time complexity and code size. Iteration is preferable if time complexity is the main concern and there will be a lot of recursive calls. However, recursion would be the best option if time complexity was not a concern and code length was.

   Recursion: Recursion includes repeatedly calling the same function, which results in relatively little code. However, as we saw in the study, when there are a lot of recursive calls, the time complexity of recursion might become exponential. Recursion is, therefore, helpful in shorter code but more time-consuming.

   Iteration: The repetition of a block of code is known as iteration. Although there is more code involved, it often takes less time than recursion does.

3. Overhead

   Compared to iteration, recursion has a lot more overhead.

   Recursion: Recursion has the overhead of repeated function calls, which means that because the same function is called repeatedly, the code's time complexity multiplies.

   Iteration: There is no such overhead with iteration.

4. Infinite Repetition

   In iteration, repetition will end when memory is used up. However, infinite repetition in recursion can cause a CPU crash.

   Recursion: Recursion can result in infinite recursive calls if the base condition is specified incorrectly and never becomes false, which keeps calling the function and could cause the system's CPU to crash.

   Iteration: An infinite iteration caused by an error in the assignment or increment of the iterator or in the terminating condition will result in infinite loops. These loops may or may not cause system faults, but they will definitely stop further script execution.

Difference between Recursion and Iteration

The key differences between iteration and recursion are listed in the table below: