/*A recursive algorithm is an algorithm that calls itself.
* A recursive algorithm has Base case:
* output computed directly on small inputs
Recursive algorithms can be used to solve some problems such as Towers of Hanoi (TOH),
Inorder/Preorder/Postorder
Tree
Traversals,
DFS
of
Graph,
easily.
Recursion techniques can be also divided into following types:
1. Linear Recursion
2. Binary Recursion
3. Tail Recursion
4. Mutual Recursion
5. Nested Recursion
*
* Given Problem Statement.
*Write a program to calculate using recursion x^y ( X power y) . X and y are input.
Calculate time complexity of written code.
Write a better solution in terms of time complexity.
Calculate time complexity again for a better solution
*/
////////* Solution *//////
//As the output depends on every element of the input. O(n) or O(n*log(n)) are the best results of time complexities in this case.
//For small number of inputs the O(n log n) < O(n) ? Let n = 10 then 10*log(10) =10*1=10 which is obviously same value.
//Let n = 5 then 5*log5 = 3.49 which is obviously smaller than 5,which is better than O(5).
//Aiming for O(1) which is constant time but for the recursion problems it is difficult to achieve.
/*
*
* one big concern is the recursion depth (how many times the algorithm calls itself) .
* If the depth is small, recursive algorithms are often a good solution,and O(n*log(n)) Time complexity holds good.
* If the recursion depth is large, then the better time complexity tends to O(n),when the input is large number.
* If the recursion depth is huge, then running out of stack memory becomes a real concern,
* hence Iterative solutions (using loops) can be preferred to recursive algorithms.
*
*
*/
////////* Solution *//////
#include <chrono>
#include <sstream> // for std::stringstream
#include <iostream>
using namespace std;
using namespace std::chrono;
typedef high_resolution_clock
Clock;
typedef Clock::time_point ClockTime;
//Iterative Solution Non-Recursive [Time-Complexity O(log(n))]
long pow(int x, int n)
{
long pow = 1;
while ( n )
{
if ( n & 1 )
{
pow = pow * x;
--n;
}
x = x*x;
n = n/2;
}
return pow;
}
// Iterative solution to calculate pow(x, n) using binary operators [Time-Complexity O(log(n))]
int powB(int x, unsigned n)
{
// initialize result by 1
int pow = 1;
// do till n is not zero
while (n)
{
// if n is odd, multiply result by x
if (n & 1)
pow *= x;
// divide n by 2
n = n >> 1;
// multiply x by itself
x = x * x;
}
// return result
return pow;
}
//Tail Recursion [Time-Complexity O(n)]
float power(int x, unsigned n)
{
if (x==0)
{
return 0;
}
else if(n==0)
{
return 1;
}
else if (n>0)
{
return( x* power(x,n-1));
}
else
{
return ((1/x)*power(x,n+1));
}
}
void printExecutionTime(ClockTime start_time, ClockTime end_time);
int main(int argc , char*argv[])
{
////////////////////////////////////////////////////////
//X and y are inputs.//reading x,y input from Commandline.
cout << "Program name " <<argv[0];
std::stringstream convertx{ argv[1]};
std::stringstream convertn{ argv[2]};
int x;
unsigned int n;
if (!(convertx >> x) && !(convertn >> n)) {// do the conversion
x = 0; // if conversion fails, set x,n to a default value
n = 0;
}
////////////////////////////////////////////////////////
ClockTime start_time = Clock::now();
// power(x,n);
// pow(x,n);
powB(10,10);
////////////////////////////////////////////////////////
ClockTime end_time = Clock::now();
printExecutionTime(start_time, end_time);
}
void printExecutionTime(ClockTime start_time, ClockTime end_time)
{
auto execution_time_ns
= duration_cast<nanoseconds>(end_time - start_time).count();
auto execution_time_ms
= duration_cast<microseconds>(end_time - start_time).count();
auto execution_time_sec
= duration_cast<seconds>(end_time - start_time).count();
auto execution_time_min
= duration_cast<minutes>(end_time - start_time).count();
auto execution_time_hour
= duration_cast<hours>(end_time - start_time).count();
cout << "\nExecution Time: ";
if(execution_time_hour > 0)
cout << "" << execution_time_hour
<<
"
Hours,
";
if(execution_time_min > 0)
cout << "" << execution_time_min
% 60 << " Minutes, ";
if(execution_time_sec > 0)
cout << "" << execution_time_sec
% 60 << " Seconds, ";
if(execution_time_ms > 0)
cout << "" << execution_time_ms
% long(1E+3) << " MicroSeconds, ";
if(execution_time_ns > 0)
cout << "" << execution_time_ns
% long(1E+6) << " NanoSeconds, ";
}
//Understanding
The iterative solution
performs much better than the recursive one, the recursive solution need more memory for function call stacks so
slow.
