Exploring Recursion
What is Iteration? Iteration is the repetition of a block of statements within a computer program using a loop.
Recursion is a method where the solution to a problem depends on the solutions to smaller instances of the same problem. A recursive function is a function that calls itself. The best way to explain this in a photo format is an example of a Russian doll. Every other doll is a copy of the doll that is inside the next one.
Let’s looks at a popular math concept named Factorial.
If you were asked what was the factorial of 5. It would mean the following
5! = 5*4*3*2*1
5! = 5*4*3*2
5! = 5*4*6
5! = 5*24
5! = 120
This means we have iterated through the multiplication of all the numbers that make 5 to get the factorial value of 5 which is 120.
To write a code to mimic the above iteration, this is what the code would look like
// Code to calculate the factorial of a given integer
#include <stdio.h>
int factorial(int n)
{
int factorialValue;
int i;
// factorialValue is a variable to store the factorial value
factorialValue = 1;
//i is the counter for the while loop
i = 1;
while(i <= n)
{
factorialValue = factorialValue * i;
i++;
}
return(factorialValue);
}
int main() {
// dummy printf
printf(“Hello world, THis program calcuates the factorail of an int\n”);
int f;
f = factorial(5);
printf(“5! = %d\n”, f);
return 0;
}
While using Recursion, the factorial of 5! would have been solved by the following:
5! = 5*4!
4! = 4*3!
3! = 3*2!
2! = 2*1!
1! = 1* 0!
0! = 1
In simpler terms
!n = n *!(n-1)
Factorial(n)= n*factorial(n-1)
// code to calculate factorial of an int using recursion
#include <stdio.h>
int factorial(int n)
{
if (n == 0)
{
return (1);
}
return ( n * factorial(n-1));
}
int main() {
// Write C code here
printf(“Hello world, code to print factorial of a integer using recursion\n”);
int f;
f = factorial(5);
printf(“the factorial of 5! = %d\n”, f);
return 0;
}
Printing the alphabet
First, we look at printing the alphabet iteratively using a loop
// Code to print the alphabet
#include <stdio.h>
#include<unistd.h>
void print_char(char c)
{
Recommended by LinkedIn
write (1,&c,1);
}
void print_alphabet(void)
{
char c;
c = ‘a’;
while (c <= ‘z’)
{
print_char(c);
c = c + 1;
}
}
int main() {
// Write C code here
printf(“Hello world”);
print_alphabet();
print_char(‘\n’);
return 0;
}
Here is how we print the alphabet using recursion
// code to print the alphabet using recursion
#include <stdio.h>
#include<unistd.h>
void print_char(char c)
{
write (1,&c,1);
}
void print_all_letters_from(char c)
{
if (c > ‘z’)
{
return;
}
print_char(c);
print_all_letters_from(c + 1);
c = ‘a’;
}
void print_alphabet(void)
{
print_all_letters_from(‘a’);
}
int main() {
// dummy printf code
printf(“Code to print the alphabet using recursion”);
print_alphabet();
print_char(‘\n’);
return 0;
}
Conclusion
Recursion is a technique in which a function calls itself to solve a problem. The problem is solved by breaking it down into smaller instances of the problem. The recursive function has to have a base case or an exit case that acts as the exit or defines when the recursion should stop. The base case is important as it makes sure the recursion function does not run infinitely.
In some cases, recursion can be having higher performance cost and memory costs while compared to an iterative solution. This is due to the stack storage of the values of the recursive values.
Recursion is mostly used in solving factorial problems, Fibonacci numbers, traversing tree structures and some search algorithms and sorting algorithms.
Example
Here are some more examples of problems that be solved using recursive functions.
1. Write a recursive function called sumDigits that returns the sum of all digits in a given integer value.
// code to sum the values of integers in a number
#include <stdio.h>
int sumDigits(int n)
{
//base case
if (n == 0)
{
return 0;
}
return(n % 10) + sumDigits(n/10);
}
int main() {
// Write C code here
printf(“The sum of integers in the number is %d\n”, sumDigits(53));
return 0;
}