Recursion is a programming technique where a function calls itself to solve a problem. It works by breaking down the problem into smaller, similar subproblems that can be solved using the same function. This approach is particularly useful for problems that have a natural self-similar structure.

The Key Ingredients: Base Cases and Self-Similarity

For recursion to work effectively, there are two crucial elements:

Base Case: This is a simple condition that stops the self-calls and provides the final answer. It acts as the stopping point, preventing an infinite loop. Self-Similarity: The problem can be broken down into smaller versions of itself, each solved by the same function. This allows the function to "recursively" call itself on the smaller subproblems.

For example, suppose we need to add up all of the numbers in an array. We'll write a function called add_array that takes as arguments an array of numbers and a count of how many of the numbers in the array we would like to add; it will return the sum of that many numbers.

If we had a function that would add up all but the very last number in the array, then we would simply have to add the last number to that sum and we would be done. Add_array is an ideal function for adding up all but the last number (as long as the array contains at least one number). After all, add_array is responsible for taking an array and a count, and adding up that many array elements. If there are no numbers in the array, then zero is the desired answer. These observations suggest the following function:

int add_array(int arr[], int count) {
          
             if (count == 0) return 0;
             return arr[count - 1] + add_array(arr, count - 1);
          }
          

This function is perfectly legal C, and it operates correctly. Notice that the function has two components:

• a base case, represented by the if and the return 0, in which the function does not call itself. This handles the case where there are no numbers to add.
• a recursive case that breaks the problem down into a smaller version of the original problem together with an addition. In the recursive case, add_array is used to add together count-1 items; the count-th item is then added to this result (remember that the n-th item of an array is stored at position n-1).

The call to add_array from inside add_array is called a recursive call.

Example: The Factorial Function

One of the classic examples of recursion is the factorial function. Although factorial is not the world's most interesting function, it will provide us with many useful observations.

Recall that factorial, which is written n!, has the following definition:

n! = 1 * 2 * 3 * .... * (n-2) * (n-1) * n

Iterative Approach (Simpler but Uses Loops):

The first approach uses a loop (for) to multiply all numbers from 1 to n. Here's the code:

int fact(int n) {
             int i;
             int result;
            
             result = 1;
             for (i = 1; i <= n; i++) {
                result = result * i;
             }
             return result;
          }
          

This function uses two local variables: i as a loop counter and result to accumulate the product. It iterates from 1 to n, multiplying result with the current number i in each step. Finally, it returns the accumulated product.

Recursive Approach (Concise but Uses More Memory):

The second approach utilizes recursion, where a function calls itself. The definition of factorial itself is used as a base

Here's the code:

int fact(int n) {
          
             if (n == 1) return 1;
          
              return n * fact(n - 1);
          }
          

This function has a base case: if n is 1, it simply returns 1. Otherwise, it uses the recursive case: n! is calculated as n multiplied by the factorial of n-1 (achieved by another call to fact). This process continues recursively until the base case is reached.

Notice that this function precisely follows our new definition of factorial. It is recursive, because it contains a call to itself. Let's compare the two versions:

• Local Variables : Iterative uses two, while recursive uses none (arguments act as temporary storage).
• Statements: Iterative has three (initialization, loop condition, update), while recursive has one (conditional return).
• Calculation: Iterative accumulates the product in a loop, while recursive calculates and returns the result in a single expression.
• Efficiency: Iterative might be slightly faster due to less function call overhead. Recursive code can be more concise and easier to understand for some problems with self-similar structures.

While recursion can be a powerful tool for solving problems with a self-similar structure, it's important to consider its trade-offs. Recursive solutions can sometimes be more concise and easier to understand than non-recursive approaches (like using loops). However, recursion can also use more memory due to the function call overhead. The choice between recursion and other methods depends on the specific problem and your programming preferences.

By understanding recursion, you'll gain a valuable technique for breaking down complex problems into smaller, manageable pieces. It might seem like a mind-bender at first, but with practice, you'll be a master of self-referential functions in no time!