#include <cassert>
#include <cmath>
#include <iostream>

// Mathematical recursion
//
// We have seen the general structure of a recursive
// function:
//
// return-type recursive_name( parameters... ) {
//     // Perform operations required both in the
//     // trivial and non-trivial cases...
//
//     if ( this-is-a-trivial-case ) {
//         // Solve the trivial case.
//
//         return return-value;
//     } else {
//         // Determine appropriate arguments.
//
//         // Call recursive_name(...) with those
//         // arguments.
//
//         // If necessary, use the solution or
//         // solutions to solve the current problem.
//     }
// }
//
// We will now examine several mathematical examples.
//
// These examples demonstrate different forms of
// recursion:
//
//     factorial:
//         one recursive call on n - 1
//
//     binomial:
//         two recursive calls on n - 1
//
//     Fibonacci:
//         two recursive calls on smaller arguments
//
//     power:
//         one recursive call on approximately n/2
//
// Although all four functions are recursive, their
// behavior and efficiency are very different.

// Function declarations
int main();

unsigned int factorial(
    unsigned int const n
);

unsigned int binomial(
    unsigned int const n,
    unsigned int const k
);

unsigned int fibonacci(
    unsigned int const n
);

double power(
    double    const x,
    long long const n
);

// Function definitions
int main() {
    // Factorials

    std::cout << "Factorials" << std::endl;
    std::cout << "5! = " << factorial( 5 ) << std::endl;
    std::cout << "9! = " << factorial( 9 ) << std::endl;

    std::cout << std::endl;

    // Binomial coefficients

    std::cout << "Choosing from 7 items:" << std::endl
              << "   ";

    for ( unsigned int k{ 0 }; k <= 7; ++k ) {
        std::cout << binomial( 7, k ) << " ";
    }

    std::cout << std::endl;
    std::cout << std::endl;

    // Fibonacci numbers

    std::cout << "Fibonacci numbers" << std::endl;

    std::cout << "              F(6) = "
              << fibonacci( 6 ) << std::endl;

    std::cout << "              F(7) = "
              << fibonacci( 7 ) << std::endl;

    std::cout << "F(8) = F(7) + F(6) = "
              << fibonacci( 8 ) << std::endl;

    std::cout << std::endl;

    // Powers

    std::cout << "1.1 raised to various powers"
              << std::endl;

    for ( int k{ -5 }; k <= 5; ++k ) {
        std::cout << "1.1^" << k << " = "
                  << power( 1.1, k ) << std::endl;
    }

    std::cout << std::endl;

    // 0.909090... = 0.90 repeating

    double const repeating{ 0.90909090909090909 };

    std::cout
        << "0.90 repeating raised to various powers"
        << std::endl;

    for ( int k{ -5 }; k <= 5; ++k ) {
        std::cout << "0.909090...^" << k << " = "
                  << power( repeating, k )
                  << std::endl;
    }

    return 0;
}


// unsigned int factorial( ... )
//
// The factorial function is defined recursively:
//
//     0! = 1
//
// and, for n >= 1,
//
//     n! = n (n - 1)!
//
// Thus, to calculate n!, we first calculate the
// simpler problem:
//
//     (n - 1)!
//
// and then multiply the result by n.

unsigned int factorial(
    unsigned int const n
) {
    if ( n <= 1 ) {
        // Trivial cases:
        //
        //     0! = 1
        //     1! = 1

        return 1;
    } else {
        // Solve the simpler problem.

        unsigned int const simpler_result{
            factorial( n - 1 )
        };

        // Use that solution to solve the original
        // problem.

        return n * simpler_result;
    }
}


// unsigned int binomial( ... )
//
// The binomial coefficient
//
//     C(n, k)
//
// counts the number of ways of choosing k objects
// from n objects.
//
// It satisfies:
//
//     C(n, 0) = 1
//
//     C(n, n) = 1
//
// and:
//
//     C(n, k)
//       = C(n - 1, k) + C(n - 1, k - 1)
//
// for 0 < k < n.
//
// We will additionally define:
//
//     C(n, k) = 0
//
// whenever k > n.

unsigned int binomial(
    unsigned int const n,
    unsigned int const k
) {
    if ( k > n ) {
        return 0;
    } else if ( (k == 0) || (k == n) ) {
        return 1;
    } else {
        unsigned int const result_1{
            binomial( n - 1, k )
        };

        unsigned int const result_2{
            binomial( n - 1, k - 1 )
        };

        return result_1 + result_2;
    }
}


