There are many instances where you might need to solve a problem with recursion. It could be during a coding interview, some coursework, or you just love using recursion.
If you can solve the problem with a loop, then you'll be able to solve it with recursion. Read along to learn how to do this.
The Problem We're Trying to Solve
So, we're going to solve a simple problem. We'll be printing the string Recursion using a for loop, a while loop, and finally recursion.
While doing this, I'll point out the shared characteristics between loops and recursion.
I believe that would make it easier for you to understand how it works.
The Basic Structure of a Loop
To understand how to convert a loop to recursion, we need to understand the basic structure of a loop.
A loop is basically divided into four parts: initializer, condition check, execution, and then update.
To illustrate this, let's try to solve the problem with a for loop:
#include <stdio.h>
#include <string.h>
int main (void)
{
char *recursion = "Recursion";
for (int i = 0; i < strlen(recursion); i++)
{
printf("%c", recursion[i]);
}
printf("\n");
}
The initialiser is int i = 0. The condition check is i < strlen(recursion), the update is i++, while the execution is the part within the curly braces.
This is the same structure using a while loop for the same problem:
#include <stdio.h>
#include <string.h>
int main (void)
{
int i;
char *recursion = "Recursion";
i = 0;
while (i < strlen(recursion))
{
printf("%c", recursion[i]);
i++;
}
printf("\n");
}
The initialiser here is i = 0; , the condition check is while i < strlen(recursion) , the execution is printf("%c", recursion[i]); while the update is i++.
Running either of these loops gives us this output:
Recursion
Solving the problem using Recursion
Now that we have solved the problem using loops, let's attempt to solve it using recursion.
First, a refresher. A recursive function is basically a function that calls itself. And like a loop, a recursive function also has an initialiser, condition check, execution, and iterator update.
So, let's first declare a recursive function to solve the problem:
#include <stdio.h>
#include <string.h>
void print_recursion(char *recursion, int string_len, int i);
This recursive function is a void function because we're not returning anything. We just need to print the string Recursion. To pass in the string we need to print, we make char *recursion a parameter. For the length of the string, we create a parameter int string_len , and finally, we pass the initialiser with int i.
Now, we're going to define the recursive function:
#include <stdio.h>
#include <string.h>
void print_recursion(char *recursion, int string_len, int i);
int main (void)
{
int i;
char *recursion = "Recursion";
print_recursion(recursion, strlen(recursion), i = 0);
}
void print_recursion(char *recursion, int string_len, int i)
{
printf("%c", recursion[i]);
i++;
if (i == string_len)
{
printf("\n");
return;
}
print_recursion(recursion, string_len, i);
}
Note that we set the initialiser when we make the function call here:
#include <stdio.h>
#include <string.h>
void print_recursion(char *recursion, int string_len, int i);
int main (void)
{
int i;
char *recursion = "Recursion";
print_recursion(recursion, strlen(recursion), i = 0);
}
We do this because if we set the initiliser to 0 within the recursive function, then every time the function calls itself, the initiliser is reset to 0. That would create a lot of problems, like printing the 0th index of the string in an infinite loop, and we don't want that.
Next is the execution part of the code in the function definition here:
#include <stdio.h>
#include <string.h>
void print_recursion(char *recursion, int string_len, int i);
int main (void)
{
int i;
char *recursion = "Recursion";
print_recursion(recursion, strlen(recursion), i = 0);
}
void print_recursion(char *recursion, int string_len, int i)
{
printf("%c", recursion[i]);
}
So, the function prints the first character of the string R , then we move to the iterator update:
#include <stdio.h>
#include <string.h>
void print_recursion(char *recursion, int string_len, int i);
int main (void)
{
int i;
char *recursion = "Recursion";
print_recursion(recursion, strlen(recursion), i = 0);
}
void print_recursion(char *recursion, int string_len, int i)
{
printf("%c", recursion[i]);
i++;
}
Recall that i = 0 in the function call. When we increment it, it becomes 1.
Next, we make the condition check the base case of the recursion:
#include <stdio.h>
#include <string.h>
void print_recursion(char *recursion, int string_len, int i);
int main (void)
{
int i;
char *recursion = "Recursion";
print_recursion(recursion, strlen(recursion), i = 0);
}
void print_recursion(char *recursion, int string_len, int i)
{
printf("%c", recursion[i]);
i++;
if (i == string_len)
{
printf("\n");
return;
}
}
This means that the recursive function would keep on running until the iterator matches the int string_len that we already passed to the function. Recall that this is the size of the string that we got using strlen(recursion) in the function call.
Finally, we make the recursive call:
#include <stdio.h>
#include <string.h>
void print_recursion(char *recursion, int string_len, int i);
int main (void)
{
int i;
char *recursion = "Recursion";
print_recursion(recursion, strlen(recursion), i = 0);
}
void print_recursion(char *recursion, int string_len, int i)
{
printf("%c", recursion[i]);
i++;
if (i == string_len)
{
printf("\n");
return;
}
print_recursion(recursion, string_len, i);
}
When we make the recursive call, we pass incremented i to the function. When the function calls itself, it runs the execution part of the code, but this time i has already been incremented by 1, printing recursion [i + 1], the next character in the string.
Then i gets incremented again, the base case doesn't get activated until the i has been incremented enough times in subsequent function calls that it becomes equal to string_len. Then the recursive function returns.
When we run the code, we get this output:
Recursion
If we run both the while loop and the recursive function:
#include <stdio.h>
#include <string.h>
void print_recursion(char *recursion, int string_len, int i);
int main (void)
{
int i;
char *recursion = "Recursion";
i = 0;
while (i < strlen(recursion))
{
printf("%c", recursion[i]);
i++;
}
printf("\n");
print_recursion(recursion, strlen(recursion), i = 0);
}
void print_recursion(char *recursion, int string_len, int i)
{
printf("%c", recursion[i]);
i++;
if (i == string_len)
{
printf("\n");
return;
}
print_recursion(recursion, string_len, i);
}
We get the same output:
Recursion
Recursion
So, that's it. That's how you create a recursion from a loop. If you have any questions, feel free to ask them in the comments.