## Introduction

Lateral thinking is one of those ‘good’ skills to have by any person. If we have it, then its god’s gift, if don’t then we try to achieve it through practice. Lateral thinking is about concepts and ideas that may not be obtainable by using only traditional step-by-step logic. Hence, they are bit difficult. Remember I said bit! So, beginners should not feel disheartened at all. After all, the attempt of this article is to shift ‘Recursion’ from the lateral thinking track to little simpler platform. At the end of this article you are able to deduce a generic way to approach all kinds of recursion problems.

## So, what is recursion?

In my view we should understand recursion with two perspectives

1. Conceptual – Helps in coming up with general technique that can be applied in varied situations.

2. Implementation – A real life examples that helps in writing code from the abstract (conceptual) solution.

## Recursion Concepts

Recursion is a way of thinking about and solving a problem. Suppose we have a problem statement of solving a factorial of a given number n. Once, we have a problem we have to find a solution, between that we ‘think’ using our knowledge, mind and experiences. Hence, ‘recursion’ is one of the way of thinking (approaching) a given problem. We can approach for solving a factorial problem in at least in two standard ways:-

- Iterative/standard thinking

4! = 1*2*3*4 or 4*3*2*1 = 24

4! = 4 * 3!

= 4 * (3*2!)

= 4 * (3*(2*1!))

= 4 * (3*(2*(1)))

= 24

Obviously, the second approach is more complex to think as compared to first one. The second solution is called ‘Recursion’. Thinking the solution of the problem in this way is termed as ‘recursive thinking’. In this method of simplification we use ‘Divide and Conquer’ technique. *We try to divide a problem (main problem) into sub-problems of the same type.* Remember our factorial example. Problem of finding factorial of n can be formulated in recursive way as follows:-

Main problem = fact(n)

=(Preprocessing)(Sub problem of same type but for simpler case)(Post Processing)

= n times fact(n-1) (~~Postprocessing~~)

= n times fact(n-1)

= n * fact(n–1)

Now we are going to understand the gist of the above concept. There are same two steps we have to perform in designing any recursive solution.

1. **Define what could be the base case(s) of this recursive solution**. Examples:-

1.1. Base case for factorial problem is:-

fact(n) = 1 , if n =0.

1.2. Base case for fibonnaci problem is:-

fibonnaci(n) = 0 ,if n=0

fibonnaci(n) = 1 ,if n=1

1.3. Base case for palindrome problem is:-

IsPalindrome(string) = true ,if Length(string) = 1

2. **Think and formulate the recursive case of this problem**. Recursive case designing needs to perform three tasks as given below:-

2.1. **Divide the problem into one or more simpler parts of the main problem**. End result of this exercise usually comes out to a mathematical formula expressed in form of a function:

Figure 1

Where, n1 = Current input to recursive function

n2 = Reduced or simpler input passed in next recursive call

g() = Some pre/post processing operations need to applied to get f(n1) value from reduced case f(n2).But g() is optional. Examples:-

2.1.1. Problem of calculating factorial can be divided into sub problem of same types as:-

fact(n) = n * fact(n-1), where n > 0

2.1.2. Problem of calculating nth term of fibonnaci series is done as:-

fib(n) = fib(n-1) + fib(n-2)

2.1.3. Problem of checking that any given string is a palindrome or not can be reduced to checking its substring is a Palindrome or not. Substring is obtained from original string by removing first and last characters of the string. Provided before removing first and last character we have checked that the first and last characters are equal.

Figure 2

2.2. **Call the function (recursively) on each sub divided parts**.

Figure 3

2.3. **Combine the solutions of the parts into a solution of the problem**.

This points need explanation for sure. First of all this step is not necessary in every recursive solution. We all know from step (a) given above that to create a recursive case we have to divide the main problem into sub problem of same type before giving a recursive call. What ever be the type of recursion every recursion should divide the problem in such a way that it should approach a base case in finite number of steps. But ultimately purpose of the whole exercise is to get our end result. So, depending upon when we get our end result in a recursive function we have two types of recursive functions.

