#include <cassert>
#include <cstddef>
#include <iostream>

// Introduction to recursion
//
// Until now, when we wanted to repeat an operation,
// we generally used a loop:
//
//     for ( ... ) {
//         ...
//     }
//
// There is another way to repeat an operation:
//
//     recursion.
//
// A recursive function is a function that calls
// itself.
//
// This may initially sound strange. If a function
// calls itself, why does it not continue calling
// itself forever?
//
// The key is that each recursive call must solve a
// SMALLER version of the original problem.
//
// Eventually, the problem must become sufficiently
// small that it can be solved immediately without
// another recursive call.
//
// This is called the trivial case or base case.
//
// The general structure of a recursive function is:
//
// 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 to the
//         // smaller problem to solve the current
//         // problem.
//     }
// }
//
// We will begin with a simple algorithmic example.
//
// Given an array:
//
//     4.2   7.1   3.8   9.5
//
// print its entries from left to right:
//
//     4.2 7.1 3.8 9.5
//
// We already know how to do this with a loop.
//
// Here, however, we will solve the problem
// recursively.

// Function declarations
int main();

void print_array(
    double      const array[],
    std::size_t const capacity
);

// Function definitions
int main() {
    double const data[5]{
        4.2, 7.1, 3.8, 9.5, 2.6
    };

    std::cout << "Printing five entries:" << std::endl;

    print_array( data, 5 );

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

    std::cout << "Printing the last three entries:"
              << std::endl;

    print_array( data + 2, 3 );

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

    std::cout << "Printing one entry:" << std::endl;

    print_array( data, 1 );

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

    std::cout << "Printing an empty array:"
              << std::endl;

    print_array( nullptr, 0 );

    std::cout << std::endl;

    return 0;
}


// void print_array( ... )
//
// @param array
//     An array of doubles whose entries are to be
//     printed.
//
// @param capacity
//     The number of entries in the array.
//
// @algorithm
//     If the array is empty, there is nothing to
//     print.
//
//     Otherwise:
//
//       - print the first entry;
//
//       - recursively print all of the remaining
//         entries.
//
//     Each recursive call therefore considers an
//     array containing one fewer entry.

void print_array(
    double      const array[],
    std::size_t const capacity
) {
    assert( (capacity == 0) || (array != nullptr) );

    if ( capacity == 0 ) {
        // Trivial case:
        //
        // There are no entries to print.

        return;
    } else {
        // Non-trivial case:
        //
        // Print the first entry.

        std::cout << array[0] << " ";

        // Now solve the smaller problem:
        //
        // Print the remainder of the array.
        //
        //     array + 1
        //
        // points to the second entry of the current
        // array.
        //
        // There is also one fewer entry remaining.

        print_array( array + 1, capacity - 1 );
    }
}









































