Simplified Recursion

Recursion is nothing more than a function calling itself directly or indirectly.Any function that is implemented using iteration i.e. with a while loop, for loop can be implemented using recursion.So, why recursion? It simplifies code and maybe increase running time.
Downside is that sometimes iterative implementation gives better running time and forging a reclusive solution needs to get your head around the concept.

Iteration to recursion transition:

Before transitioning into recursion, let see how a solution is implemented using iteration: Consider a function which computes factorial of a given number, implemented using iteration.

#import <stdio.h>
#import <stdlib.h>
int factorial(int number)
{
     if(number == 0) return 0;
     else{
     int result = 1;
     for(int i=1;i<=number;i++)
     {
         result = result * i;
     }
     return result;
 }
}
int main (int argc, char * const argv[])
{
    printf("%d\n", factorial(5));
    return 0;
}

Breaking down the problem:

Factorial can be further broken down,with these 2 rules.
1.It can compute just one value of the factorial and pass the rest of the computation to the delegate, provided the problem is smaller than the original.
2.Dispatching function has to handle the trivial condition.
#import <stdio.h>
#import <stdlib.h>
int delegateFactorial(int number)
{
    int result =1;
    for(int i=1;i<=number;i++)
    {
        result = result *i;
    }
    return result;
}
int factorial(int number)
{
    int factorialOfOneNumber = number;
    if(number == 1) return 1;
    int factorialOfTheRestOfNumbers = delegateFactorial(number-1);
    return factorialOfOneNumber * factorialOfTheRestOfNumbers;
 }

int main (int argc, char * const argv[])
{
    printf("%d\n", factorial(5));
    return 0;
}

Recursion transition:

With all the rules in place and the problem broken down into a dispatcher and delegate, here the dispatcher is not concerned about the ‘how’ of the solution, but the ‘what’. The problem is progressively broken down, with the operation summing up the result until the trivial case is handled.

#import <stdio.h>
#import <stdlib.h>
int delegateFactorial(int number)
{
    int result =1;
    for(int i=1;i<=number;i++)
    {
        result = result *i;
    }
    return result;
}
int factorial(int number)
{
    int factorialOfOneNumber = number;
    if(number == 1) return 1;
    int factorialOfTheRestOfNumbers = factorial(number-1);
    return factorialOfOneNumber * factorialOfTheRestOfNumbers;
 }

int main (int argc, char * const argv[])
{
    printf("%d\n", factorial(5));
    return 0;
}

 Where to place the Recursive call?

Before checking the details of when to make a recursive call, let summarize the components of a Recursive method.

1.Trivial condition

2.Recursive call

3.Operation to perform

With just three simple components recursive method call is easy to understand. But using step2 before the operation of the method or after the operation can make all the difference.

Head Recursion, is placing a recursive call before the operation and usually used to maintain a running total throughout the length of the loop.

Tail Recursion, is placing the recursive call after the operation is performed.

To familiarize, lets see a classic example for both, head and tail recursion. Printing the contents of a linked list.

Tail recursion prints the data in increasing order, staring from the node pointed by ‘HEAD’.

Head recursion prints the data in reverse order.

Tail recursion:

//structure to build a linked list with nodes
typedef struct Node Node;
struct Node
{
	int data;
	Node *nextNode;
};
Node *head;

void printLinkedList(Node *head)
{
//trivial condition
if(head->nextNode == NULL) return;
//operation
printf("%d\n",head->data);
//tail recursion
printLinkedList(head->nextNode);
}

Head recursion:

//structure to build a linked list with nodes
typedef struct Node Node;
struct Node
{
	int data;
	Node *nextNode;
};
Node *head;

void printLinkedList(Node *head)
{
//trivial condition
if(head->nextNode == NULL) return;
//head recursion
printLinkedList(head->nextNode);
//operation
printf("%d\n",head->data);
}

Leave a Reply

Your email address will not be published. Required fields are marked *