Recursion practice problems and solutions

In this article, we will discuss some recursion practice problems and their detailed solutions.

Let’s first understand what recursion is and how it works:

Recursion - Recursion is a programming technique in which a function or method calls itself multiple times to solve a problem. This function breaks the problem into smaller sub-problems and solves them until the base case is reached.

The basic case is a stopping condition that ensures that the function stops calling itself and returns the result within a limited time.

Recursion is a powerful technique for solving complex problems, but it is important to design it carefully to avoid infinite loops and to ensure that the function terminates correctly when a function is called recursively multiple times.

Question 1

This is the most basic issue related to recursion.

Find the factorial of a given number using the concept of factorial.

Implementation in C

#include <bits/stdc++.h>
using namespace std;
// recursive function to 
// calculate factorial of number
int Numberfact(int number) {
// base condition
    if(number == 1) {
        return 1;
    } else {
        return number * Numberfact(number-1);
    }
}
// main code
int main() {
   int number = 5;
   cout<< " The factorial of 5 is " << Numberfact(number);
   return 0;
}

Output

The factorial of 5 is 120

Question 2

In this problem, we need to print the n-th number in the sequence starting from 1, where the i-th number is the sum of its first two numbers, commonly known as the Fibonacci sequence.

Implementation in C

#include <bits/stdc++.h>
using namespace std;
// function to 
// calculate nth number of
// Fibonacci series
int Numberfib(int number) {
   // base condition
   if(number <= 1) {
      return number;
   } else {
      return Numberfib(number-1)+Numberfib(number-2);
   }
}
// main code
int main() {
   int number = 9;
   cout<< " The 9th number of the Fibonacci series is " << Numberfib(number);
   return 0;
}

Output

The 9th number of the Fibonacci series is 34

Question 3

Calculate the sum of the digits in a given number

Implementation in C

#include <bits/stdc++.h>
using namespace std;
// recursive method to 
// calculate sum of digits
int Sumofdigits(int number) {
// base case
   if(number <=10) {
      return number;
   }
   else {
      return number%10 + Sumofdigits( number/10 );
   }
}
// main code
int main() {
   int number = 563;
   cout<< " The sum of digits of the number " << number << " is "<< Sumofdigits(number);
   return 0;
}

Output

The sum of digits of the number 563 is 14

Question 4

Calculate the value of a number raised to the "power" power.

In this question, we will be given two numbers "number" and "power", and our task is to find the "power" power of the number "number".

Implementation in C

#include <bits/stdc++.h>
using namespace std;
// recursive method to 
// generate the nth power
// of a given number
int powerofx( int nums , int pow) {
   // termination condition
   if(pow == 0) {
      return 1;
   } else {
      return nums*powerofx(nums, pow-1);
   }
}
// main code
int main() {
   int nums = 2;
   int pow =6;
   cout<< " The number " << nums << " To the power "<< pow <<" is "<< powerofx(nums, pow);
   return 0;
}

Output

The number 2 To the power 6 is 64

Question 5

Find the GCD (greatest common divisor) of two numbers.

GCD stands for Greatest Common Divisor, which is the largest number by which two or more numbers can be divided without a remainder. It is also called the highest common factor (HCF) of these numbers.

Suppose we have two different numbers: 14 and 28.

The factors of 14 are 1, 2, 7 and 14.

The factors of

28 are 1, 2, 4, 7, 14 and 28.

We can then find the common factors of these two numbers, which are 1, 2, 7 and 14. The largest number that can divide both 14 and 28 without leaving a remainder is 14, so the greatest common divisor of 14 and 28 is 14.

Implementation in C

#include <bits/stdc++.h>
using namespace std;
// function to recursively
// calculate the gcd
int greatestcommondivisor(int num1, int num2) {
   if (num2 == 0) {
      return num1;
   } else {
      return greatestcommondivisor(num2, num1 % num2);
   }
}
// main code
int main() {
   int num1 = 36;
   int num2 =60;
   cout<< " The Greatest common divisor of " << num1 << " and "<< num2<<" is "<< greatestcommondivisor(num1, num2);
   return 0;
}

Output

The Greatest common divisor of 36 and 60 is 12

Question 6

Print array in reverse order

We get an array containing n integers, and our task is to print out the same array in order, with the first number as the last number, the second number as the second to last number, and so on.

Implementation in C

#include <bits/stdc++.h>
using namespace std;
// recursive function to 
// =reverse print the given array
void reverseprint(int nums[], int begining, int end) {
   if (begining >= end) {
      return ;
   } else {
      cout << nums[end-1] << " ";
      reverseprint(nums, begining, end - 1);
   }
}
// main code
int main() {
   int size =4;
   int nums[] = { 2, 3, 4, 5 } ;
   cout<< " the given array is reverse order is " << endl ;
   reverseprint(nums, 0, size);
   return 0;
}

Output

the given array is reverse order is 
5 4 3 2 

Here are some more basic practice questions to master a basic level of recursion -

Write a function to recursively check whether a string is a palindrome.

Write a function to find the factorial of a given number using tail recursion.

Write a function to solve the Tower of Hanoi problem.

Write a function to perform a binary search on a sorted array.

The above is the detailed content of Recursion practice problems and solutions. For more information, please follow other related articles on the PHP Chinese website!