#include <cassert>
#include <iostream>

// Discovering a formula from a recurrence
//
// A recursive definition does not have to describe
// a function such as factorial or Fibonacci.
//
// We can also use recursion to describe how much
// work an algorithm performs.
//
// Consider the function T(n) defined by:
//
//             /
//            (   1                 n = 1
//             )
//     T(n) = <
//             )
//            (   T(n - 1) + 1     n > 1
//             \
//
// Author the function T(n), asserting that:
//
//     n >= 1.
//
// Then, in main(), write a loop that calculates:
//
//     T(1), T(2), T(3), ...
//
// until you can determine a formula for T(n).
//
// Do not immediately try to manipulate the formula
// algebraically.
//
// First, calculate some values and look for a
// pattern.

// Function declarations
int main();

unsigned int T(
    unsigned int const n
);

// Function definitions
int main() {
    // Your implementation here.

    return 0;
}


// unsigned int T( ... )
//
// @param n
//     A positive integer.
//
// @returns
//     The value defined recursively by:
//
//         T(1) = 1
//
//     and:
//
//         T(n) = T(n - 1) + 1
//
//     for n > 1.

unsigned int T(
    unsigned int const n
) {
    assert( n >= 1 );

    // Your implementation here.

    return 1;
}














































// Hint
//
// Begin by printing:
//
//     T(1)
//     T(2)
//     T(3)
//     ...
//
// For example:
//
//     for ( unsigned int k{ 1 };
//           k <= 10;
//           ++k ) {
//         std::cout << "T(" << k << ") = "
//                   << T( k )
//                   << std::endl;
//     }
//
// What pattern do you observe?
//
// Once you think you know the formula for T(n), test
// your formula against all of the values printed by
// the program.














































// Solution

/*
int main() {
    for ( unsigned int k{ 1 };
          k <= 10;
          ++k ) {
        std::cout << "T(" << k << ") = "
                  << T( k )
                  << std::endl;
    }

    return 0;
}

unsigned int T(
    unsigned int const n
) {
    assert( n >= 1 );

    if ( n == 1 ) {
        return 1;
    } else {
        return T( n - 1 ) + 1;
    }
}
*/














































