Recursion is an important programming concept that can come handy in several use cases. Recursion has many uses in various scenarios. It is used in sorting algorithms, also to find the nth Fibonacci number and to find factorial of a number, etc.
Today let’s focus on a fairly easy and straightforward application of recursion, a C program to print even numbers using recursion. For this example, let’s consider even numbers in the inclusive range from 1 to 10. Once you get the basic idea behind it, you’ll be able to find odd numbers in a range using recursion yourself!
HINT: An Inclusive Range is a range in which the lower and upper limits are also included in the range.
If you are new to C, I suggest you first look at this article by me to get some understanding of the language.
What are we going to learn today?
- Write a C program to print even numbers in the inclusive range from 1 to 10 using recursion.
- How to decide between Recursive vs Iterative approaches?
- Understanding the flow diagram of our “finding even numbers” problem.
- What if we don’t define a “Base Case”?
Source code for today’s lesson
#include <stdio.h>
int printEven(int num); //function prototype
int main() {
printf("\nFinal return value from function is : %d\n", printEven(2)); //normal function call
return 0;
}
int printEven(int num){ //function definition
printf("%d\n", num);
if (num == 10) { //base case
return num;
}
else{ //recursive case
return printEven(num + 2); //recursive function call
}
}
Output
Source code explanation
Line 3 is the function prototype for our user-defined recursive function printEven().
Line 6 contains the call to the recursive function. The numerical argument 2 is sent to the function during this call.
Lines 10 to 18 contains the function definition of our recursive function. It has an integer parameter num.
Because of line 11, whenever this function is called, the current value of the parameter num is printed to the console.
Lines 12 to 14 is the Base Case of our recursive function. The base case is the branch of the recursive function that occurs when the recursive function is just about to terminate.
In our base case condition, the program checks whether the value of the variable num is equal to 10, and if it is, the base case condition is satisfied. Then the program executes line 13, to return the current value of num, to the caller of the function. This caller is the line 6 in our main function.
Lines 15 to 17 is the Recursive Case of our recursive function. The recursive case is the branch of the recursive function that executes repeatedly until the base case condition is satisfied.
If the program fails the base case condition, it executes line 16. This line is our recursive function call. Unlike the normal function call on line 6, this recursive function call is taking place from that same function. Therefore, we can think of this as a spiraling loop.
How to decide between Recursive vs Iterative approaches?
Many problems can be solved using either loops (iterative approach) or recursion (recursive approach). But the programmer should wisely choose between the two.
According to this question, we can decide it’s better to use recursion to solve a problem when,
- Recursive approach is much simpler than the Iterative approach.
- Depth of recursion doesn’t cause a memory stack overflow.
An important step when deciding whether a particular problem can be solved using recursion is to identify the Base Case and the Recursive Case. If these two can be properly identified, the implementation of recursion becomes quite straightforward.
For example, in our program,
- Base Case is when the value of num is 10.
- Recursive Case is when the value of num is not 10.
Flow diagram of our even number problem
In order to understand how I wrote the source code mentioned above, let’s visualize our logic graphically.
Unlike traditional loops where each iteration performs a task until a condition becomes false, in some recursion applications like finding the factorial of a number, the execution does not happen until finally meet a base case.
But our program outputs, even without a base case since it just directly prints the current value of num every time the function is called, rather than waiting for return values to print. But, it will only run until the memory stack overflows.
Think of recursion as climbing a large, spiraling staircase. First, you have to climb down to the bottom. Then you have to climb up while carrying a bag up step by step. This bag that you carry is the return value of each recursive function call.
Sometimes (for example when calculating factorials using recursion) you change what’s inside the bag, in each step, when going upwards. But in some other times (like in our even number example), the final return value is the same as the return value of the innermost recursive call.
The recursive calls nest downwards until meeting the base case of the innermost recursive call. Then, the return value from that call goes to the call outer to that. This process repeats upwards until meeting the initial recursive function call.
Then the recursive function terminates, and return the value to the caller which called the function normally. (With the initial argument).
To summarise, let’s go a little crazy and explain our whole program with one sentence.
The printEven(2) returns the return value of printEven(4) which is the return value of printEven(6), which is the return value of printEven(8), which is the return value of printEven(10), which is 10.
What if no “Base Case”?
Unlike loops that have a definitive end, some recursions can go on forever without doing anything if base cases are not defined properly.
So if not meet any base case, theoretically, the recursion occurs infinitely so we wouldn’t expect any output to be printed to the console (Evident in finding factorial of a number). But in reality, our program runs out of memory (a stack overflow) and throws a segmentation fault error. This is a topic for another day.
This terminates the innermost call of the recursive function and returns from the bottom to the top. (like the steps of a staircase) (We’ll talk about this in a next article regarding memory stack overflow).
Conclusion
That’s our C program to print even numbers using recursion, and we considered even numbers in the inclusive range from 1 to 10. If you have any questions or ideas, please feel free to share them in the comments below.
Like rukbook.com so far? Chances are, you’ll like rukbook on YouTube (coming soon)! Click the button below to stay subscribed ahead of time!
Did you enjoy this article? Why not share it with your friends and connections? It helps spread the word about rukbook and it means a lot! Thanks for reading. Subscribe to rukbook.com mailing list by just entering your email below! It’s just one click!