1. Tail recursive

2. Augmenting recursive

## Tail Recursive functions

First we have to understand that what a ‘tail call’ is. Let’s understand by example.

Figure 4

So, Tail recursive functions are those whose tail call gives call to same function. For example, in the code below we see two tail operations and in the one of the tail call, we see that tail call foo(a-1), gives call to the same function foo. Hence, this is known as tail recursive function.

Figure 5

Other characteristics of the tail recursive function are as given below:-

1. Tail Recursive function in general looks as follows:-

foo(n1)
{
…
//No operation need to be done after returning from foo(n2)
Return foo(n2);
…
}

2. If the ‘Tail Recursion Optimization’ is done in high level language compiler then end result from the last recursive call is directly returned to the external calling function that had called the Tail recursive function first time outside its function body. Usually, for each function call ‘stack’ space is allocated to store parameters and local variables. Stack space of the function is reserved till the return statement is executed for that function. As we know that in recursive calls, function is not able to execute its return statement since a recursive call is present before the return statement of the function and this is done till the base case is reached. Hence, for each call runtime has to reserve a stack space one after the other till base case is reached. So in tail recursion optimization stack is not kept reserved in the subsequent calls, only it is reserved for the current executing call and then deallocated on next recursive call without waiting for current function return statement to execute.

3. There are no pending operations to be performed on return from a recursive call.

Tail recursive functions are often said to "return the value of the last recursive call as the value of the function. Some modern computing systems will actually compute tail-recursive functions using an iterative process.

## Augmenting recursive functions

There are some functions that keep on simplifying problems till they end up to the base case and then actually start building end result when they are returning back from the base case. These types of functions are called ‘Augmenting-Recursive’ functions. Let’s better understand it by examples.

Palindrome, Greatest Common Divisor (GCD) and Fibonnaci problems are implemented as ‘Tail-Recursive’ functions as there is no operation is left pending at each return call. While factorial calculation is ‘Augmenting Recursive’ function as the result actually start building when the function actually returns back from the base case (last recursive call). In fact, ‘Augmentative recursive’ functions are those when we have some function g() which does some post/preprocessing on ‘recursive case’ f(n2). When g() does not exits, then those functions are ‘Tail – recursive’. Usually we find that there are more ‘Tail – recursive’ cases then ‘Augmenting recursive’ cases.

Tail Recursion example. Recursive case for Greatest common divisor problem is:-

Program given below:-

First call = gcd( 24 , 6)

Second call = gcd(6, 24 % 6)

Third call = 6

Figure 6

Augmenting Recursion example. Recursive case for factorial problem is:-

Figure 7

Let’s calculate the factorial of 4. It is denoted as 4!

First call = 4 * fact(3)

Second Call =4 * 3 * fact(2)

Third Call =4 * 3 * 2 * fact(1)

Fourth Call =4 * 3 * 2 * 1 * fact(0)

Fifth Call =4 * 3 * 2 * 1 * 1 [1st return from Fifth Call (1*1) ]

=4 * 3 * 2 * 1 [2nd return from Fourth Call (2*1)]

=4 * 3 * 2 [3rd return from Third Call (3*2)]

=4 * 6 [4th return from Second Call (4 * 6)]

=24 [5th return (last return) from First call]

Given below is the illustration that gives comparative analysis of three recursive problems (factorial, fibonnaci, palindrome) and helps in identifying general pattern used in designing all types of recursion problem.

Figure 8( To view larger image, please download the attached 'Recurson Generic Steps.zip' file)

## Types of recursion

A recursive function is said to be tail recursive if there are no pending operations to be performed on return from a recursive call. Greatest Common Divisor GCD problem is a‘Tail recursion’ example.

int GCD(int ,int y)
{
if(y == 0)
return x;
else
return GCD(y, x % y);
}

