C - Recursion

In this tutorial we will learn about recursion in C programming language.

When we call or invoke a function then the flow of control moves from the calling function to the called function. And when all the code statement in the called function is executed the flow of control returns back to the calling function.

If we are calling greetings() function from the main() function then the main function is the calling function and the greetings function is the called function.

This is the general function call. Recursion on the other hand is a special case.

Recursion occurs when a function calls itself.

Note! If no terminating condition is provided then the recursion becomes a never ending function call like an infinite loop.

Recursion with terminating condition

Recursion with terminating condition is a scenario were we have a condition that prevents the function from calling itself.

One of the most common example of recursion is the factorial problem.

So, if we have a number say n then, its factorial is the following:

factorial of n
= n x (n - 1) x (n - 2) x ... x 1

Example: Factorial of 3 is 6

Factorial of 3
= 3 x 2 x 1
= 6

The formula to find the factorial of a number is given below.

F(n) represents the Factorial function to find factorial of n.

F(n) = n x F(n - 1)  if n > 1
     = 1             if n = 1 or 0

In the above formula we are computing the factorial of n by recursively calling function F() and passing the value n - 1 in each call as long as the condition n > 1 is true or valid. When the value of n is 1 or 0 then, F(n) returns 1.

Factorial program

Following is the program written in C to find the factorial of 3.

#include <stdio.h>

int factorial(int);

int main(void) {
  int
    num = 3,
    fact;

  fact = factorial(num);
  
  printf("Factorial of %d is %d\n", num, fact);
  return 0;
}

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

Output:

Factorial of 3 is 6

Exploring recursion

In order to understand the flow the following code has some printf() statements to print out the flow of control.

#include <stdio.h>

int factorial(int);

// this will mark the function
int functionID = 1;

int main(void) {
  int
    num = 3,
    fact;
  
  printf("----------------- Inside main() function ---------------\n");
  
  printf("main(): About to call the factorial() function #%d.\n", functionID);

  fact = factorial(num);
  
  printf("----------------- Back to main() function ---------------\n");
  
  printf("main(): Back from factorial() function #%d. Value returned: %d\n", functionID, fact);
  
  printf("main(): Factorial of %d is %d\n", num, fact);
  return 0;
}

int factorial(int n) {
  int prod;
  
  printf("----------------- Inside factorial() function #%d ---------------\n", functionID);
  
  printf("factorial() #%d: Value of n passed: %d\n", functionID, n);
  
  if (n == 1 || n == 0) {
    printf("factorial() #%d: Inside if-block. Value of n is 1 so, about to return 1 back to factorial function #%d\n", functionID, (functionID - 1));
    return 1;
  }
  else {
    printf("factorial() #%d: Inside else-block. Value of n is %d\n", functionID, n);
    printf("factorial() #%d: About to make a recursive call to factorial() function #%d with value of n = n - 1 i.e., %d\n", functionID, (functionID + 1), (n -  1));
    // increase function id to assign to called function 
    functionID++;
    prod = n * factorial(n - 1);
    // decrease function id to assign to calling function
    functionID--;
    printf("----------------- Back to factorial() function #%d ---------------\n", functionID);
    printf("factorial() #%d: Inside else-block. Value returned from factorial(%d) = %d\n", functionID, (n - 1), prod/n);
    printf("factorial() #%d: Inside else-block. Value stored in prod = n * factorial(n - 1) = %d * factorial(%d) = %d * %d = %d\n", functionID, n, (n- 1), n, prod/n, prod);
  }
  if (functionID == 1) {
    printf("factorial() #%d: About to return the value of prod = %d back to main()\n", functionID, prod);
  } else {
    printf("factorial() #%d: About to return the value of prod = %d back to factorial() function #%d\n", functionID, prod, (functionID - 1));
  }
  return prod;
}

Output:

----------------- Inside main() function ---------------
main(): About to call the factorial() function #1.
----------------- Inside factorial() function #1 ---------------
factorial() #1: Value of n passed: 3
factorial() #1: Inside else-block. Value of n is 3
factorial() #1: About to make a recursive call to factorial() function #2 with value of n = n - 1 i.e., 2
----------------- Inside factorial() function #2 ---------------
factorial() #2: Value of n passed: 2
factorial() #2: Inside else-block. Value of n is 2
factorial() #2: About to make a recursive call to factorial() function #3 with value of n = n - 1 i.e., 1
----------------- Inside factorial() function #3 ---------------
factorial() #3: Value of n passed: 1
factorial() #3: Inside if-block. Value of n is 1 so, about to return 1 back to factorial function #2
----------------- Back to factorial() function #2 ---------------
factorial() #2: Inside else-block. Value returned from factorial(1) = 1
factorial() #2: Inside else-block. Value stored in prod = n * factorial(n - 1) = 2 * factorial(1) = 2 * 1 = 2
factorial() #2: About to return the value of prod = 2 back to factorial() function #1
----------------- Back to factorial() function #1 ---------------
factorial() #1: Inside else-block. Value returned from factorial(2) = 2
factorial() #1: Inside else-block. Value stored in prod = n * factorial(n - 1) = 3 * factorial(2) = 3 * 2 = 6
factorial() #1: About to return the value of prod = 6 back to main()
----------------- Back to main() function ---------------
main(): Back from factorial() function #1. Value returned: 6
main(): Factorial of 3 is 6

Recursion without terminating condition

In this case there will be no terminating condition to stop the function from itself.

In the following example we have a function happy() which keeps calling itself.

#include <stdio.h>

void happy(void);

int main(void) {
  happy();
  return 0;
}

void happy(void) {
  printf("Because I am happy...\n");
  happy();
}

Output:

Because I am happy...
Because I am happy...
Because I am happy...
Because I am happy...
Because I am happy...
Because....

The execution of the program was terminated forcefully by pressing Ctrl + C.