// unsigned int fibonacci( ... )
//
// The Fibonacci numbers are defined by:
//
//     F(0) = 0
//
//     F(1) = 1
//
// and, for n >= 2,
//
//     F(n) = F(n - 1) + F(n - 2).
//
// This definition translates almost directly into
// a recursive C++ function.

unsigned int fibonacci(
    unsigned int const n
) {
    if ( n == 0 ) {
        return 0;
    } else if ( n == 1 ) {
        return 1;
    } else {
        unsigned int const result_1{
            fibonacci( n - 1 )
        };

        unsigned int const result_2{
            fibonacci( n - 2 )
        };

        return result_1 + result_2;
    }
}


// double power( ... )
//
// Calculate:
//
//     x^n
//
// recursively.
//
// We could use:
//
//     x^n = x * x^(n - 1)
//
// but there is a much better recursive definition.
//
// If n is positive and even:
//
//     x^n = (x^(n/2))^2.
//
// If n is positive and odd:
//
//     x^n = x (x^((n - 1)/2))^2.
//
// Since integer division discards the fractional
// part, n/2 gives:
//
//     n/2              if n is even,
//
//     (n - 1)/2        if n is odd.
//
// Thus, both cases can use:
//
//     power( x, n/2 ).
//
// Notice that we calculate this value ONCE, store
// the result, and then use it twice.
//
// We do NOT want:
//
//     return power( x, n/2 ) * power( x, n/2 );
//
// That would unnecessarily solve the same recursive
// problem twice.

double power(
    double    const x,
    long long const n
) {
    if ( n == 0 ) {
        return 1.0;
    } else if ( n < 0 ) {
        assert( x != 0.0 );

        return 1.0/x * power( 1.0/x, -(n + 1) );
    } else if ( (n%2) == 0 ) {
        double const result{
            power( x, n/2 )
        };

        return result*result;
    } else {
        double const result{
            power( x, n/2 )
        };

        return x*result*result;
    }
}









































