**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:**

#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); }