// What just happened?
//
// Suppose we call:
//
//     print_array( data, 4 );
//
// where:
//
//     data:
//
//         4.2   7.1   3.8   9.5
//
//
// The problem is:
//
//     print:
//
//         4.2   7.1   3.8   9.5
//
// This is not the trivial case.
//
// Therefore, print:
//
//     4.2
//
// and recursively solve the smaller problem:
//
//     print:
//
//               7.1   3.8   9.5
//
//
// We can picture this as:
//
//     print_array( data, 4 )
//
//         print 4.2
//
//         |
//         v
//
//     print_array( data + 1, 3 )
//
//         print 7.1
//
//         |
//         v
//
//     print_array( data + 2, 2 )
//
//         print 3.8
//
//         |
//         v
//
//     print_array( data + 3, 1 )
//
//         print 9.5
//
//         |
//         v
//
//     print_array( data + 4, 0 )
//
//         print nothing
//
//         return
//
//
// At this point, there is no further recursive call.
//
// The recursion stops.
//
//
//
// Why does the recursion stop?
//
// Look at the second argument:
//
//     print_array( data,     4 )
//
//     print_array( data + 1, 3 )
//
//     print_array( data + 2, 2 )
//
//     print_array( data + 3, 1 )
//
//     print_array( data + 4, 0 )
//
// Each recursive call decreases capacity by one.
//
// Therefore:
//
//     4 -> 3 -> 2 -> 1 -> 0
//
// Eventually:
//
//     capacity == 0
//
// and we reach the trivial case.
//
//
//
// This gives us two essential requirements for
// recursion.
//
// 1. There must be a trivial case.
//
//    In this example:
//
//        capacity == 0
//
//    means there is nothing to print.
//
//
// 2. Each recursive call must move us closer to the
//    trivial case.
//
//    In this example:
//
//        capacity - 1
//
//    gives us a smaller problem.
//
//
//
// What would happen if we wrote:
//
//     print_array( array + 1, capacity );
//
// instead?
//
// The capacity would remain:
//
//     4 -> 4 -> 4 -> 4 -> ...
//
// We would never reach:
//
//     capacity == 0.
//
// The recursion would continue until the program
// eventually failed.
//
//
//
// The recursive idea
//
// A recursive algorithm asks:
//
//     Can I solve this problem by:
//
//         doing a small amount of work
//
//     and then:
//
//         solving a smaller version of the
//         same problem?
//
//
// For printing an array:
//
//     print this array
//
// becomes:
//
//     print the first entry
//
// and then:
//
//     print the remaining array.
//
//
// In pictures:
//
//     [ A B C D E ]
//
// becomes:
//
//     print A
//
//         +
// 
//     [ B C D E ]
//
// and:
//
//     [ B C D E ]
//
// becomes:
//
//     print B
//
//         +
//
//     [ C D E ]
//
// and so on.
//
//
//
// Compare this with a loop
//
// We could write the same algorithm using:
//
//     for ( std::size_t k{ 0 };
//           k < capacity;
//           ++k ) {
//         std::cout << array[k] << " ";
//     }
//
// For this particular problem, the loop is simpler.
//
// That is important.
//
// Recursion is NOT automatically better than
// iteration.
//
// We are using this example because the algorithm is
// already familiar, allowing us to concentrate on
// the new idea:
//
//     a function can call itself to solve a smaller
//     version of the same problem.
//
//
//
// Runtime
//
// Suppose there are n entries.
//
// The function prints one entry and then recursively
// processes the remaining n - 1 entries:
//
//     n
//     |
//     v
//     n - 1
//     |
//     v
//     n - 2
//     |
//     v
//     ...
//     |
//     v
//     2
//     |
//     v
//     1
//     |
//     v
//     0
//
// There are approximately n recursive calls.
//
// Each call performs a constant amount of work.
//
// Therefore, the runtime is:
//
//     Theta(n).
//
// This is the same asymptotic runtime as the loop.
//
//
//
// Recursion also uses memory
//
// There is one additional difference.
//
// When one function calls another function, the
// calling function has not yet finished.
//
// Thus:
//
//     print_array( data, 4 )
//
// waits while:
//
//         print_array( data + 1, 3 )
//
// waits while:
//
//             print_array( data + 2, 2 )
//
// waits while:
//
//                 print_array( data + 3, 1 )
//
// waits while:
//
//                     print_array( data + 4, 0 )
//
// returns.
//
// Then the previous call returns.
//
// Then the previous call returns.
//
// And so on.
//
// The computer must remember these unfinished
// function calls.
//
// For this example, the number of active calls can
// grow proportionally to n.
//
// We will discuss this in more detail later.
//
//
//
// A small experiment
//
// What happens if we reverse these two operations:
//
//     std::cout << array[0] << " ";
//
//     print_array( array + 1, capacity - 1 );
//
//
// That is, suppose we instead write:
//
//     print_array( array + 1, capacity - 1 );
//
//     std::cout << array[0] << " ";
//
//
// Trace:
//
//     4.2   7.1   3.8   9.5
//
// What gets printed?
//
//
//
// Questions:
//
// 1. What is the trivial case in print_array(...)?
//
// 2. Why is that case trivial?
//
// 3. What is the smaller problem solved by the
//    recursive call?
//
// 4. How do we know that each recursive call moves
//    closer to the trivial case?
//
// 5. What would happen if capacity were not reduced
//    in the recursive call?
//
// 6. How many recursive calls are required for an
//    array containing n entries?
//
// 7. What is the runtime of this algorithm?
//
// 8. Is recursion preferable to a loop for this
//    particular problem?
//
// 9. Why are we nevertheless using recursion here?
//
// 10. What happens if the recursive call is made
//     BEFORE array[0] is printed?
//
//
//
// The important idea:
//
// A recursive function does not need to solve the
// entire problem immediately.
//
// Instead, it can:
//
//     solve one small part
//
// and then trust that:
//
//     the same function can solve a smaller version
//     of the remaining problem.
//
// Eventually, that smaller problem becomes trivial.
//
// That is the fundamental idea behind recursion.
//
// Later, we will use exactly this idea in algorithms
// where recursion is much more natural and powerful.