
☠️Recursion
Q1:
Head-Recursion
Q1:
Head-Recursionvoid headRecursion(int count) {
// Base-Condition
if (count == 0)
return;
// Recursive Relation
headRecursion(count - 1);
// Processing
cout << count << " ";
}
// o/p = 1 2 3 4 5
Q2:
Tail-Recursion
Q2:
Tail-Recursion
void tailRecursion(int count) {
// Base-Condition
if (count == 0)
return;
// Processing
cout << count << " ";
// Recursive Relation
tailRecursion(count - 1);
}
// o/p = 5 4 3 2 1
Q3:
Fibonacci Number
Q3:
Fibonacci Numberint fib(int n) {
if(n < 2)
return n;
return fib(n-1) + fib(n-2);
}

int climbStairs(int n) {
if(n < 0)
return 0;
if(n == 0)
return 1;
return climbStairs(n-1) + climbStairs(n-2);
}
Q5:
SayDigits
Q5:
SayDigits#include <iostream>
using namespace std;
void sayDigits(int x, string* arr) {
if (x == 0) return ;
int digit = x%10;
x /= 10;
sayDigits(x, arr);
cout << arr[digit] << " ";
}
int main() {
string arr[] = {"Zero", "One", "Two", "Three", "Four",
"Five", "Six", "Seven", "Eight", "Nine"};
sayDigits(4129192, arr);
}
Q6:
isSorted-Array
Q6:
isSorted-Array#include <iostream>
using namespace std;
bool isSorted(int *arr, int size, int i = 0) {
if(i == size-1) return true;
if(arr[i] > arr[i+1]) return false;
isSorted(arr, size, ++i);
}
int main() {
int arr[4] = {5, 7, 7, 10};
cout << boolalpha << isSorted(arr, 4);
}

bool isSorted(int arr[], int size);
bool isRotated(int arr[], int size);
bool check(int nums[], int size) {
return isSorted(nums, size);
}
bool isSorted(int arr[], int size) {
if(size == 0 || size == 1)
return true;
if(arr[0] > arr[1])
return isRotated(arr + 1, size);
return isSorted(arr + 1, size - 1);
}
bool isRotated(int arr[], int size) {
if(size == 0 || size == 1)
return true;
if(arr[0] > arr[1])
return false;
return isRotated(arr + 1, size - 1);
}
int main() {
int arr[5] = {3,4,5,1,2};
if(check(arr, 5))
cout << "Given Array is Sorted or Rotated";
else
cout << "Given Array isn't Sorted or Rotated";
}
Q8:
Linear Search
Q8:
Linear Searchvoid print(int arr[], int size) {
cout << "Size: " << size << endl;
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
} cout << endl;
}
bool linearSearch(int arr[], int size, int k) {
print(arr, size);
if(size == 0)
return false;
if(arr[0] == k)
return true;
return linearSearch(arr + 1, size - 1, k);
}
Day-04 Recursion
Q9:
Reverse String
Q9:
Reverse String #include <iostream>
#include <cstring>
using namespace std;
void reverseString(char* str, int e, int s = 0) {
if(s > e) return ;
swap(str[s], str[e]);
reverseString(str, --e, ++s);
}
int main() {
char str[] = "nafees";
reverseString(str, strlen(str)-1);
for (auto c : str) {
cout << c << " ";
}
}
In this program, the recursiveFunc()
function is called recursively until the base case is reached. The base case is when s > e
. Therefore, the number of recursive calls made by the function is equal to half the length of the string. Hence, the time complexity of your program is O(n/2) or O(n) 1.
The space complexity of your program depends on the maximum depth of recursion. In your program, the maximum depth of recursion is equal to half the length of the string. Therefore, the space complexity of your program is O(n/2) or O(n) 2.
Q10:
Find Exponent in logarithmic time
Q10:
Find Exponent in logarithmic time#include "iostream"
using namespace std;
int findExpo(int a, int pow, int ans = 0) {
if(pow == 0) return 1;
else if(pow == 1) return a;
else if(pow % 2 == 0) {
// a^(n/2).a^(n/2)
ans = findExpo(a, pow/2, ans);
return ans * ans;
}
else {
// a^[(n-1)/2].a^[(n-1)/2].a
ans = findExpo(a, (pow-1)/2, ans);
return ans*ans*a;
}
}
int main() {
int a = 2,pow = 7;
cout << findExpo(a, pow);
}
Last updated
Was this helpful?