// Understanding factorial
//
// Consider:
//
//     factorial( 5 )
//
// The recursive calls are:
//
//     factorial( 5 )
//         |
//         v
//     factorial( 4 )
//         |
//         v
//     factorial( 3 )
//         |
//         v
//     factorial( 2 )
//         |
//         v
//     factorial( 1 )
//
// At this point we reach the trivial case:
//
//     factorial( 1 ) = 1.
//
// The calls can now return:
//
//     factorial( 1 ) = 1
//
//     factorial( 2 ) = 2 * 1
//                    = 2
//
//     factorial( 3 ) = 3 * 2
//                    = 6
//
//     factorial( 4 ) = 4 * 6
//                    = 24
//
//     factorial( 5 ) = 5 * 24
//                    = 120.
//
//
//
// Going down and coming back up
//
// This illustrates an important feature of recursion.
//
// On the way DOWN:
//
//     factorial( 5 )
//     factorial( 4 )
//     factorial( 3 )
//     factorial( 2 )
//     factorial( 1 )
//
// we repeatedly reduce the problem.
//
// Once we reach the trivial case, the recursive calls
// begin returning.
//
// On the way UP:
//
//     1
//     2
//     6
//     24
//     120
//
// we use the solution to each smaller problem to
// construct the solution to the larger problem.
//
//
//
// One recursive call versus two
//
// Factorial makes one recursive call:
//
//                factorial(5)
//                     |
//                factorial(4)
//                     |
//                factorial(3)
//                     |
//                factorial(2)
//                     |
//                factorial(1)
//
// This produces a chain.
//
// Fibonacci is very different:
//
//                     F(5)
//                   /      \
//                F(4)      F(3)
//               /   \      /   \
//            F(3)  F(2)  F(2) F(1)
//            / \    / \    / \
//         F(2) F(1) ...
//
//
// Instead of a chain, we obtain a TREE of recursive
// calls.
//
//
//
// Repeated work
//
// Look carefully at the Fibonacci tree.
//
// The calculation of:
//
//     F(3)
//
// occurs more than once.
//
// The calculation of:
//
//     F(2)
//
// occurs even more often.
//
// As n becomes larger, the function repeatedly
// calculates the same Fibonacci numbers.
//
// This is a warning:
//
//     A recursive definition that is mathematically
//     elegant does not necessarily produce an
//     efficient recursive algorithm.
//
// We will return to this issue in later courses.
//
//
//
// Binomial coefficients
//
// The binomial function also makes two recursive
// calls:
//
//                 C(n, k)
//
//                /       \
//
//       C(n - 1, k)     C(n - 1, k - 1)
//
// This corresponds to Pascal's identity.
//
// For example:
//
//                   C(5, 2)
//
//                  /       \
//
//             C(4, 2)     C(4, 1)
//
// Again, a tree of recursive calls develops.
//
// Like the simple recursive Fibonacci function,
// this implementation may repeatedly solve the same
// smaller problems.
//
//
//
// A very different recursive strategy
//
// Now consider power(...).
//
// Suppose we want:
//
//     power( x, 16 ).
//
// We do NOT calculate:
//
//     power( x, 15 ).
//
// Instead:
//
//     power( x, 16 )
//          |
//          v
//     power( x, 8 )
//          |
//          v
//     power( x, 4 )
//          |
//          v
//     power( x, 2 )
//          |
//          v
//     power( x, 1 )
//          |
//          v
//     power( x, 0 )
//
//
// The exponent is approximately HALVED on each
// recursive call.
//
// Compare:
//
//     factorial:
//
//         n -> n - 1 -> n - 2 -> ...
//
//
// with:
//
//     power:
//
//         n -> n/2 -> n/4 -> n/8 -> ...
//
//
// This distinction will become very important.
//
//
//
// How many recursive calls?
//
// For factorial:
//
//     factorial( n )
//
// reduces n by one on each call.
//
// Therefore, there are approximately n calls.
//
// Its runtime is:
//
//     Theta(n).
//
//
// For power:
//
//     power( x, n )
//
// approximately halves n on each call.
//
// For example:
//
//     1024
//      512
//      256
//      128
//       64
//       32
//       16
//        8
//        4
//        2
//        1
//        0
//
// Only about 10 halvings are required to reduce
// 1024 to 1.
//
// Therefore, for positive n, the runtime is:
//
//     Theta(log(n)).
//
// This is the same kind of repeated halving we saw
// with binary search.
//
//
//
// Why calculate result only once?
//
// Consider the even case:
//
//     x^n = x^(n/2) * x^(n/2).
//
// It might be tempting to write:
//
//     return power( x, n/2 )
//          * power( x, n/2 );
//
// Mathematically, this is correct.
//
// Algorithmically, however, it is wasteful.
//
// Both recursive calls calculate EXACTLY the same
// value.
//
// Instead:
//
//     double const result{
//         power( x, n/2 )
//     };
//
//     return result*result;
//
// calculates the recursive result once and reuses it.
//
// This preserves the repeated-halving behavior.
//
//
//
// Remainder versus bit operations
//
// The condition:
//
//     (n%2) == 0
//
// asks whether the remainder after division by 2 is
// zero.
//
// For non-negative integers, a bit test could also
// determine whether the number is even.
//
// However, our mathematical reasoning is explicitly:
//
//     Is n divisible by 2?
//
// or:
//
//     What is the remainder when n is divided by 2?
//
// Therefore:
//
//     n%2
//
// directly expresses the idea being implemented.
//
// Code should communicate the algorithm, not merely
// produce the correct result.
//
//
//
// --------------------------------------------------
// Exercise 1: A faster recursive Fibonacci function
// --------------------------------------------------
//
// The simple recursive Fibonacci function above is
// a direct translation of:
//
//     F(n) = F(n - 1) + F(n - 2).
//
// Unfortunately, it repeatedly calculates the same
// values.
//
// There are identities that allow Fibonacci numbers
// to be calculated by approximately halving the
// argument.
//
// Implement the recursive definition:
//
//     F(0) = 0
//
//     F(1) = F(2) = 1
//
// For n = 2k:
//
//     F(2k) = F(k) * (2*F(k + 1) - F(k))
//
// For n = 2k + 1:
//
//     F(2k + 1) = F(k + 1)^2 + F(k)^2
//
//
// Once you have implemented your function, verify
// that you obtain:
//
//     0, 1, 1, 2, 3, 5, 8, 13,
//     21, 34, 55, 89, 144, ...
//
// Then compare its runtime with fibonacci(...).
//
//
//
// --------------------------------------------------
// Exercise 2: Chebyshev polynomials
// --------------------------------------------------
//
// The Chebyshev polynomials T_n are defined by:
//
//     T_0(x) = 1
//
//     T_1(x) = x
//
// and:
//
//     T_n(x)
//       = 2*x*T_(n - 1)(x) - T_(n - 2)(x).
//
// Implement:
//
//     double chebyshev_T(
//         unsigned int n,
//         double       x
//     );
//
//
// Another definition is:
//
//     T_n(x) = cos( n * acos(x) )
//
// for:
//
//     -1 <= x <= 1.
//
// The inverse cosine is implemented in C++ as:
//
//     std::acos( x )
//
// Implement this version as:
//
//     double chebyshev_Ta(
//         unsigned int n,
//         double       x
//     );
//
// Compare the results of the two functions for
// values of x between -1 and 1.
//
//
//
// --------------------------------------------------
// Exercise 3: Laguerre polynomials
// --------------------------------------------------
//
// The Laguerre polynomials L_n are defined by:
//
//     L_0(x) = 1
//
//     L_1(x) = 1 - x
//
// and:
//
//                 (2*n - 1 - x)*L_(n - 1)(x)
//     L_n(x) =    ----------------------------
//                              n
//
//                 (n - 1)*L_(n - 2)(x)
//               - ----------------------.
//                           n
//
// Equivalently:
//
//     L_n(x)
//       = ((2*n - 1 - x)*L_(n - 1)(x)
//          - (n - 1)*L_(n - 2)(x))/n.
//
// Implement:
//
//     double laguerre_L(
//         unsigned int n,
//         double       x
//     );
//
//
// --------------------------------------------------
// Exercise 4: Bell numbers
// --------------------------------------------------
//
// The Bell numbers are defined recursively by:
//
//     B(0) = 1
//
// and, for n >= 1:
//
//                 n - 1
//                 -----
//                  \
//     B(n) =        )   C(n - 1, k) B(k).
//                  /
//                 -----
//                  k = 0
//
// Implement:
//
//     unsigned int bell(
//         unsigned int n
//     );
//
// You may use binomial(...) in your implementation.
//
//
//
// --------------------------------------------------
// Exercise 5: Stirling numbers
// --------------------------------------------------
//
// The signed Stirling numbers of the first kind
// satisfy:
//
//     s(0, 0) = 1
//
//     s(n, 0) = 0       for n >= 1
//
//     s(0, k) = 0       for k >= 1
//
// and:
//
//     s(n, k)
//       = -(n - 1)*s(n - 1, k)
//         + s(n - 1, k - 1).
//
// Implement:
//
//     int stirling(
//         unsigned int n,
//         unsigned int k
//     );
//
// Why must the return type be signed?
//
//
//
// --------------------------------------------------
// Advanced exercise: recursive trapezoidal rule
// --------------------------------------------------
//
// It is possible in C++ to pass a function as an
// argument to another function.
//
// Consider:
//
//        b
//       /
//      |   f(x) dx.
//     /
//      a
//
// Define:
//
//     trapezoidal( 0, f, a, b )
//
// to be:
//
//     0.5*(f(a) + f(b))*(b - a).
//
// For n > 0, recursively divide the interval in
// half:
//
//     trapezoidal( n, f, a, b )
//
//         = trapezoidal(
//               n - 1,
//               f,
//               a,
//               0.5*(a + b)
//           )
//
//         + trapezoidal(
//               n - 1,
//               f,
//               0.5*(a + b),
//               b
//           );
//
// Implement:
//
//     double trapezoidal(
//         unsigned int const n,
//         double             f(double),
//         double       const a,
//         double       const b
//     );
//
// Test your implementation with:
//
//     trapezoidal( 10, std::exp, -4.0, 0.0 )
//
// The result should be close to:
//
//     0.98168436111.
//
// What happens to the approximation as n increases?
//
//
//
// --------------------------------------------------
// Looking ahead
// --------------------------------------------------
//
// These examples show several different recursive
// structures:
//
//     factorial:
//
//         solve one problem of size n - 1
//
//
//     Fibonacci:
//
//         solve two smaller problems
//
//
//     binomial:
//
//         solve two smaller problems
//
//
//     power:
//
//         solve one problem of approximately
//         half the size
//
//
// Later, we will apply these same ideas to algorithms
// rather than mathematical definitions.
//
// For example, selection sort can be described
// recursively:
//
//     - place the largest entry in its final
//       position;
//
//     - recursively sort the remaining entries.
//
// Insertion sort can also be described recursively:
//
//     - recursively sort the first n - 1 entries;
//
//     - insert the final entry into its correct
//       position.
//
// We can even describe binary search recursively:
//
//     - examine the middle entry;
//
//     - recursively search only the appropriate
//       half.
//
// Your lecture notes develop exactly these transitions
// from recursive sorting to binary representation,
// binary search, subset generation, and eventually
// merge sort.
//
// The central question remains the same:
//
//     What smaller version of THIS SAME PROBLEM
//     would make the current problem easier to solve?
//
// Once that question has a natural answer, recursion
// is often a natural way to express the algorithm.