#include <iostream>
#include <cassert>

/***************************************************
 * This exercise is a little more challenging,
 * but may interest students who have mastered
 * other recursive functions.
 *
 * PROBLEM
 *
 * Having finished calculus, one of your friends
 * in the mathematics faculty describes a function
 * Cantor(x) that is continuous everywhere and
 * differentiable almost everywhere, with derivative
 * zero wherever it is differentiable.
 *
 * Nevertheless, the function satisfies
 *
 *     Cantor(0) = 0
 *     Cantor(1) = 1.
 *
 * If a function is continuous and has derivative
 * zero almost everywhere, should it not be a
 * constant function?
 *
 * You look up the Cantor function on Wikipedia:
 *
 * https://en.wikipedia.org/wiki/Cantor_function
 *
 * Looking at its graph, you notice that the
 * function on [0, 1/3] is a horizontally and
 * vertically scaled copy of the original function.
 *
 * Similarly, the function on [2/3, 1] is another
 * scaled copy, shifted upward by 1/2.
 *
 * Between these intervals, the function is
 * constant and equal to 1/2.
 *
 * Can you use this self-similarity to implement
 * the Cantor function recursively?
 *
 * Since some arguments may require indefinitely
 * many recursive calls, your implementation
 * should limit the recursion to 53 levels.
 *
 * The result will therefore be an approximation
 * to the Cantor function.
 ***************************************************/

// Function declarations
int main();

double cantor(
    double const x
);

// Function definitions
int main() {
    // Print the results to sixteen
    // significant digits.
    std::cout.precision( 16 );

    // The exact mathematical values are:
    //
    //     0.0 -> 0
    //     0.1 -> 0.2
    //     0.2 -> 0.25
    //     0.3 -> 0.4
    //     0.4 -> 0.5
    //     0.5 -> 0.5
    //     0.6 -> 0.5
    //     0.7 -> 0.6
    //     0.8 -> 0.75
    //     0.9 -> 0.8
    //     1.0 -> 1
    //
    // The arguments are represented using
    // floating-point numbers, so the computed
    // results may differ slightly.

    for ( int k{ 0 }; k <= 10; ++k ) {
        double const x{ 0.1*k };

        std::cout << cantor( x ) << std::endl;
    }

    // Test values that have exact binary
    // floating-point representations.
    assert( cantor( 0.0 ) == 0.0 );
    assert( cantor( 0.5 ) == 0.5 );
    assert( cantor( 1.0 ) == 1.0 );

    return 0;
}

double cantor(
    double const x
) {
    assert( 0.0 <= x && x <= 1.0 );

    // Your implementation goes here.

    return 0.0;
}

























// First hint:
//
// Notice that the Cantor function satisfies
//
//     Cantor(0) = 0,
//     Cantor(x) = 1/2  if 1/3 <= x <= 2/3,
//     Cantor(1) = 1.
//
// For 0 < x < 1/3, the function is a
// scaled copy of itself:
//
//     2*Cantor(x) = Cantor(3*x).
//
// Similarly, for 2/3 < x < 1, it is
// another scaled copy, shifted upward
// by 1/2:
//
//     2*(Cantor(x) - 1/2)
//         = Cantor(3*x - 2).
//
// Solving for Cantor(x), we obtain
//
//     Cantor(x) = Cantor(3*x)/2
//
// for 0 < x < 1/3, and
//
//     Cantor(x) = 1/2 + Cantor(3*x - 2)/2
//
// for 2/3 < x < 1.
//
// These equations give us a recursive
// definition of the Cantor function.
//
// However, there is still a problem:
//
// How can we limit the number of
// recursive calls?

























// Second hint:
//
// Suppose we want to allow at most 53
// levels of recursion.
//
// We cannot reliably determine how many
// recursive calls have already occurred
// simply by examining x.
//
// Instead, introduce a second parameter
// that specifies how many levels of
// recursion remain.
//
// For example, consider a function that
// applies the cosine function n times:
//
//     f(x, 0) = x,
//
//     f(x, n) = cos(f(x, n - 1)).
//
// We could implement this using
//
//     double cos_n(
//         double const x,
//         unsigned int const n
//     ) {
//         if ( n == 0 ) {
//             return x;
//         } else {
//             return std::cos(
//                 cos_n( x, n - 1 )
//             );
//         }
//     }
//
// Each recursive call decreases n by one,
// guaranteeing that the recursion stops.
//
// For the Cantor function, you can use
// a similar approach.
//
// Implement a helper function
//
//     double cantor(
//         double const x,
//         unsigned int const n
//     );
//
// The public function cantor(x) simply
// calls this helper with n = 53.
//
// When n reaches zero, return x as an
// approximation to the remaining
// Cantor function.
//
// Returning x is not exact, but the
// contribution of the remaining function
// has already been scaled by 2^(-53).
//
// Be sure to handle the constant interval
// and the endpoints before making another
// recursive call.

























// Here is one solution:

/*
double cantor(
    double       const x,
    unsigned int const n
);

double cantor(
    double const x
) {
    assert( 0.0 <= x && x <= 1.0 );

    return cantor( x, 53 );
}

double cantor(
    double       const x,
    unsigned int const n
) {
    assert( 0.0 <= x && x <= 1.0 );

    if ( x == 0.0 ) {
        return 0.0;
    } else if ( x == 1.0 ) {
        return 1.0;
    } else if ( 1.0/3.0 <= x && x <= 2.0/3.0 ) {
        return 0.5;
    } else if ( n == 0 ) {
        // Approximate the remaining
        // Cantor function by x.
        return x;
    } else if ( x < 1.0/3.0 ) {
        return 0.5*cantor( 3.0*x, n - 1 );
    } else {
        return 0.5
             + 0.5*cantor( 3.0*x - 2.0, n - 1 );
    }
}
*/