Recursive Function in C Example Programs

Recursive function in C example | Here we will write the recursive function in C language, for example, the sum of natural number, Calculate power, Sum of digits, Base conversion, Prime factorization, Fibonacci series, gcd using recursion. Prerequisites:- Recursion in C Programming Language

Sum of Natural Number Using Recursion

Program:- Write a C program to find the sum of the natural number using recursion techniques.

We already know how to write a C program to find the sum of the natural number using for loop and while loop. Now we will find the same using Recursion. We know that For Recursion there will be a need for a recursive function. In Recursion, We divided the big problems into smaller problems or sub-problems.

Sum of N natural numbers given as 1+2+….+(n-1)+n. So, the problem can be divided as n + ( (n-1) +… + 2 + 1 ).

General case for finding the sum of natural number
sum(n) = n + sum(n-1);
The base case for finding the sum of the natural number
sum(0) = 0; or sum(1) = 1;

#include<stdio.h>

// recursive function for sum of natural number
int sum(int n)
 
{
   if(n==0) return 0; //base case
   else return( n + sum(n-1) ); //general case
}

int main()
{
   int num;

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

   printf("Sum of natural numbers 1+2+…+%d = %d",
                                 num, sum(num) );

   return 0;
}

Output for the different test-cases:-

Enter a positive integer number: 5
Sum of natural numbers 1+2+…+5 = 15

Enter a positive integer number: 10
Sum of natural numbers 1+2+…+10 = 55

Recursive Function Example to Calculate Power in C

Program:- Write a C program to find the power of a number using a recursive function.

Power of any number bⁿ given as b*b*…..*b (n-times). Here b is called base and n is called exponent. For Example:-

• 2² = 2*2 = 4
• 3³ = 3*3*3 = 27
• 5³ = 5*5*5 = 125

We had already written a program to calculate the power of a number using for loop, while loop and pow() function. Now, we will find the same using Recursion. if we want to calculate 5³ then this problem can be divided into a smaller problem such as 5*5² and so on.

General case for finding the sum of natural number
bn = b * b(n-1) ;
The base case for finding the sum of natural number
b1 = b; or b0 = 1;

#include<stdio.h>

// recursive function for finding power
int calPower(int a, int b)
{
   if(b==0) return 1; //base case
   else return a*calPower(a, --b); //general case
}

int main()
{
   int base, power;
   printf("Enter base and power: ");
   scanf("%d %d",&base, &power);
   printf("Result = %d", calPower(base, power));
   return 0;
}

Output for the different test-cases:-

Enter base and power: 2 3
Result = 8

Enter base and power: 5 3
Result = 125

Sum of Digits Using Recursion

Program:- Write a C program to find the sum of digits in a number using recursion.

For finding the sum of digits, we need to find all digits and sum all of them. Any number%10 gives the last digit of the number and number/10 removes the last digit of the number.

We have already written a C program to find the sum of digits using the loop. If you don’t know how to find the sum of digits of a number then first learn it then try with recursion.

// finding sum of digits using recursion
#include<stdio.h>

int sum = 0; //global variable

int digitalSum(int n)
{
   if(n!=0)
   {
     //general case
     sum = sum + (n%10); 
     digitalSum(n/10);
   }
   return sum; //base case
}

int main()
{
   int n;
   printf("Enter an integer number: ");
   scanf("%d",&n);
   printf("Sum of digits of %d is = %d",
                     n, digitalSum(n) );
   return 0;
}

Output for the different test-cases:-

Enter an integer number: 12345
Sum of digits of 12345 is = 15

Enter an integer number: 819
Sum of digits of 819 is = 18

Base Conversion Using Recursion

Program:- Write a C program to convert a positive decimal number to binary, octal, and hexadecimal number using recursion techniques.

To convert a decimal number into the binary, octal and hexadecimal number, we have to divide the decimal number repeatedly by the base till it reduced to 0 and print the remainders in reverse order. If the base is hexadecimal then we have to print alphabets for remainder values greater than equal to 10. We want to print the remainders in reverse order, so we can do this work in the unwinding phase.

#include<stdio.h>

// recursive function for base conversion
int convert(int num, int base)
{
   int rem = num % base;

   if(num==0) return;

   convert(num/base, base);

   if(rem<10) printf("%d",rem);
   else printf("%c",rem-10+'A');
}

int main()
{
   int number;

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

   printf("The Binary value of %d = ",number);
   convert(number,2);

   printf("\nThe Octal value of %d = ", number);
   convert(number,8);

   printf("\nThe Hexadecimal value of %d = ", number);
   convert(number,16);

   return 0;
}

Output:-

Enter a positive decimal number: 32
The Binary value of 32 = 100000
The Octal value of 32 = 40
The Hexadecimal value of 32 = 20

Recursive Function Example for Prime Factorization in C

Program:- Write a C program to find prime factors of a number using recursion techniques.

Prime factorization of a number means factoring a number into a product of prime numbers. For example, prime factors of 12 are 2 and 3.

To find prime factors of a number n, we check its divisibility by prime numbers 2,3,5,7,… till we get a divisor d. Now d becomes a prime factor and the problem reduces to finding the prime factor of n/d. The base case occurs when the problem reduces to finding prime factors of 1.

#include<stdio.h>

// recursive function for 
// finding prime factor
int primeFactor(int num)
{
   int i = 2;
   if(num==1) return;
   while(num%i!=0) i++;
   printf("%d\t",i);
   primeFactor(num/i);
}

int main()
{
   int number;

   printf("Enter a Positive Integer number: ");
   scanf("%d",&number);

   printf("Prime factors of %d :\n",number);
   primeFactor(number);

   return 0;
}

Output for the different test-cases:-

Enter a positive Integer number: 50
Prime factors of 50 :
2 5 5

Enter a positive Integer number: 96
Prime factors of 96 :
2 2 2 2 2 3

Enter a positive Integer number: 1470
Prime factors of 1470 :
2 3 5 7 7

For simplicity, we have checked the divisibility by all numbers starting from 2 (prime and non-prime). But we will get only prime factors. For example, 10 is a non-prime factor of 50 but it is already removed as a factor of 2 and the factor of 5.

Another C Programming examples on Recursion

• Fibonacci Series using Recursion:- C program to Find Nth Fibonacci term using Recursion, and Find first n numbers in Fibonacci series using recursion.
• Factorial using Recursion:- Write a C program to find factorial of a number using recursion techniques.
• GCD or HCF using Recursion:- Write a C program to find the greatest common divisor (GCD) of given two non-negative integers using recursion.

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search