Recursive Functions in C

 Lecture Notes: Recursive Functions in C

Introduction to Recursive Functions:

Recursive functions are functions that call themselves directly or indirectly to solve a problem by dividing it into smaller instances of the same problem. They are a powerful programming technique used to solve problems that can be broken down into simpler subproblems.

Definition:

A recursive function is a function that calls itself either directly or indirectly during its execution.

Types of Recursive Functions:

1. Direct Recursion: In direct recursion, a function calls itself directly.

   c
   // Example of direct recursion
   void countdown(int n) {
       if (n > 0) {
           printf("%d ", n);
           countdown(n - 1);  // Recursive call
       }
   }
   

2. Indirect Recursion: In indirect recursion, a function calls another function, which in turn calls the first function, creating a cycle of function calls.

   c
   // Example of indirect recursion
   void func1(int n);
   
   void func2(int n) {
       if (n > 0) {
           printf("%d ", n);
           func1(n / 2);  // Recursive call to func1
       }
   }
   
   void func1(int n) {
       if (n > 1) {
           printf("%d ", n);
           func2(n - 1);  // Recursive call to func2
       }
   }
   

Explanation with Examples:

1. Direct Recursion:

   • Factorial Function:

     The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n.

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

     Explanation: The function factorial() calculates the factorial of a number by calling itself with a smaller argument (n - 1) until it reaches the base case (n == 0 or n == 1), at which point it returns 1.

2. Indirect Recursion:

   • Odd and Even Numbers:

     This example demonstrates indirect recursion by printing odd and even numbers in a given range using two mutually recursive functions.

     c
     void printOdd(int n);
     
     void printEven(int n) {
         if (n > 0) {
             printf("%d ", n);
             printOdd(n - 1);  // Recursive call to printOdd
         }
     }
     
     void printOdd(int n) {
         if (n > 0) {
             printf("%d ", n);
             printEven(n - 1);  // Recursive call to printEven
         }
     }
     

     Explanation: The functions printOdd() and printEven() call each other alternatively, printing odd and even numbers respectively until the base case (n == 0) is reached.

   • 


Conclusion:

Recursive functions provide an elegant solution for solving problems that can be divided into smaller subproblems. However, excessive recursion can lead to stack overflow errors, and recursive functions may not always be the most efficient solution. It is essential to understand the principles of recursion and when to use it appropriately in programming.