Question

Recursion and Iteration in C++

Locate the TODO comments in the hw02.h file. These comments provide direction on what needs to be done.

// hw02.h

#ifndef CSC232_HW02_H
#define CSC232_HW02_H

// TODO: All pre-conditions must be validated using the assert function imported from the following library.
// TODO: You are not allowed to use the pow function in this assignment!
#include <cassert>

#ifndef FALSE
#define FALSE 0
#endif

#ifndef TRUE
#define TRUE !FALSE
#endif

#define USE_MAIN_INPUT_FILE FALSE
#define USE_DEMO_INPUT_FILE FALSE
#define USE_TEST_INPUT_FILE FALSE

/**
 * Custom namespace for our work in CSC232.
 */
namespace csc232
{
    using integer_t = int;
    using real_t = double;

    /**
     * An iterative function used to compute x^n for some n >= 0.
     *
     * @param x a real number whose nth power is computed
     * @param n the power used in calculating x^n
     * @return x^n for n >= 0 is returned.
     * @pre n >= 0.
     * @post Power1(x, n) > 0 if n >= 0.
     */
    real_t Power1(real_t x, integer_t n)
    {
        // TODO: Implement me iteratively, i.e., without using recursion.
        return 0;
    }

    /**
     * A recursive function used to compute x^n for some n >= 0 using the following
     * recursive formulation:
     *
     * @code{.cpp}
     * x^0 = 1
     * x^n = x * x^(n - 1) if n > 0
     * @endcode
     *
     * @param x a real number whose nth power is computed
     * @param n the power used in calculating x^n
     * @return x^n for n >= 0 is returned.
     * @pre n >= 0.
     * @post Power2(x, n) > 0 if n >= 0.
     */
    real_t Power2(real_t x, integer_t n)
    {
        // TODO: Implement me using the given recursive formulation.
        return 0;
    }

    /**
     * Determines the evenness of a number.
     *
     * @param n the number under interrogation
     * @return True is returned if the given number is even, false otherwise.
     */
    bool isEven(integer_t n)
    {
        // TODO: Implement me correctly; I should be used in Power3.
        return false;
    }

    /**
     * A recursive function used to compute x^n for some n >= 0 using the following
     * recursive formulation:
     *
     * @code{.cpp}
     * x^0 = 1
     * x^n = (x^(n/2))^2 if n > 0 and n is even
     * x^n = x * (x^(n/2))^2 if n > 0 and n is odd
     * @endcode
     *
     * @param x a real number whose nth power is computed
     * @param n the power used in calculating x^n
     * @return x^n for n >= 0 is returned.
     * @pre n >= 0.
     * @post Power3(x, n) > 0 if n >= 0.
     */
    real_t Power3(real_t x, integer_t n)
    {
        // TODO: Implement me using the given recursive formulation.
        return 0;
    }
}

#endif //CSC232_HW02_H

Answer 1

// hw02.h

#ifndef CSC232_HW02_H
#define CSC232_HW02_H

// TODO: All pre-conditions must be validated using the assert function imported from the following library.
// TODO: You are not allowed to use the pow function in this assignment!
#include <cassert>

#ifndef FALSE
#define FALSE 0
#endif

#ifndef TRUE
#define TRUE !FALSE
#endif

#define USE_MAIN_INPUT_FILE FALSE
#define USE_DEMO_INPUT_FILE FALSE
#define USE_TEST_INPUT_FILE FALSE

/**
 * Custom namespace for our work in CSC232.
 */
namespace csc232
{
    using integer_t = int;
    using real_t = double;

    /**
     * An iterative function used to compute x^n for some n >= 0.
     *
     * @param x a real number whose nth power is computed
     * @param n the power used in calculating x^n
     * @return x^n for n >= 0 is returned.
     * @pre n >= 0.
     * @post Power1(x, n) > 0 if n >= 0.
     */
    real_t Power1(real_t x, integer_t n)
    {
        // TODO: Implement me iteratively, i.e., without using recursion.
        assert(n >= 0);
        real_t ans = 1.0;
        while(n){
            if(n & 1){
                ans *= x;
            }
            x = x*x;
            n>>=1;
        }

        return ans;
    }

    /**
     * A recursive function used to compute x^n for some n >= 0 using the following
     * recursive formulation:
     *
     * @code{.cpp}
     * x^0 = 1
     * x^n = x * x^(n - 1) if n > 0
     * @endcode
     *
     * @param x a real number whose nth power is computed
     * @param n the power used in calculating x^n
     * @return x^n for n >= 0 is returned.
     * @pre n >= 0.
     * @post Power2(x, n) > 0 if n >= 0.
     */
    real_t Power2(real_t x, integer_t n)
    {
        assert(n >= 0);
        // TODO: Implement me using the given recursive formulation.
        if( n == 0 )return 1;
        return x*Power2(x,n-1);
    }

    /**
     * Determines the evenness of a number.
     *
     * @param n the number under interrogation
     * @return True is returned if the given number is even, false otherwise.
     */
    bool isEven(integer_t n)
    {
        // TODO: Implement me correctly; I should be used in Power3.
        return n&1 ? false: true;
    }

    /**
     * A recursive function used to compute x^n for some n >= 0 using the following
     * recursive formulation:
     *
     * @code{.cpp}
     * x^0 = 1
     * x^n = (x^(n/2))^2 if n > 0 and n is even
     * x^n = x * (x^(n/2))^2 if n > 0 and n is odd
     * @endcode
     *
     * @param x a real number whose nth power is computed
     * @param n the power used in calculating x^n
     * @return x^n for n >= 0 is returned.
     * @pre n >= 0.
     * @post Power3(x, n) > 0 if n >= 0.
     */
    real_t Power3(real_t x, integer_t n)
    {
        assert(n >= 0);
        // TODO: Implement me using the given recursive formulation.
        if( n == 0 ){
            return 1;
        }
        if(n % 2 == 0){   // n is even
            real_t temp = Power2(x,n/2);
            return temp*temp;
        }
        else{             // n is odd
            real_t temp = Power2(x,n/2);
            return x*temp*temp;
        }
    }
}

#endif //CSC232_HW02_H