In this section, we will learn what the recursion is and how to use it in C.
Before reading this section, we’re assuming you know what functions and stack& heap are.
Note: the concept of stack is important in order to understand recursion. So please, if you don’t know what the Stack is, it’s important to read the `stack& heap` section first.
What Is Recursion and What Is a Recursive Function?
Recursion is the process of invoking a function over and over again. In C programming, a function is allowed to call itself within its body. This process is called recursion and the function that is doing this process is called a recursive function.
Note that there’s no difference in the way a function calls another function and the way it calls itself within its body.
C Recursion Syntax
The syntax of creating recursion is simple:
data-type functionName(){
functionName();
}
As you can see, all we need to do is to call a function within its body.
Example: creating recursive function in C
The best way of describing the work of recursion and what it does is to run an example and explain from there.
So let’s start with an example:
#include <stdio.h>
int sum (int);
int main() {
int result = sum(5);
printf("The result is: %d\n", result);
return 0;
}
int sum(int number){
if (number >0){
return number + sum(number -1);
}else{
return 0;
}
}
Output:
15
How recursion works in C?
In the example above, the `sum-function` called itself in its body, and this recursion caused the result to be 15.
Let’s see what happened behind the scene:
The `main` function, as mentioned in the `stack& heap` section, is the entry point of our program. So the first time we run the `main` function, a space in the stack memory will be allocated to the `main` function and the CPU will start to run the instructions of this function.
The first line of this function is to declare a variable named `result` and assign the value returned from `sum` function to the variable.
So we’re calling the `sum` function here and that’ll cause a new space in the stack memory to be allocated to this function.
The `main` function at this point stops running and will wait for the `sum` function to execute.
Within the body of the `sum` function, the first line of instruction is to check whether the value assigned to the local variable ` input` is greater than 0.
Of course, the value assigned to this variable is greater than 0 (currently it is 5) so the result of the condition is true and the body of the if-statement will run.
Within the body of the `if` statement, there’s the `return` keyword, which means the function is about to finish and return the result of the `input + sum(input -1)` expression. If we replace the `input` parameter with its actual value, we will have this expression `5 +sum(4)`.
As you can see, in order to resolve this expression, we need to call the `sum` function, but this time with the value 4 as its argument.
Each time we call a function, a new space in the stack memory will be allocated to that function and calling a function with the same name is no exception.
So here calling the `sum` function with the value 4 will create a new space in the memory and the CPU will start to execute this function.
Again, the first line of instruction in this function is to check whether the value assigned to the `input` variable is greater than 0, which in this case the condition is true (the value is 4 and so greater than 0) and the body of the `if` statement will run as a result.
In the body again, we have to return the result of `input + sum(input – 1)` expression which is equal to `4 + sum(3)`.
In order to solve the expression, we need to call the `sum(3)` function as well.
The same things happen here: a new space in the stack memory will be assigned to the `sum(3)` function and the CPU starts to execute its instructions.
Note: So far, we have a stack of 4 functions: `main()`, `sum(5)`, `sum(4)`, `sum(3)`. With the `sum(3)` function being on top of the stack and the rest of functions waiting for the function on top of them to finish its work so each gets a chance of rerunning.
Now moving on with the `sum(3)` function:
Within the body of this function, we have the `if` statement that checks whether the value assigned to the `input` variable is greater than 0. Because the value is higher than 0, the body of this statement will run.
Within this body, we need to return the result of the `input + sum(input -1)` expression, which is equal to `3 + sum (2)`.
Again, the result of this expression depends on the returned value from calling the `sum` function with the value of 2 as its argument.
So now we have the `sum(2)` function. A new space in the stack memory will be assigned to this function and its instructions will run.
Within the body, we have the `if` statement and because the value assigned to the `input` variable is greater than 0 (the value is 2), the condition is true and the body of the `if` statement will run.
In the body, there’s the `return` keyword, which means the function is about to return the result of the `input + sum(input -1)` expression, which is equal to `2 + sum(1)`.
The result of this expression is dependent on the returned value from `sum(1)` function and so the function needs to run first.
Again, at this time, new space for the `sum(1)` function will be allocated in the stack memory and its instructions will run.
Note: So far we have a stack of 6 functions: `main()`, `sum(5)`, `sum(4)`, `sum(3)`, `sum(2)` and `sum(1). With the `sum(1)` function being on top of the stack and the rest of functions waiting for the function on top of them to finish its work, so they get a chance of running again.
In the body of `sum(1)` function we have the condition of the if statement which resulted true because the value of the `input` variable is greater than 0 and so the body of the `if` statement ran one more time.
The expression here is `input + sum(input -1)` which is equal to `1 + sum(0)`.
Because the result of the expression is dependent on the returned value from `sum(0)` function, a new space will be allocated to `sum(0)` function in the stack and its instructions will run.
The first line of instruction in the `sum(0)` function is to check whether the value assigned to the `input` variable is greater than 0 which in this case it’s not! And so the body of the `if` statement will be skipped and the `else` statement will run instead.
In the else statement, we have the `return 0` statement, which is the final returned value from `sum(0)` function.
At this stage we have the `sum(0)` function off the stack and the function below it which is the `sum(1)` becomes the top stack function to be executed next.
In the `sum(1)` we had the `1+sum(0)` expression. Because the result of `sum(0)` is now clear, we can solve the expression here by replacing the `sum(0)` with the value 0 and so the final returned value from the `sum(1)` function will be 1 which is the result of `return 1+0`.
Now the `sum(1)` function is also off the stack and the function below it which is the `sum(2)` becomes the top stack function and the CPU continues to run its last instruction that caused the function to call the `sum()` function with the value 1.
The expression in this function was `2 + sum(1)`.
Of course now that the result of the `sum(1)` function is cleare (which is 1) the call to this function is replaced by the returned value (1) and so the final tally of this expression becomes 3 (2 + 1). Now the value 3 is the returned value from `sum(2)` function.
Alright, the `sum(2)` function is also off the stack at this stage and the function below it will be run (which is `sum(3)` function).
In the `sum(3)` function the expression was `3+ sum(2)` and because the result of the `sum(2)` is 3, this result will be replaced with the `sum(2)` and the final result of the `sum(3)` function becomes 6.
Now the `sum(3)` is off the stack and the function below it will run (which is the `sum(4)` function).
In the `sum(4)` function, the expression was `4 + sum(3)` and now that the result of the `sum(3)` function is clear; the result replaces the call to the `sum(3)` function and so the expression becomes `4 + 6` which is equal to 10. So the result of the `sum(4)` function is 10 and that will return to the caller function of the `sum(4)` which was the `sum(5)`.
The expression in the `sum(5)` function was `5 + sum(4)` and because the result of the `sum(4)` expression is clear now, the function will be replaced with its resolved value which is 10.
The final and resolved value of the `sum(5)` function will be 15, and that’s the returned value from this function.
Now the `sum(5)` is resolved and off the stack and the function below it will get a chance to run.
The function below the `sum(5)` function is the `main` function and it’ll start running right where it called the `sum(5)` function.
Here, the `main` function was waiting for the result of `sum(5)` function and now because the result is cleared (which is 15), this value will be assigned to the `result` local variable.
The next line of instruction in the `main()` is to call the `printf()` function.
A new space in the stack will be allocated to the `printf` function and it is now on the top of the stack and CPU starts to run the instructions of this function.
After this function finished its work (Sending the argument to the output stream) it’ll be off the stack and the `main` function will keep running the next line of its instructions.
The final line in the `main` function is a call to the `return 0; ` statement which is equal to the end of the program.
Notes on C recursion:
- Recursion is about simplifying a process. For example, if someone asked to add a range of numbers together (for example, 0 to 100). We can simply use the recursion just like the way we did it in the example above and got the total sum.
- Recursion is somewhat difficult at first, but if you keep running other types of examples, it’ll soon get easy to understand.
- If you don’t pay attention, a function can call itself infinitely! Of course, because the memory is limited, a function might call itself multiple times and then the program simply crashes because it ran out of memory which also known as the `Stack overflowed`.
So make sure there’s a condition in your function that finally will stop letting a function to call itself.
Example: creating recursion in C
#include <stdio.h>
void printRange( int);
int main() {
printRange(10);
return 0;
}
void printRange(int number){
if (number > 0){
printf("The number is: %d\n ", number);
printRange(number -1);
}
}
Result:
The number is: 10 The number is: 9 The number is: 8 The number is: 7 The number is: 6 The number is: 5 The number is: 4 The number is: 3 The number is: 2 The number is: 1
In this example, again, we used recursion in the `printRange` function. The idea here is to send a number to the `printRange` function and this function will print the entire range of numbers below the input number until it reaches to 0.
Within the body of the function, the first line is to check whether the input value is greater than 0. This is an insurance that will actually stop a function form calling itself infinitely.
Then, within the body of the `if` statement, we first print the number and then called the function itself with `number-1` as its argument.
For each function call, there will be a new space in the stack-memory allocated to the called function.
This process keeps happening until the condition of the `if` statement no-longer returns true. Which in that case the functions on the stack will be removed from the stack one at a time until there’s no function left there.
Infinite recursion in C
Infinite recursion means creating a recursive function that will never stop calling itself!
Infinite recursion mainly happens when we don’t put a breakpoint in a function and hence the function would call itself infinitely to the point where the program crashes.
We will get back to this crashing part in just a moment. But for now, let’s see how we can create infinite recursion in a program.
Example: creating infinite recursion in C
#include <stdio.h>
void infinity(void);
int main() {
infinity();
return 0;
}
void infinity(void){
printf("%s\n", "Calling the infinity function...");
infinity();
}
Output:
Calling the infinity function... Calling the infinity function... Calling the infinity function... Calling the infinity function... Calling the infinity function... Calling the infinity function... Calling the infinity function... Calling the infinity function… ….
Here within the body of the `infinity` function, we called the function itself and if you look closely, there’s no break point here, actually! So what happens is that the function will call itself without ever stopping until the Operating System shut it down because it’s taking too much stack memory space!
Note: depending on your OS, you may or may not get a StackOverFlow error on the output.
Stop condition in C Recursion
As you saw from the last example, when working with a recursive function, it’s important to set a stop condition for a function so that it won’t run infinitely!
Stop condition means a condition in a recursive function that eventually causes the function to stop calling itself, as you saw an example of this stop condition at the beginning of this article.
What is StackOverFlow error in C?
The StackOverFlow error is an error that occurs when there’s no space availability in the stack memory of a program to be used!
This mainly happens when we have a recursive function without any break point in it. Basically, when a function infinitely calls itself, this error will occur.
Note: this error will crash a program as you saw in the example of the infinite recursion.
