Answer in C++, Fully Commented Question 1 (5 marks) Purpose: To explore the natu
ID: 3686537 • Letter: A
Question
Answer in C++, Fully Commented
Question 1 (5 marks)
Purpose: To explore the nature of recursive functions in C/C++. To introduce the concept of
computational efficiency.
Open up Eclipse and create a new project called a9q1. Copy and paste from file A9Q1start.cpp. There are two recursive functions defined, named powers() and superpowers().
Build the program, and run it.
Make sure that x = 2.0, and y = 6 in main().
In the program's code, uncomment the lines indicated for "Task 3".
Build and run the program again. Record how many times the powers() function was
called, and how many times the superpowers() function was called.
Change y=16 in main() (keep x=2.0 --but it doesn't matter really ).
Repeat step 4, for y=16.
Now WITHOUT running the program, make a guess about how many times powers()
would appear if y=100? Make the same guess about superpowers() for y=100.
Answer the following questions: Explain in general terms the difference in behaviour
between powers() and superpowers() when they are solving the same problem. Which method is better, and why?
What to hand in:
1. A text document called a9q1.txt (.rtf, and .doc are also okay) with the answers to the
above questions in them.
//============================================================================
// Name : A9Q1.cpp
// Author : CMPT 111
// Description : Exploring different ways to do recursion
//============================================================================
// INSTRUCTIONS:
// 1. Create a new Eclipse project and copy/paste this code into it.
// 2. Save, build, and run.
// 3. There are some lines of code in the functions powers and superpowers that are
// "commented out". Uncomment them all, save, build and run.
// 4. Answer the questions on A9Q1.
#include <iostream>
using namespace std;
// calculate x^y using simple recursion
// Note: if parameter y is negative, program will crash!
float powers(float x, int y)
{
// TODO: Task 3; uncomment the following line
// cout << "this delegate's task: powers(" << x << "," << y << ")" << endl;
float result;
if (y == 0)
{
result = 1;
}
else
{
float delegatedAnswer = powers(x,y-1);
result = x * delegatedAnswer;
}
return result;
}
// calculate x^y using simple recursion
// here we exploit a mathematical property to speed things up!
// if y is even:
// x^y = [x^(y/2)]^2
//
// if y is odd, use the normal formula
// x^y = x*[x^(y-1)]
// Note: if parameter y is negative, program will crash!
float superpowers(float x, int y)
{
// TODO: Task 3; uncomment the following line
// cout << "this delegate's task: superpowers(" << x << "," << y << ")" << endl;
float result;
if (y==0)
{
result = 1;
}
else if (y % 2 == 0)
{
float delegatedAnswer = superpowers(x,y/2); // x^(y/2)
result = delegatedAnswer*delegatedAnswer;
}
else
{
float delegatedAnswer = superpowers(x,y-1); // x*[x^(y-1)]
result = x * delegatedAnswer;
}
return result;
}
int main() {
float x = 2.0;
int y = 6;
cout << "***Starting powers calculation***" << endl;
// set the calculation apart to make exploration with the debugger easier
float example1 = powers(x,y);
cout << "The output from powers(" << x << "," << y << "): " << example1 << endl;
cout << "***Starting superpowers calculation***" << endl;
// set the calculation apart to make exploration with the debugger easier
float example2 = superpowers(x,y);
cout << "The output from superpowers(" << x << "," << y << "): " << example2 << endl;
cout << "Bye now!" << endl;
return 0;
}
Explanation / Answer
//============================================================================
// Name : A9Q1.cpp
// Author : CMPT 111
// Description : Exploring different ways to do recursion
//============================================================================
// INSTRUCTIONS:
// 1. Create a new Eclipse project and copy/paste this code into it.
// 2. Save, build, and run.
// 3. There are some lines of code in the functions powers and superpowers that are
// "commented out". Uncomment them all, save, build and run.
// 4. Answer the questions on A9Q1.
#include <iostream>
using namespace std;
// calculate x^y using simple recursion
// Note: if parameter y is negative, program will crash!
float powers(float x, int y)
{
cout << "this delegate's task: powers(" << x << "," << y << ")" << endl;
float result;
if (y == 0)
{
result = 1;
}
else
{
float delegatedAnswer = powers(x,y-1);
result = x * delegatedAnswer;
}
return result;
}
// calculate x^y using simple recursion
// here we exploit a mathematical property to speed things up!
// if y is even:
// x^y = [x^(y/2)]^2
//
// if y is odd, use the normal formula
// x^y = x*[x^(y-1)]
// Note: if parameter y is negative, program will crash!
float superpowers(float x, int y)
{
cout << "this delegate's task: superpowers(" << x << "," << y << ")" << endl;
float result;
if (y==0)
{
result = 1;
}
else if (y % 2 == 0)
{
float delegatedAnswer = superpowers(x,y/2); // x^(y/2)
result = delegatedAnswer*delegatedAnswer;
}
else
{
float delegatedAnswer = superpowers(x,y-1); // x*[x^(y-1)]
result = x * delegatedAnswer;
}
return result;
}
int main() {
float x = 2.0;
int y = 100;
cout << "***Starting powers calculation***" << endl;
// set the calculation apart to make exploration with the debugger easier
float example1 = powers(x,y);
cout << "The output from powers(" << x << "," << y << "): " << example1 << endl;
cout << "***Starting superpowers calculation***" << endl;
// set the calculation apart to make exploration with the debugger easier
float example2 = superpowers(x,y);
cout << "The output from superpowers(" << x << "," << y << "): " << example2 << endl;
cout << "Bye now!" << endl;
return 0;
}
/*
* for y = 6, power() function called 7 times, superpowers() called 5 times
*
* for y = 16, power() function called 16 times, superpowers() called 6 times
*
* for y = 100, power() function called 100 times, superpowers() called 10 times
*
* */
For y = 16
Output:
***Starting powers calculation***
this delegate's task: powers(2,16)
this delegate's task: powers(2,15)
this delegate's task: powers(2,14)
this delegate's task: powers(2,13)
this delegate's task: powers(2,12)
this delegate's task: powers(2,11)
this delegate's task: powers(2,10)
this delegate's task: powers(2,9)
this delegate's task: powers(2,8)
this delegate's task: powers(2,7)
this delegate's task: powers(2,6)
this delegate's task: powers(2,5)
this delegate's task: powers(2,4)
this delegate's task: powers(2,3)
this delegate's task: powers(2,2)
this delegate's task: powers(2,1)
this delegate's task: powers(2,0)
The output from powers(2,16): 65536
***Starting superpowers calculation***
this delegate's task: superpowers(2,16)
this delegate's task: superpowers(2,8)
this delegate's task: superpowers(2,4)
this delegate's task: superpowers(2,2)
this delegate's task: superpowers(2,1)
this delegate's task: superpowers(2,0)
The output from superpowers(2,16): 65536
Bye now!
superpower() method is better than power() method, because it takes log(n) time to compute whereas power() takes O(n) time