Question

Question 2: Recursion versus Iteration
[20 marks correctness]
BLACK QUESTION (moderate collaboration allowed)
my_pow(b, e) returns b to the power of e.

count_digits(n) returns the number of digits in n, for example, 1234 => 4.

sum_digits(n) returns the sum of all digits in n, for example, 1234 => 1 + 2 + 3 + 4 = 10.

is_prime(n) returns true if n is prime, and false otherwise. The Sieve of Eratosthenes is a simple and easy to implement primality test.

[q2a-recursion]: Implement all four functions (my_pow, count_digits, sum_digits, and is_prime). You must use recursive algorithms; you may not use any iterations (loops)!
[q2b-iteration]: Implement all four functions (my_pow, count_digits, sum_digits, and is_prime). In addition, also implement fibonacci, a function that calculates the Fibonacci Number (see Assignment 1). You must use iterative algorithms (loops); you may not use any recursion!

Answer 1

-----------------------------------------------------------------------------------------------------------------------------

Please do show your support with a “ Thumbs – Up ” vote in case you find my answer useful and appreciate this effort. It truly helps me improve upon my answering abilities for the future. Thank you :-)

-----------------------------------------------------------------------------------------------------------------------------

Answer To Question No 2 - Part (a) - Recursive Implementations of All 4 Functions

-----------------------------------------------------------------------------------------------------------------------------

Your Complete Working Program Code (C++ Programming Language Format)

(kindly take note that I have briefly explained about what each and every single line of code does in the form of added programming comments right next to all such lines in the program itself)

(so please do refer to those for further detailed understanding and ease of explanation)

-----------------------------------------------------------------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;

// RECURSIVE IMPLEMENTATIONS  

long my_pow(int b, int e)  
{
    if (e == 0)       // if the power is 0
    {
        return 1;       // we can directly return 1 as any number raised to 0 is 1
    }

return (b * my_pow(b, e - 1));       // otherwise we just need to multiply the base by the 1 reduced power of the base using the recursion
}

int count_digits(int n)
{
   int digitCount = 0;       // to store the total no of digits

   if(n > 0)       // if there still are some digits left in the number
   {
       digitCount++;       // we count that digit

       return digitCount + count_digits(n / 10);       // and get the remaining result from the recursive call (by removing that last digit from the number)
   }

   return 0;
}

int sum_digits(int n)
{
   if(n == 0)       // if the number is 0 only
   {
       return 0;       // its sum will only be 0
   }

   int lastDigit = n % 10;       // otherwise we store the last digit of the number

   return lastDigit + sum_digits(n / 10);       // then we add that last digit to the remaining sum of digits of the number from which that last digit has been removed
}

bool is_prime(int n, int divisor = 2)        // the divisor is a default parameter that we use as 2 only in the starting (since 1 is not a prime no)
{
if (n < 2)        // no numbers less than 2 are prime nos
{
return false;
}

if(n == 2)       // we already know that the number 2 is a prime no
{
   return true;
}

if (n % divisor == 0)    // if this number is being completely divided by current divisor value (so divisor is its factor) hence it is not prime
{
return false;
}

if (divisor * divisor > n)        // if sqaure of current divisor is more than this number then it will always be prime
{
return true;
}
  
return is_prime(n, divisor + 1);        // otherwise we simply make a recursive call for the next number as the divisor
}

int main()
{
   cout << "\n Enter any number (n) to count the sum of digits of that number : ";
   int number; cin >> number;

   cout << "\n The sum of all the individual digits of the number (" << number << ") is : " << sum_digits(number) << endl;

   cout << "\n Enter any number (n) to count the total no of digits of that number : ";
   cin >> number;

   cout << "\n The total no of digits in the number (" << number << ") is : " << count_digits(number) << endl;

   cout << "\n Enter any number (n) to check if that number is Prime or not : ";
   cin >> number;

   if(is_prime(number))
   {
       cout << "\n The entered number (" << number << ") is a Prime Number " << endl;
   }

   else
   {
       cout << "\n The entered number (" << number << ") is not a Prime Number " << endl;
   }

   cout << "\n Enter a number (b) as the base whose power raised to an exponent (e) is to be calculated : ";
   int base; cin >> base;

   cout << "\n Enter the number (e) as the power to which the base (b) is to be raised : ";
   int exponent; cin >> exponent;

   cout << "\n The power of the base (" << base << ") raised to the exponent (" << exponent << ") is : " << my_pow(base, exponent) << endl;

   return 0;
}

