What is a recursive Algorithm?

An algorithm that calls itself with smaller and smaller subsets of the original input, doing a little bit or work each time, until it reaches the base case.

Example of a recursion algorithm used in the real life

  • Compilers (Parsers)
  • Some sort algorithms like quicksort (there are also iterative versions!)

Why use recursion?

So why use recursion? The answer to our question is predominantly because it is easier to code a recursive solution once one is able to identify that solution. The recursive code is usually smaller, more concise, more elegant, possibly even easier to understand, though that depends on ones thinking style. But also, there are some problems that are very difficult to solve without recursion. Those problems that require backtracking such as searching a maze for a path to an exit or tree based operations (which we will see in semester 2) are best solved recursively. There are also some interesting sorting algorithms that use recursion.
Note: quicksort is very fast and usually implemented with recursion.

Good description of various kinds of recursive algorithms:

  • Recursive Factorial Algorithm
  • Recursive Palindrome Algorithm
  • Recursive Ackermann's Algorithm
  • Fibonacci Numbers
  • Recursive Searching and Sorting

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License