# Introduction to Recursion in C

A function that calls itself is said to be recursive. Recursion allows something to be defined in terms of smaller instances of itself.

While most of us are comfortable with breaking down problems into smaller pieces using functions, data structures, or methods and classes, using one single function to solve a big problem is somewhat more daunting.

```#include <stdio.h>

void simpleRecursion(int num){
if(num > 0){
simpleRecursion(num-2);
printf("%d\t", num);
simpleRecursion(num-1);
}
}

int main(void){

int i;
for(i=0; i < 6; i++){
printf("\nPassed the function %d:\n", i);
simpleRecursion(i);
putchar('\n');
}

return 0;

}```

The simpleRecursion() function only prints output if the parameter is greater than zero, meaning that any value printed must be one or greater.

Our second example is simpler still, it in effect goes backward one by one. We will use it to print the ASCII table backwards.

```#include <stdio.h>

void simpleRecursion2(int num){
if(num < 127){
printf("%2c", num);
}
if(num > 33){
simpleRecursion2(num - 1);
}
}

int main(void){

//print ASCII characters backward
simpleRecursion2(127);

return 0;

}```

Factorials are a common mathematical example of recursion. The factorial of a number n, written n!, is the product of all numbers from n to 1. While we could follow an iterative approach, we can also define n! as itself being the product of smaller factorials. In this case, n! = (n-1)!, with n(0)=1. In this case, n(0) = 1 is what is known as the terminating condition. This is the point at which the function returns a value rather than calling itself again.

```#include <stdio.h>

int factorial(int n){

if(n>1){
//return a call to the same function
return n*factorial(n-1);
}

//terminating conditions
if((n==0)||(n==1)){
return 1;
}

//error
return 0;
}

int main(void){

printf("%d! = %d\n", 5, factorial(5));
printf("%d! = %d\n", 3, factorial(3));

return 0;

}```

Remember, every recursive function must have at least one terminating condition.

To understand recursion, it helps to have a rough idea of the way functions are executed in C. When a function is called, a block of storage is allocated on the stack to keep track of data associated with the call. This block of storage is called a stack frame. The stack frame remains on the stack until the function call terminates.

This next example will sum an integer with every positive integer below it.

```#include <stdio.h>

printf("%d", n);

if(n>1){
printf(" + ");
}

if(n==1){
return n;
}
//error
return 0;
}

int main(void){

int i = 0;

while(i++ <= 10){