C - IntroductionC - Hello World ProgramC - Exercise 1C - Basic structure of a C programC - TokensC - Data TypesC - Type ConversionC - Exercise 2C - Character Input Output OperationsC - Input Output operation using scanf and printf functions

Operators

C - Arithmetic OperatorsC - Relational OperatorsC - Logical OperatorsC - Assignment OperatorsC - Increment Decrement OperatorsC - Bitwise Operators

Precedence and Associativity

C - Precedence and AssociativityC - Exercise 3

Conditions

C - If Else decision making statementsC - Switch Case decision making statements

Loop

C - While LoopC - Do While LoopC - For LoopC - Exercise 4

Array

C - ArraysC - Two Dimensional ArraysC - Multi Dimensional ArraysC - Exercise 5

String

C - StringC - Exercise 6C - String Manipulation

Functions

C - FunctionsC - Functions CategoryC - Function Call - Flow of ControlC - RecursionC - Functions and ArraysC - Functions and Strings

Structures

C - StructuresC - Structures and ArraysC - Passing structure to functionC - Function returning structureC - Structure in Structure

Pointers

C - PointersC - Pointers and VariablesC - Pointers and Variables Memory RepresentationC - Pointers Chaining

Pointers and Arrays

C - Pointers and One Dimensional ArrayC - Pointers and Two Dimensional ArrayC - Array of Pointers

Pointers and Strings

C - Pointers and Strings

Pointers and Functions

C - Pointers and Functions - Call by Value and Call by ReferenceC - Function returning pointer

Pointers and Structures

C - Pointers and StructuresC - Pointers and Array of StructuresC - Passing structure pointer to function

Handling Files

C - File Handling - Getting StartedC - File Handling - Read and Write CharactersC - File Handling - Read and Write IntegersC - File Handling - Read and Write multiple dataC - File Handling - Randomly Access Files

Command Line Arguments

C - Command Line Arguments

Dynamic Memory Allocation

C - Dynamic Memory Allocation - Getting StartedC - Dynamic Memory Allocation - malloc functionC - Dynamic Memory Allocation - calloc functionC - Dynamic Memory Allocation - realloc function

C - Recursion

C Programming

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.