Recursion
Practice problems
UMAMA RAHMAN
DSA II LAB
Print the numbers from 1 to n.
#include<iostream>
using namespace std;
//print 1 to n
void print(int n){
if(n<=0) return;
print(n-1);
cout<<n<<endl;
}
int main(){
print(10);
}
Calculate the sum from 1 to n
#include<iostream>
using namespace std;
int Sum(int n){
if(n<=0) return 0;
return n+Sum(n-1);
}
int main(){
int n=5;
cout<<"Sum from 1 to "<<n<<":"<<Sum(n);
}
Calculate the factorial of n.
#include<iostream>
using namespace std;
int Factorial(int n){
if(n<=0) return 1;
return n*Factorial(n-1);
}
int main(){
int f=Factorial(5);
cout<<"factorial:"<<f<<endl;
}
Consider the following scenario
Suppose that, you are at 0th stair and you have to reach
at nth stair. Each time you can climb 1 or 2 steps. Find
out the total number of distinct ways you can climb from
0th to nth stair.
Calculate the sum of digits of a given
number n.
#include<iostream>
using namespace std;
int digitSum(int n){
if(n==0) return 0;
return n%10 + digitSum(n/10);
}
int main(){
int d=digitSum(342);
cout<<"digit sum:"<<d;
}
Count the number of digits of a given number n.
#include<iostream>
using namespace std;
int CountDigit(int n){
if(n==0) return 0;
return 1 + CountDigit(n/10);
}
int main(){
int d=CountDigit(0);
cout<<"digit count:"<<d;
}
Calculate a to the power b
#include<iostream>
using namespace std;
int power(int a,int b){
if(b==0) return 1;
return a*power(a,b-1);
}
void printPower(int a,int b){
int x=power(a,abs(b));
cout<<a<<" to the power of "<<b<<":";
if(b<0) cout<<"1/"<<x;
else cout<<x;
}
int main(){
int a=2,b=-5;
printPower(a,b);
}
Print the array elements.
#include<iostream>
using namespace std;
void printArray(int arr[],int idx){
//print the value at index n
if(idx<0) return;
printArray(arr,idx-1);
cout<<arr[idx]<<endl;
}
int main(){
int a[]={4,5,6,7,8,9,10};
printArray(a,sizeof(a)/sizeof(int)-1);
}
Calculate the sum of array
#include<iostream>
using namespace std;
int ArraySum(int arr[],int n){
if(n<0) return 0;
return arr[n]+ArraySum(arr,n-1);
}
int main(){
int a[]={4,5,6,7,8};
int sum=ArraySum(a,sizeof(a)/sizeof(int)-1);
cout<<"Array sum:"<<sum<<endl;
}
Find the largest element of a given array.
#include<iostream>
using namespace std;
//largest in an array
int largest(int arr[],int n){
if(n<0) return INT_MIN;
return max(arr[n],largest(arr,n-1));
}
int main(){
int a[]={414,52,61,7,181};
int l=largest(a,sizeof(a)/sizeof(int)-1);
cout<<"largest :"<<l<<endl;
}
Find if a number is a power of 4.
•
Check whether a given string is palindrome or not.
#include<iostream>
#include<string>
using namespace std;
bool palindrome(string str){
int l=[Link]();
if(l==0) return true;
if(str[0]==str[l-1]) return palindrome([Link](1,l-2));
else return false;
}
int main(){
if(palindrome("abeeba")) cout<<"palindrome";
else cout<<"not palindrome";
}
Remove white spaces from a string & convert upper cases to lower
#include <iostream>
#include <string>
using namespace std;
string removeSpaceToLower(string str)
{
if ([Link]()) return "";
char last = [Link]();
string rest = removeSpaceToLower([Link](0, [Link]() - 1));
if (last == ' ')
return rest; // skip spaces
else
return rest + char(tolower(last)); // keep lowered
}
int main()
{
cout << removeSpaceToLower("Hello World It's Me.") << endl;
}