Recursion – The basics

Recursion – The basics

 

COMPUT: a programming technique where a routine performs its task by delegating part of it to another instance of itself.

Introduction
For new computer science students, the concept of recursive programming is often difficult. Recursive thinking is difficult because it almost seems like circular reasoning. It’s also not an intuitive process; when we give instructions to other people, we rarely direct them recursively.

For those of you who are new to computer programming, here’s a simple definition of recursion: Recursion occurs when a function calls itself directly or indirectly.

A classic example of recursion
The classic example of recursive programming involves computing factorials. In mathematics, the factorial of a nonnegative integer, n (denoted n!) is the product of all positive integers less than or equal to n. For example, 5! is the same as 5*4*3*2*1, and 3! is 3*2*1.

An interesting property of a factorial is that the factorial of a number is equal to the starting number multiplied by the factorial of the number immediately below it. For example, 5! is the same as 5 * 4! You could almost write the factorial function as:

int factorial(int n)
{
   return n * factorial(n - 1);
}

Listing 1. First cut factorial function

However, there is a small problem with this; it will run forever because there is no place where it stops calling itself. It therefore needs a condition to tell it to stop. Since a factorial is for positive numbers only it makes sense to stop the recursion when the input is 1 and return 1 as the result. The modified code will look like this:

int factorial(int n)
{
   if(n == 1)
   {
      return 1;
   }
   else
   {
      return n * factorial(n - 1);
   }
}

Listing 2. better factorial function

As you can see, as long as the initial value is above zero, this function will terminate. Note that more work will need to be done to guard again invalid initial values.

The point at with the recursion is stopped is called the base case. A base case is the bottom point of a recursive program where the operation is so trivial as to be able to return an answer directly. In the case of a factorial 1! = 1. All recursive programs must have at least one base case and must guarantee that they will hit one eventually; otherwise the program would run forever or until the program ran out of memory or stack space.

recursion

Basic steps of recursive programs
All recursive programs follows the same basic sequence of steps:
1: Initialize the algorithm. Recursive programs often need a seed value to start with.
2: Check to see whether the current value(s) being processed match the base case. If so, process and return the value.
3: Redefine the answer in terms of a smaller or simpler sub-problem or sub-problems.
4: Run the algorithm on the sub-problem.
5: Combine the results in the formulation of the answer.
6: Return the results.

 

Advantages and drawbacks of recursion

Main advantage of recursion is programming simplicity. When using recursion, programmer can forget for a while of the whole problem and concentrate on the solution of a current case. Then, returning back to the whole problem, base cases (it’s possible to have more than one base case) and entry point for recursion are developed.

On the other hand, recursion has a serious disadvantage of using large amount of memory. Moreover, for most programming languages, recursion use stack to store states of all currently active recursive calls. The size of a stack may be quite large, but limited. Therefore too deep recursion can result in Stack Overflow. To resolve this problem recursion can be simulated, using loop and stack data structure.