Home >Backend Development >C++ >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.
This is the most basic issue related to recursion.
Find the factorial of a given number using the concept of factorial.
#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; }
The factorial of 5 is 120
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.
#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; }
The 9th number of the Fibonacci series is 34
Calculate the sum of the digits in a given number
#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; }
The sum of digits of the number 563 is 14
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".
#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; }
The number 2 To the power 6 is 64
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 of28 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.
#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; }
The Greatest common divisor of 36 and 60 is 12
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.
#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; }
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!