Thinking in a Recursive Way: Unleashing the Power of Recursive Programming

What is Recursion in Programming?

Recursion is a programming concept where a function calls itself to solve a problem. It's like a problem-solving strategy where you break a big problem into smaller, similar problems until you reach a simple problem that's easy to solve directly.

Before diving into recursion, it's helpful to be familiar with some key terms and concepts in computer science and programming.

Functions are "self-contained" modules of code that accomplish a specific task. Functions usually "take in" data, process it, and "return" a result. Once a function is written, it can be used over and over and over again.

Function calls are typically managed using a data structure called the "call stack." The call stack keeps track of the order of function calls and their local variables. When one function calls another, the calling function is paused, and the called function starts running. The call stack ensures that when the called function finishes, the calling function can resume from where it left off.

#include<stdio.h>
int multiply(int a,int b)
{
    return a*b;
}
int square(int n)
{
    return multiply(n,n);
}
int printSquare(int n)
{
    int squared = square(n);
    printf("%d",squared);
}
int main()
{
    printSquare(4);
    return 0;
}

"In the scenario depicted above, the program starts by invoking the 'main' function, pushing it onto the initially empty stack. Within the 'main' function, a call to 'printSquare(4)' is made, adding 'printSquare(4)' to the top of the stack on top of 'main'. Subsequently, 'printSquare(4)' calls the 'square(4)' function, passing '4' as the value of the function parameter 'n', and this call is placed on top of 'printSquare(4)' on the stack.

Inside the 'multiply(4, 4)' function, a calculation is performed, resulting in a return value of '16.' This return value is then passed back to the calling function, which can be seen as returning '16' to the next function on the stack. After this return, 'multiply(4, 4)' is removed from the stack.

The 'square(4)' function receives the returned value precisely where it is called 'multiply(4, 4)' in this example, right after the 'return' keyword in 'square(4)'. 'square(4)' then proceeds to return the value '16' to the 'printSquare(4)' function. This return is made because 'printSquare(4)' had called 'square(4)'. After returning, 'printSquare(4)' is also removed from the stack.

With the returned value of '16', 'printSquare(4)' stores this value in a variable named 'squared'. Subsequently, 'console.log(squared)/printf("%d",&squared)' is executed to print the value '16' on the terminal or console. After this step, 'printSquare(4)' is removed from the stack as it has reached the end of the function. The program can then continue with any additional tasks in the 'main' function or beyond."

Let's Drive into Recursion

#include<stdio.h>
int sum(int n)
{
    if(n==0)
        return 0;
    return n + sum(n-1);
}
int main()
{
    int result = sum(10);
    printf("%d",result);
    return 0;
}

How would you solve it recursively?

Recursion is all about taking a problem and solving it using a simpler version of the problem.

To solve a recursive problem ask yourself

1. What is the simplest possible input?

   The simplest case is also called the "Base case". Base Case: The base case of a recursive function is the only input when we provide the explicit answer. All other solutions to the problem we'll build on the base case.

   Here, the minimum non-negative number is 0 and the sum of it is also 0. So, it'll be the base case for this problem.

2. Play with examples and Visualize the function call.

   

3. Relate Hard Case to Simpler Case
   One interesting relationship to note is that if you already know the answer for the n=4 case, you can simply add 5 to it to find the answer for the n=5 case. Similarly, if you know the answer for the n=3 case, you can obtain the answer for the n=4 case by adding 4 to it.

4. Generalize the pattern

   We can see that if we want to find the sum of n integers value, we first need to find the sum of n-1 integers value and then add it with n.

5. Write code by combining the recursive pattern with the base case.

$$sum(n) = \begin{cases} 0, &\text{if $n$ =0} \ n+sum(n-1) \end{cases}$$

int sum(int n)
{
    if(n==0)
        return 0;
    return n + sum(n-1);
}