What is recursion in a programming world?

Steffany Naranjo Vargas
3 min readFeb 23, 2021

Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.

For example.

void recursion() {
recursion(); /* function calls itself */
}

int main() {
recursion();
}

The C programming language supports recursion, a function to call itself. But while using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.

Recursive functions are very useful to solve many mathematical problems, such as calculating the factorial of a number, generating Fibonacci series, etc.

Some examples about how recursion works

Generates the Fibonacci series for a given number using a recursive function

#include <stdio.h>

int fibonacci(int i) {

if(i == 0) {
return 0;
}

if(i == 1) {
return 1;
}
return fibonacci(i-1) + fibonacci(i-2);
}

int main() {

int i;

for (i = 0; i < 10; i++) {
printf("%d\t\n", fibonacci(i));
}

return 0;
}

Output:

0	
1
1
2
3
5
8
13
21
34

Factorial of a given number using recursion

#include <stdio.h>

unsigned long long int factorial(unsigned int i) {

if(i <= 1) {
return 1;
}
return i * factorial(i - 1);
}

int main() {
int i = 12;
printf("Factorial of %d is %d\n", i, factorial(i));
return 0;
}

Output

Factorial of 12 is 479001600

Sum of Natural Numbers Using Recursion

#include <stdio.h>
int sum(int n);

int main() {
int number, result;

printf("Enter a positive integer: ");
scanf("%d", &number);

result = sum(number);

printf("sum = %d", result);
return 0;
}

int sum(int n) {
if (n != 0)
// sum() function calls itself
return n + sum(n-1);
else
return n;
}

Output:

Enter a positive integer:3
sum = 6

Initially, the sum() is called from the main() function with number passed as an argument. Suppose, the value of n inside sum() is 3 initially. During the next function call, 2 is passed to the sum() function. This process continues until n is equal to 0. When n is equal to 0, the if condition fails and the else part is executed returning the sum of integers ultimately to the main() function.

How memory is allocated to different function calls in recursion?

When any function is called from main(), the memory is allocated to it on the stack. A recursive function calls itself, the memory for a called function is allocated on top of memory allocated to calling function and different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function by whom it is called and memory is de-allocated and the process continues.
Let us take the example how recursion works by taking a simple function.

I hope this blog helps you to understand how recursion works in C programming.

Reference

Recursion in C — Cprogramming.com. (2019). Alex Allain. https://www.cprogramming.com/tutorial/c/lesson16.html

GeeksforGeeks. (2021, 3 febrero). Recursion. https://www.geeksforgeeks.org/recursion/

Recursion in C — javatpoint. (2018). www.javatpoint.com. https://www.javatpoint.com/recursion-in-c

--

--