Completed Recursion Assignment

roydevashish · roydevashish · commit f1612e43bbb6 · 2025-01-25T18:57:33.000+05:30
diff --git a/F20RecursionAssignment/CheckAB.cpp b/F20RecursionAssignment/CheckAB.cpp
@@ -0,0 +1,76 @@
+/*
+Title: Check AB
+Problem statement
+Suppose you have a string, S, made up of only 'a's and 'b's. Write a recursive function that checks
+if the string was generated using the following rules:
+a. The string begins with an 'a'
+b. Each 'a' is followed by nothing or an 'a' or "bb"
+c. Each "bb" is followed by nothing or an 'a'
+If all the rules are followed by the given string, return true otherwise return false.
+
+Detailed explanation ( Input/output format, Notes, Images )
+Input format :
+String S
+
+Output format :
+'true' or 'false'
+
+Constraints :
+1 <= |S| <= 1000
+where |S| represents length of string S.
+
+Sample Input 1 :
+abb
+
+Sample Output 1 :
+true
+
+Sample Input 2 :
+abababa
+
+Sample Output 2 :
+false
+
+Explanation for Sample Input 2
+In the above example, a is not followed by either "a" or "bb", instead it's followed by "b" which
+results in false to be returned.
+*/
+
+#include <iostream>
+using namespace std;
+
+bool CheckAB(char input[]) {
+    if (input[0] == '\0') {
+        return true;
+    }
+
+    if (input[0] != 'a') {
+        return false;
+    }
+
+    int count = 0;
+    while (input[count] != '\0') {
+        if(count >= 3) {
+            break;
+        }
+        count++;
+    }
+
+    if (count >= 3 && input[0] == 'a' && input[1] == 'b' && input[2] == 'b') {
+        return CheckAB(&input[3]);
+    } else {
+        return CheckAB(&input[1]);
+    }
+}
+
+int main() {
+    char input[100];
+    bool ans;
+    cin >> input;
+    ans = CheckAB(input);
+    if(ans) {
+        cout << "true" << endl;
+    } else {
+        cout << "false" << endl;
+    }
+}
diff --git a/F20RecursionAssignment/CheckPalindromeRecursive.cpp b/F20RecursionAssignment/CheckPalindromeRecursive.cpp
@@ -0,0 +1,83 @@
+/*
+Title: Check Palindrome (Recursive)
+
+Problem statement
+Determine if a given string ‘S’ is a palindrome using recursion. Return a Boolean value of true if
+it is a palindrome and false if it is not.
+Note: You are not required to print anything, just implement the function.
+Example:
+Input: s = "racecar"
+Output: true
+Explanation: "racecar" is a palindrome.
+
+Detailed explanation ( Input/output format, Notes, Images )
+Input Format:
+The first and only line of the input contains string S.
+
+Output format:
+Return a boolean value True or False.
+
+Sample Input 1:
+abbba
+
+Sample Output 1:
+true
+
+Explanation Of Sample Input 1 :
+“abbba” is a palindrome
+
+Sample Input 2:
+abcd
+
+Sample Output 2:
+false
+
+Explanation Of Sample Input 2 :
+“abcd” is not a palindrome.
+
+Constraints:
+0 <= |S| <= 10^6
+where |S| represents the length of string S.
+*/
+
+#include<iostream>
+#include<string>
+using namespace std;
+
+bool IsPalindrome(string t) {
+    if(t.length() == 0) {
+        return true;
+    }
+
+    if(t.at(0) != t.at(t.length() - 1)) {
+        return false;
+    }
+
+    return IsPalindrome(t.substr(1, t.length() - 2));
+}
+
+class Runner {
+    string t;
+
+    public:
+        void takeInput() {
+            cin >> t;
+        }
+
+        void execute() {
+            auto ans = IsPalindrome(t);
+        }
+
+        void executeAndPrintOutput() {
+            auto ans = IsPalindrome(t);
+            ans ? cout << "true" : cout << "false";
+            cout << endl;
+        }
+};
+
+int main() {
+    Runner runner;
+    runner.takeInput();
+    runner.executeAndPrintOutput();
+    return 0;
+}
diff --git a/F20RecursionAssignment/CountZeros.cpp b/F20RecursionAssignment/CountZeros.cpp
@@ -0,0 +1,57 @@
+/*
+Title: Count Zeros
+
+Problem statement
+Given an integer N, count and return the number of zeros that are present in the given integer
+using recursion.
+
+Detailed explanation ( Input/output format, Notes, Images )
+Input Format :
+Integer N
+
+Output Format :
+Number of zeros in N
+
+Constraints :
+0 <= N <= 10^9
+
+Sample Input 1 :
+0
+
+Sample Output 1 :
+1
+
+Sample Input 2 :
+00010204
+
+Sample Output 2 :
+2
+
+Explanation for Sample Output 2 :
+Even though "00010204" has 5 zeros, the output would still be 2 because when you convert it to an
+integer, it becomes 10204.
+
+Sample Input 3 :
+708000
+
+Sample Output 3 :
+4
+*/
+
+#include<iostream>
+using namespace std;
+
+int CountZeros(int n) {
+    if(n == 0) {
+        return 0;
+    }
+    int small_output = CountZeros(n/10);
+    int output = n % 10 == 0 ? 1 + small_output : small_output;
+    return output;
+}
+
+int main() {
+    int n;
+    cin >> n;
+    cout << CountZeros(n) << endl;
+}
diff --git a/F20RecursionAssignment/GeometricSum.cpp b/F20RecursionAssignment/GeometricSum.cpp
@@ -0,0 +1,53 @@
+/*
+Title: Geometric Sum
+
+Problem statement
+Given k, find the geometric sum i.e.
+1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^k)
+Note: using recursion.
+
+Detailed explanation ( Input/output format, Notes, Images )
+Input format :
+Integer k
+
+Output format :
+Geometric sum (upto 5 decimal places)
+
+Constraints :
+0 <= k <= 1000
+
+Sample Input 1 :
+3
+
+Sample Output 1 :
+1.87500
+
+Sample Input 2 :
+4
+
+Sample Output 2 :
+1.93750
+
+Explanation for Sample Input 1:
+1+ 1/(2^1) + 1/(2^2) + 1/(2^3) = 1.87500
+*/
+
+#include<iostream>
+#include<math.h>
+#include<iomanip>
+using namespace std;
+
+float GeometricSum(int k) {
+    if(k == 0) {
+        return 1;
+    }
+
+    return 1 / pow(2, k) + GeometricSum(k - 1);
+}
+
+int main() {
+    int k;
+    cin >> k;
+    cout << fixed << setprecision(5);
+    cout << GeometricSum(k) << endl;
+}
diff --git a/F20RecursionAssignment/MultiplicationRecursive.cpp b/F20RecursionAssignment/MultiplicationRecursive.cpp
@@ -0,0 +1,50 @@
+/*
+Title: Multiplication(Recursive)
+
+Problem statement
+Given two integers M & N, calculate and return their multiplication using recursion. You can only
+use subtraction and addition for your calculation. No other operators are allowed.
+
+Detailed explanation ( Input/output format, Notes, Images )
+Input format :
+Line 1 : Integer M
+Line 2 : Integer N
+
+Output format :
+M x N
+
+Constraints :
+0 <= M <= 1000
+0 <= N <= 1000
+
+Sample Input 1 :
+3
+5
+
+Sample Output 1 :
+15
+
+Sample Input 2 :
+4
+0
+
+Sample Output 2 :
+0
+*/
+
+#include<iostream>
+using namespace std;
+
+int MultiplyNumbers(int m, int n) {
+    if(n == 0) {
+        return 0;
+    }
+
+    return MultiplyNumbers(m, n-1) + m;
+}
+
+int main() {
+    int m, n;
+    cin >> m >> n;
+    cout << MultiplyNumbers(m, n) << endl;
+}
diff --git a/F20RecursionAssignment/PairStar.cpp b/F20RecursionAssignment/PairStar.cpp
@@ -0,0 +1,64 @@
+/*
+Title: Pair Star
+
+Problem statement
+Given a string S, compute recursively a new string where identical chars that are adjacent in the
+original string are separated from each other by a "*".
+
+Detailed explanation ( Input/output format, Notes, Images )
+Input format :
+String S
+
+Output format :
+Modified string
+
+Constraints :
+0 <= |S| <= 1000
+where |S| represents length of string S.
+
+Sample Input 1 :
+hello
+
+Sample Output 1:
+hel*lo
+
+Sample Input 2 :
+aaaa
+
+Sample Output 2 :
+a*a*a*a
+*/
+
+#include<iostream>
+using namespace std;
+
+void PairStar(char input[]) {
+    if(input[0] == '\0') {
+        return;
+    }
+
+    PairStar(&input[1]);
+
+    if(input[0] == input[1]) {
+        int count = 0;
+        while(input[count] != '\0') {
+            count++;
+        }
+
+        while(count > 0) {
+            input[count+1] = input[count];
+            count--;
+        }
+
+        input[1] = '*';
+    }
+
+    return;
+}
+
+int main() {
+   char input[100];
+   cin.getline(input, 100);
+   PairStar(input);
+   cout << input << endl;
+}
diff --git a/F20RecursionAssignment/Staircase.cpp b/F20RecursionAssignment/Staircase.cpp
diff --git a/F20RecursionAssignment/StringToInteger.cpp b/F20RecursionAssignment/StringToInteger.cpp
diff --git a/F20RecursionAssignment/SumOfDigitsRecursive.cpp b/F20RecursionAssignment/SumOfDigitsRecursive.cpp