// What is the pattern?
//
// Running the program produces:
//
//     T(1)  = 1
//     T(2)  = 2
//     T(3)  = 3
//     T(4)  = 4
//     T(5)  = 5
//     T(6)  = 6
//     T(7)  = 7
//     T(8)  = 8
//     T(9)  = 9
//     T(10) = 10
//
// The pattern appears to be:
//
//     T(n) = n.
//
//
//
// Why?
//
// Start with the recurrence:
//
//     T(n) = T(n - 1) + 1.
//
// Apply the definition again:
//
//     T(n)
//       = T(n - 1) + 1
//
//       = (T(n - 2) + 1) + 1
//
//       = T(n - 2) + 2.
//
// Apply it again:
//
//     T(n)
//       = T(n - 3) + 3.
//
// Continuing:
//
//     T(n)
//       = T(n - 4) + 4
//
//       = ...
//
// Eventually we reach the trivial case:
//
//     T(1) = 1.
//
// How many times did we add 1 while going from
// n down to 1?
//
//     n - 1
//
// times.
//
// Therefore:
//
//     T(n)
//       = T(1) + (n - 1)
//
//       = 1 + (n - 1)
//
//       = n.
//
//
//
// Why do we care?
//
// At first, this recurrence may seem unnecessarily
// complicated.
//
// After all:
//
//     T(n) = n
//
// is much simpler than:
//
//     T(n) = T(n - 1) + 1.
//
// The important point is that the RECURRENCE may be
// much easier to discover from an algorithm.
//
// Suppose an algorithm processes n entries.
//
// It performs one operation on the first entry and
// then performs the same algorithm on the remaining
// n - 1 entries.
//
// We might naturally describe its work as:
//
//     work for n entries
//
//         = work for n - 1 entries
//
//         + one additional operation.
//
// That gives:
//
//     T(n) = T(n - 1) + 1.
//
// The recurrence describes HOW the algorithm works.
//
// Solving the recurrence tells us HOW MUCH work the
// algorithm performs.
//
//
//
// A concrete example
//
// Consider our recursive function for printing an
// array:
//
//     print_array( array, capacity );
//
// It prints one entry and then recursively prints
// the remaining entries:
//
//     print one entry
//
//         +
// 
//     print n - 1 entries.
//
// If T(n) counts the number of entries printed, then:
//
//     T(1) = 1
//
// and:
//
//     T(n) = T(n - 1) + 1.
//
// Solving this recurrence gives:
//
//     T(n) = n.
//
// Thus, printing n entries requires work
// proportional to n.
//
// We describe this as:
//
//     Theta(n).
//
//
//
// Be careful when deciding what T(n) counts
//
// Suppose instead that we ask:
//
//     How many additions are required to add
//     n numbers?
//
// For one number:
//
//     17
//
// no addition is required.
//
// Thus:
//
//     T(1) = 0.
//
// For two numbers:
//
//     17 + 23
//
// one addition is required.
//
// For three:
//
//     17 + 23 + 41
//
// two additions are required.
//
// Therefore, if T(n) counts ADDITIONS:
//
//             /
//            (   0                 n = 1
//             )
//     T(n) = <
//             )
//            (   T(n - 1) + 1     n > 1
//             \
//
// and the solution is:
//
//     T(n) = n - 1.
//
//
//
// This distinction is important.
//
// The recurrence:
//
//     T(n) = T(n - 1) + 1
//
// does not by itself tell us exactly what is being
// counted.
//
// We must also know the trivial case.
//
// Compare:
//
//     T(1) = 1
//
// gives:
//
//     T(n) = n.
//
// while:
//
//     T(1) = 0
//
// gives:
//
//     T(n) = n - 1.
//
//
//
// For asymptotic analysis, however:
//
//     n
//
// and:
//
//     n - 1
//
// grow at the same rate.
//
// Both are:
//
//     Theta(n).
//
// This is one reason asymptotic analysis is useful.
//
// If we are interested in how the work grows for
// large inputs, the difference of one operation is
// usually unimportant.
//
//
//
// Recursion versus recurrences
//
// These two words sound similar, but they describe
// different ideas.
//
// RECURSION:
//
//     A function calls itself to solve a smaller
//     version of the same problem.
//
//
// RECURRENCE:
//
//     A mathematical equation defines a quantity in
//     terms of that quantity for a smaller input.
//
//
// A recursive algorithm often leads naturally to a
// recurrence describing its runtime.
//
// For example:
//
//     recursive algorithm:
//
//         solve one entry
//
//         recursively solve n - 1 entries
//
//
//     recurrence:
//
//         T(n) = T(n - 1) + 1
//
//
//     solution:
//
//         T(n) = n
//
//
//     asymptotic runtime:
//
//         Theta(n)
//
//
//
// We can therefore think of the process as:
//
//     ALGORITHM
//
//         |
//         | describe its work
//         v
//
//     RECURRENCE
//
//         |
//         | solve the recurrence
//         v
//
//     FORMULA
//
//         |
//         | examine its growth
//         v
//
//     ASYMPTOTIC RUNTIME
//
//
// For this first example:
//
//     recurrence:
//
//         T(n) = T(n - 1) + 1
//
//              |
//              v
//
//     formula:
//
//         T(n) = n
//
//              |
//              v
//
//     growth:
//
//         Theta(n)
//
//
//
// Questions:
//
// 1. What is the trivial case for T(n)?
//
// 2. Why must we assert that n >= 1?
//
// 3. What happens to the argument on each recursive
//    call?
//
// 4. How do we know that the recursion eventually
//    reaches the trivial case?
//
// 5. What values do you obtain for T(1) through
//    T(10)?
//
// 6. What formula appears to describe T(n)?
//
// 7. How can we derive that formula by repeatedly
//    substituting the recurrence into itself?
//
// 8. If T(n) counts one operation for every item
//    processed, what does T(n) = n tell us?
//
// 9. If T(n) instead counts the additions required
//    to add n numbers, why should the trivial case
//    be T(1) = 0?
//
// 10. Why are both n and n - 1 described as
//     Theta(n)?
//
//
//
// This example is intentionally straightforward.
//
// The purpose is not to make:
//
//     T(n) = n
//
// seem mysterious.
//
// The purpose is to introduce a technique:
//
//     1. Describe the work recursively.
//
//     2. Calculate a few values.
//
//     3. Look for a pattern.
//
//     4. Determine a formula.
//
//     5. Use that formula to describe how the
//        amount of work grows.
//
// The next recurrences will be only slightly more
// complicated.
//
// The same process will still apply.