Whenever there is a pending operation to be performed on return from each recursive call, then recursion is known as Augmenting recursion. The "infamous" factorial function fact is usually written in a non-tail-recursive manner:

int fact (int n)
{
if (n == 0) return 1;
return n * fact(n - 1);
}

A function is directly recursive if it contains an explicit call to itself.

int foo(int x)
{
if (x <= 0) return x;
return foo(x - 1);
}

A function foo is indirectly recursive if it contains a call to another function which ultimately calls foo.

int foo(int x)
{
if (x <= 0) return x;
return foo1(x);
}
int foo1(int y)
{
return foo(y - 1);
}

When the pair of functions contains call to each other then they are said to perform mutual recursion.

int foo(int x)
{
if (x <= 0) return x;
return foo1(x);
}
int foo1(int y) {
return foo(y - 1);
}

A recursive function is said to be linearly recursive when no pending operation involves another recursive call to the function.

For example, the "infamous" fact function is linearly recursive. The pending operation is simply multiplication by a scalar, it does not involve another call to fact

- Tree or Non-Linear Recursion

A recursive function is said to be tree recursive (or non-linearly recursive) when the pending operation does involve another recursive call to the function.

The Fibonacci function fib provides a classic example of tree recursion.

Notice that the pending operation for the recursive call is another call to fib. Therefore fib is tree-recursive.

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

Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms. This term refers to the fact that the recursive procedures are acting on data that is defined recursively. Example XML files Parser, Linked List and Binary Trees. Following example shows Structural recursion example in which underlying problem is to read XML data file that has recursive data structure, hence structural recursion is used to parse that XML file.

XML File

Figure 9

Figure 10

## Order of recursion

Order if recursion only matters when the recursive call is not the ‘Tail’ call of the function. If the recursive call is associated with the return statement of the function then all the operations should be present before the return statement. But if the recursive call statement is not associated with the return statement and the return statement is defined after the recursive call then, order of the statements below and after the recursive call effects the execution of the recursive function,

Figure 11

## Recursion versus Iteration

- When to choose recursion against iteration

1. When the problem is complex and can be expressed in more simplified form as recursive case then its iterative counter part. In the "factorial" example the iterative implementation is likely to be slightly faster in practice than the recursive one.

2. When the solution of the problem is inherently recursive. Like Structural recursion (Tree traversal) and Quick Sort.

- When to choose iterative solution against recursive solution

1. When the problem is simple.

2. When the solution of the problem is not inherently recursive. Main problem can not be expressed easily into sub problem of same type.

3. Another possible reason for choosing an iterative rather than a recursive algorithm is that in today's programming languages, the stack space available to a thread is often much less than the space available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms.

## The principle of practicality

Not all problems that have a recursive solution should necessarily be solved recursively. In fact, many problems can have both a recursive and a non-recursive solution. When deciding which solution to use, you must keep in mind not only the degree of difficulty of the resulting algorithm, but also the programming code necessary to implement it.

The figure below graphically illustrates this principle.

Figure 12 Problem to Solution difficulty curve

It applies only to problems that can be solved recursively. As the problem becomes more difficult, the difficulty and CPU usage of the non-recursive solution begin to increase. On the other hand, the difficulty and CPU usage of the recursive solution -- simulated or otherwise -- begins to flatten. Notice that for very simple problems, the non-recursive approach is usually better.

## Recursion in action

Here I’m trying to give some real life usages of recursion in computer science field.

- Quick Sort
- Merge Sort
- All N-Log Sort
- Tree traversals
- XML Parsers
- HTML Parsers
- Backtracking Algorithm
- Binary Space Partitioning (BSP) Trees used for collision detection in game development.
- Recursive-descent language parsers
- Simulating state machines
- Lists (Linked Lists)
- Graphs
- Inductive reasoning used in AI
- Fractals

## Sample programs

For beginner’s perspective, I have tried to write solutions in C#.NET of common recursive problems. Please find the source code and the executables as attachment.