BlogsDope image BlogsDope

Common examples of loops using recursion in C

May 27, 2017 C EXAMPLE LOOP RECURSION 18744

This article is an extension of the ‘My functions’ chapter of C. If you need to learn basics then visit the C course first. You can also practice a good number of questions from practice section.

This is an article on writing the common loop codes using recursion for the better understanding of recursion. So, let’s continue.

Sum of first n natural numbers using recursion


#include <stdio.h>

int sum_n(int n)
{
    if (n==1)
        return n;
    else
        return n+sum_n(n-1);
}

int main()
{
    printf("%d\n",sum_n(100));
    return 0;
}

Let’s understand this example by calculating the sum of first 4 natural numbers i.e., sum_n(4) step by step.

  • The condition of ‘if’ is not correct. So, the statements of else will get executed.
    The value returned in the else is n+sum_n(n-1) i.e., 4+sum_n(3).
  • Now, sum_n(3) will return 3+ sum(2). So, the above expression will become 4+3+sum_n(2).
  • Similarly, sum_n(2) will return 2+sum_n(1) and the expression will become 4+3+2+sum_n(1) .
  • During sum_n(1), the condition of ‘if’ will get satisfied and 0 will get returned and thus making the final expression 4+3+2+1.

Sum of all the digits of a number using recursion


#include <stdio.h>
#include <math.h>

int sum_digit(int n)
{
    //to calculate the number of digits in a number
    int number_of_digits = ((int)log10(n))+1;
    if (number_of_digits == 1)
        return n;
    else
        return n%10 + sum_digit(n/10);
}

int main()
{
    printf("%d\n",sum_digit(54321));
    return 0;
}

Please note that we are using ‘math.h’ library in the above code and hence we need to link this library while compiling our file by using:

cc -c filename.c
cc -o filename filename.c -lm

This example follows the logic that the sum of all the digits of a number 1234 will be 4 + sum of all the digits of the number 123 and again be applying the same logic on 123, it will become 4 + 3 + sum of all the digits of the number 12 then 4 + 3 + 2 +  sum of all the digits of the number 1 and finally 4 + 3 + 2 + 1.

This is exactly what we are doing in our code.

((int)log10(n))+1 will give the number of digits in the number ‘n’.

return n%10 + sum_digit(n/10) – n%10 is the last digit of the number ‘n’ and  n/10 is a number excluding the last digit of the number ‘n’.

Multiplication table using recursion


#include <stdio.h>

int mul_table(int n, int i)
{
    printf("%d\n",n*i);
    if (i!=10)
        mul_table(n,i+1);
}

int main()
{
    mul_table(5, 1);
    return 0;
}

This is an example of just calling the function ‘mul_table’ inside itself with a different value of ‘i’.

mul_table(int n, int i) – ‘n’ is the number for which we have to print the multiplication table and ‘i’ is the number which will get multiplied by ‘n’ to print the table. We will call the ‘mul_table’ from the main function with the value of ‘i’ equal to 1 e.g., mul_table(5, 1);.

mul_table(n,i+1) – This line will call the function ‘mul_table’ with the value of ‘i’ increased by 1. This means that if the value of ‘i’ is 4 (n*4 got printed) then in the next turn, the value of ‘i’ will be 5 and n*5 will get printed.

Calculating the power of one number raised to another using recursion


#include <stdio.h>

int power(int a, int b)
{
   if (b == 1)
        return a;
    else
        return a * power(a,b-1);
}

int main()
{
    printf("%d\n",power(5,3));
    return 0;
}

The logic behind this code is that the ab = a * ab-1. For e.g., 43 = 4*42 = 4*4*41 = 4*4*4.

You can see the examples of Factorial here.


Liked the post?
Developer and founder of CodesDope.
Editor's Picks
2 COMMENTS

Please login to view or add comment(s).