What is Recursion? Recursion vs Iteration and Advatages and Disadvantages of using Recursion. written by Nischal Lal Shrestha.
Image of Nischal who is author of the post.

By Nischal Lal Shrestha

On Tue 22 May 2018

What is Recursion? Recursion vs Iteration and Advatages and Disadvantages of using Recursion.

  • What is Recursion? - Introduction to Recursion.
  • Three Rules of Recursion.
  • Why Recursion? - Advatages of using Recursion.
  • Why not Recursion? - Disadvantages of using Recursion.
  • Algorithms using Recursion.
  • Recursion vs Iteration - Differences between Recursion and Iteration.

What is Recursion?

A Recursion is a method of solving a problem, that involves a function which calls itself to solve a smaller version of the problem until you get a small problem that can be solved trivially.

A recursive function call itselfs, If a function just kept calling itself it would never finish unitl it fills the computer's run-time stack. So it is very important to ensure that the recursion terminates.

Three Rules of Recursion

While designing a recursive function, it is very important to follow the following three rules.

  1. A Recursive Function must have a base case. The base case is an if-statement that handles a very simple version of your problem by returning a value.
  2. A recursive algorithm must change its state and move toward the base case.
  3. A recursive algorithm must call itself, recursively.

Why Recursion?

Recursion is a useful technique borrowed from mathematics. Recursive code is generally shorter and easier to write than iterative code. Generally, loops are turned into recursive functions when they are compiled or interpreted.

Some advantages of recursion are:

  1. Recursive solutions often tend to be shorter and simpler than non-recursive ones.
  2. Performs better in solving problems based on tree structures
  3. Code is clearer and easier to use.
  4. Recursion works similar to the original formula to solve a problem.
  5. Tower of Hanoi Problem can be solved more effectively using recursion.
  6. Recursion follows a divide and conquer technique to solve problems.
  7. For some problems, there are no obvious iterative algorithms.
  8. Any problem that can be solved recursively can also be solved iteratively.

Why not Recursion?

Recursion is not advocated when the problem can be through iteration. Recursion may be treated as a software tool to be applied carefully and selectively. If proper precautions are not taken, recursion may result in non-terminating iterations.

Some disadvantages of Recursion are:

  1. According to some computer professionals, recursion does not offer any concrete advantage over non-recursive procedures/functions.
  2. For some programmers and readers, recursion is a difficult concept.
  3. Recursion is implemented using system stack. If the stack space on the system is limited, recursion to a deeper level will be difficult to implement.
  4. Aborting a recursive program in midstream can be a very slow process.
  5. Using a recursive function takes more memory and time to execute as compared to its non- recursive counterpart.
  6. It is difficult to find bugs, particularly while using global variables.
  7. If proper precautions are not taken, recursion may result in non-terminating iterations.

Algorithms Using Recursion

  1. Fibonacci Series
  2. Factorial Finding
  3. Merge Sort
  4. Quick Sort
  5. Binary Search
  6. Tree Traversals and many Tree Problems: InOrder, PreOrder PostOrder
  7. Graph Traversals: DFS [Depth First Search] and BFS [Breadth First Search]
  8. Dynamic Programming Examples
  9. Divide and Conquer Algorithms
  10. Towers of Hanoi

Recursion vs Iteration

The main difference between recursion and iteration is that Recursion is the technique of defining anything in terms of itself while Iteration is a process of executing a statement or a set of statements repeatedly.

You can check full difference between them in Recursion vs Iteration

Comments