-----------------------------------------------------------------------------------------------------------------------------

Screenshots of The Above Given Program Code - As Written On The IDE Screen

(for your indentation reference purposes)

-----------------------------------------------------------------------------------------------------------------------------

#include<bits/stdC++.h> using namespace std; // RECURSIVE IMPLEMENTATIONS Long my_pow(int b, int e) { if (e == 0) // if the power is o { } return 1; // we can directly return 1 as any number raised to 0 is 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 return (b * my_pow(b, e - 1)); // otherwise we just need to multiply the b } int count_digits(int n) { int digitCount = 0; // to store the total no of digits if(n > 0) // if there still are some digits left in the number digitCount++; // we count that digit 26 return digitCount + count_digits(n / 10); // and get the remaining re } return 0; } 27 28 29 30 31 32 33 34 35 36 37 38 int sum_digits(int n) { { if(n == 0) // if the number is o only { { } return 0; Il its sum will only be 0

znt sum_digits(int n) { == // if the number is 0 only if(n 0) { return 0; // its sum will only be o } int lastDigit = n % 10; // otherwise we store the last digit of t return lastDigit + sum_digits(n / 10); // then we add that last } bool is_prime(int n, int divisor = 2) // the divisor is a default p { if (n < 2) // no numbers less than 2 are prime nos 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 { } return false; if(n == 2) // we already know that the number 2 is a prime no { } return true; if (n % divisor 0) // if this number is being completely divided { } return false; if (divisor * divisor > n) // if sqaure of current divisor is mon { } return true; 67 return is prime(n, divisor + 1); // otherwise we simply make a 68 69 70 }

int main() { cout << "\n Enter any number (n) to count the sum of digits of that number : "; int number; cin >> number; cout << "\n The sum of all the individual digits of the number (" « number «< ") is : " « sum_digits(number) «< endl; cout << "\n Enter any number (n) to count the total no of digits of that number : "; cin >> number; cout << "\n The total no of digits in the number (" << number << ") is : " «count_digits(number) << endl; cout << "\n Enter any number (n) to check if that number is Prime or not : "; cin >> number; if(is_prime(number)) 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 { } cout << "\n The entered number (" << number << ") is a Prime Number" << endl; else { cout << "\n The entered number (" << number << ") is not a Prime Number " << endl; } cout << "\n Enter a number (b) as the base whose power raised to an exponent (e) is to be calculated : "; int base; cin >> base; cout << "\n Enter the number (e) as the power to which the base (b) is to be raised : "; int exponent; cin >> exponent; cout << "\n The power of the base (" « base << ") raised to the exponent (" «« exponent « ") is : " «< my_pow(base, exponent) « endl; return 0; }

-----------------------------------------------------------------------------------------------------------------------------

Screenshots of The Console Output Result Screen - For The Various Sample Test Cases

(from the actually running and working code as verified in the compiler)

-----------------------------------------------------------------------------------------------------------------------------

C:1. C:\Windows\system32\cmd.exe Enter any number (n) to count the sum of digits of that number : 174892 The sum of all the individual digits of the number (174892) is : 31 Enter any number (n) to count the total no of digits of that number : 896594745 The total no of digits in the number (896594745) is : 9 Enter any number (n) to check if that number is Prime or not : 231 The entered number (231) is not a Prime Number Enter a number (b) as the base whose power raised to an exponent (e) is to be calculated : 6 Enter the number (e) as the power to which the base (b) is to be raised : 5 The power of the base (6) raised to the exponent (5) is : 7776 C:\Users\Abhyuday Dixit\Desktop>

-----------------------------------------------------------------------------------------------------------------------------

Answer To Question No 2 - Part (b) - Iterative Implementations of All 5 Functions (Including Fibonacci)

-----------------------------------------------------------------------------------------------------------------------------

Your Complete Working Program Code (C++ Programming Language Format)

(kindly take note that I have briefly explained about what each and every single line of code does in the form of added programming comments right next to all such lines in the program itself)

(so please do refer to those for further detailed understanding and ease of explanation)

-----------------------------------------------------------------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;

// ITERATIVE IMPLEMENTATIONS  

long my_pow(int b, int e)  
{
   int result = 1;       // to hold the result value

   for(int i = 0; i < e; i++)       // we loop for exponent no of times
   {
       result *= b;       // and keep multiplying the current result with itself for those many times
   }

   return result;
}

int count_digits(int n)
{
   int digitCount = 0;       // to store the total no of digits

   while(n)       // as long as there are digits left in the number
   {
       n /= 10;           // we remove the last digit from the number
       digitCount++;       // and add 1 more to the count of digits
   }

   return digitCount;
}

int sum_digits(int n)
{
   int sum = 0;       // to hold the final result sum

   while(n)       // as long as there are digits left in the number
   {
       sum += n % 10;       // we add the last digit of the number to the current sum
       n /= 10;           // and then we remove the last digit
   }

   return sum;
}

bool is_prime(int n)        // the divisor is a default parameter that we use as 2 only in the starting (since 1 is not a prime no)
{
   for(int i = 2; i < n; i++)       // we iterate for values from 2 to the number - 1 (as all these might be potential divisors)
   {  
       if(n % i == 0)       // if any of these happens to divide the number n
       {
           return false;   // then that number cannot be a prime no
       }
   }

   return true;       // otherwise if no potential divisor in between actually divided n then it means n is actually a prime no
}

int fibonacci(int n)
{
   int fibo[n + 1];       // we create an array to store all the fibonacci numbers till n

   fibo[0] = 0, fibo[1] = 1;       // the first 2 values of the fibonacci sequence are always fixed

   for(int i = 2; i <= n; i++)       // then we iterate for all the remaining values after the first 2 values
   {
       fibo[i] = fibo[i - 1] + fibo[i - 2];       // and nth fibonacci no is the sum of the prev 2 fibonacci numbers
   }

   return fibo[n];           // then we can simply return the nth fibonacci number stored in the array
}

int main()
{
   cout << "\n Enter any number (n) to count the sum of digits of that number : ";
   int number; cin >> number;

   cout << "\n The sum of all the individual digits of the number (" << number << ") is : " << sum_digits(number) << endl;

   cout << "\n Enter any number (n) to count the total no of digits of that number : ";
   cin >> number;

   cout << "\n The total no of digits in the number (" << number << ") is : " << count_digits(number) << endl;

   cout << "\n Enter any number (n) to check if that number is Prime or not : ";
   cin >> number;

   if(is_prime(number))
   {
       cout << "\n The entered number (" << number << ") is a Prime Number " << endl;
   }

   else
   {
       cout << "\n The entered number (" << number << ") is not a Prime Number " << endl;
   }

   cout << "\n Enter a number (b) as the base whose power raised to an exponent (e) is to be calculated : ";
   int base; cin >> base;

   cout << "\n Enter the number (e) as the power to which the base (b) is to be raised : ";
   int exponent; cin >> exponent;

   cout << "\n The power of the base (" << base << ") raised to the exponent (" << exponent << ") is : " << my_pow(base, exponent) << endl;

   cout << "\n Enter the number (n) for which the nth Fibonacci value is to be found : ";
   cin >> number;

   cout << "\n The " << number << " Fibonacci number is : " << fibonacci(number) << endl;

   return 0;
}

-----------------------------------------------------------------------------------------------------------------------------

Screenshots of The Above Given Program Code - As Written On The IDE Screen

(for your indentation reference purposes)

-----------------------------------------------------------------------------------------------------------------------------

#include<bits/stdc++.h> using namespace std; // ITERATIVE IMPLEMENTATIONS Long my_pow(int b, int e) { int result = 1; // to hold the result value // we loop for exponent no of times 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 for(int i 0; i < e; i++) { result *= b; and keep multiplying the current result with } return result; } int count_digits(int n) { int digitCount = 0; // to store the total no of digits as long as there are digits left in the number 25 while(n) { n/= 10; digitCount++; // we remove the last digit from the number // and add 1 more to the count of digits } return digitCount; } 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 int sum_digits(int n) { int sum = 0; // to hold the final result sum while(n) // as long as there are digits left in the number { sum += n % 10; // we add the last digit of the number to the n/= 10; // and then we remove the last digit } 43 44 return sum; } 45 46

bool is_prime(int n) // the divisor is a default parameter that we use as 2 only in the starting (since 1 is not a prin { for(int i = 2; i<n; i++) // we iterate for values from 2 to the number - 1 (as all these might be potential divisor { if(n % i == 0) // if any of these happens to divide the number n return false; // then that number cannot be a prime no } return true; // otherwise if no potential divisor in between actually divided n then it means n is actually a prime } int fibonacci(int n) { int fibo[n + 1]; // we create an array to store all the fibonacci numbers till n fibo[@] = , fibo[1] = 1; // the first 2 values of the fibonacci sequence are always fixed for(int i = 2; i <= n; i++) // then we iterate for all the remaining values after the first 2 values { 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 fibo[i] = fiboſi - 1] + fiboſi - 2]; // and nth fibonacci no is the sum of the prev 2 fibonacci numbers pellen return fibo[n]; // then we can simply return the nth fibonacci number stored in the array polo int main() { cout << "\n Enter any number (n) to count the sum of digits of that number : "; int number; cin >> number; cout << "\n The sum of all the individual digits of the number (" << number << ") is : " «< sum_digits(number) << endl; cout << "\n Enter any number (n) to count the total no of digits of that number : "; cin >> number; cout << "\n The total no of digits in the number (" «< number « ") is : " « count_digits(number) << endl; cout << "\n Enter any number (n) to check if that number is Prime or not : "; cin >> number;

cout << "\n Enter any number (n) to count the total no of digits of that number : "; cin >> number; cout << "\n The total no of digits in the number (" << number << ") is : " « count_digits(number) << endl; cout << "\n Enter any number (n) to check if that number is Prime or not : "; cin >> number; if(is_prime (number)) { cout << "\n The entered number (" << number << ") is a Prime Number " << endl; } else { } cout << "\n The entered number (" « number << ") is not a Prime Number 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 << endl; cout << "\n Enter a number (b) as the base whose power raised to an exponent (e) is to be calculated : "; int base; cin >> base; cout << "\n Enter the number (e) as the power to which the base (b) is to be raised : "; int exponent; cin >> exponent; cout << "\n The power of the base (" «< base << ") raised to the exponent (" « exponent << ") is : " << my_pow(base, exponent) << endl; cout << "\n Enter the number (n) for which the nth Fibonacci value is to be found : "; cin >> number; cout << "\n The " << number << " Fibonacci number is : " « fibonacci(number) << endl; return 0; }

-----------------------------------------------------------------------------------------------------------------------------

Screenshots of The Console Output Result Screen - For The Various Sample Test Cases

(from the actually running and working code as verified in the compiler)

-----------------------------------------------------------------------------------------------------------------------------

C:S. C:\Windows\system32\cmd.exe Enter any number (n) to count the sum of digits of that number : 5478636 The sum of all the individual digits of the number (5478636) is : 39 Enter any number (n) to count the total no of digits of that number : 38463374 The total no of digits in the number (38463374) is : 8 Enter any number (n) to check if that number is Prime or not : 29 The entered number (29) is a Prime Number Enter a number (b) as the base whose power raised to an exponent (e) is to be calculated : 4 Enter the number (e) as the power to which the base (b) is to be raised : 9 The power of the base (4) raised to the exponent (9) is : 262144 Enter the number (n) for which the nth Fibonacci value is to be found : 23 The 23 Fibonacci number is : 28657 C:\Users\Abhyuday Dixit\Desktop>

-----------------------------------------------------------------------------------------------------------------------------