Below is the code for a program that uses a recursive function call to calculate
ID: 3661789 • Letter: B
Question
Below is the code for a program that uses a recursive function call to calculate a power.
/*--------------------------------------------------------
* Name: Micah Harvey
* Lab assignment: 1
* Date: May 20, 2013
* Instructor: Micah Harvey
* Description: This program calculates the value of a power of a given base using recursive function call. *--------------------------------------------------------*/
#include "msp430.h"
#include "stdio.h"
//function prototypes
long int exponential(int, int);
int main(void)
{
WDTCTL = WDTPW + WDTHOLD; //stop the watchdog timer
int value = 12; //the base
int power = 4; //the exponent, must be positive and 1 or greater
long int answer = exponential(value, power); //find the power
printf("%d raised to the %d power is %ld", value, power, answer);
return 0;
}
//This function recursively calculates a power given a base and a power long int exponential(int value, int power)
{
int answer; //the solution
if (power > 1) //if the current call has power > 1 than call again
{
power--;
answer = value*exponential(value, power);
}
else //else the power = 1 and the answer is the base
{
answer = value;
}
return answer; //return the answer
}
PROBLEM: Write a program that calculates a power and prints the results without using recursion (use a for loop instead). How many clock cycles does the demo code with recursion take to complete? How many clock cycles does your implementation take? Explain the difference.
Explanation / Answer
Here is the code to calculate power without recursion
#include "stdio.h"
//function prototypes
long int exponential(int, int);
int main(void)
{
int value = 12; //the base
int power = 4; //the exponent, must be positive and 1 or greater
long int answer = exponential(value, power); //find the power
printf("%d raised to the %d power is %ld ", value, power, answer);
return 0;
}
long exponential(int value, int power)
{
int answer,i;
answer=1; //the solution
for(i=power;i>0;i--)
{
answer=answer*value;
}
return answer; //return the answer
}
Regarding second part of the question the program without recursion has a for loop which runs power number of times i:e 10^2 runs two times and 100^2 also euns two times so the time complexity of this program depends on the power and not the base which means its time complexity is O(power).
For recursive function it can be observed that with every call to function power is decremented by 1 thus the recurence relation becomes
T(n)= T(n-1) + 1
if we solve this using substitution method it becomes
T(n-1) = T(n-2) + 2
....
...
= T(n-k) + k putting n-k=1 we get n=k
= 1+n =O(n)
which means the time complexity remains O(n)
Thus there is no difference in time complexities of recursive and non recursive functions. Both take O(n) time. However there are few recursive techniques to calculate power in O(logn) time. You can search for those algorithms also.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.