//A recursive function calls itself, one or more times.  When a function call itself once from its body,
//this is called simple recursion.

//Demos some simple recursive functions that involve one recursive call inside the fcn
#include <iostream>
using namespace std;

//this power function computes base to the power n where n is an integer >= 1.
//recursive power function that also illustrates use of a static variable
//Recursion is not a good way to implement power = base * base * ... pow times
int power( int base, int pow)
{
   //count is a local variable declared inside the function
   //but it retains its value.  static starts the value at zero
   //this is for illustration of how a static variable works
   static int count;   //used to count now many times the function is called!  static vars start at 0
   count++;

   if (pow == 1)      //base case:  power = base ^ 1 = base
      return base;
   else
      return (base * power(base, pow-1));   //recursive call right here!
}

//computes the nth term of an arithmetic sequence
//for example, 3, 5, 7, 9, 11, 13 is an arithmetic sequence
//where 3 is the first term, and 2 is the common difference
//a is the first term and d is the common difference.  n refers to the nth term

int arithmeticTerm( int a, int d, int n)

{
    if (n == 1)
        return a;
    else
    {
        return arithmeticTerm( a, d, n-1) + d;;
    }
}

//computes the sum of an arithmetic series
int arithmeticSum( int a, int d, int n)
{
    if (n > 0 )
    {
    //NOTE if n is 1 we return a because the sole recursive call returns zero
        return (a + arithmeticSum( a + d, d, n-1));
    }
    return 0;  //for base case when we n is reduced to no terms to sum
}  //end arithmeticSum()

//computes n!  Remember n >=0 and 0! = 1
//By recursive definition, n! = n * (n-1)!
int factorial(int n)
{
    if (n == 1 || n == 0)
        return 1;
    else
        return n * factorial(n-1);
}

int main()
{
    int k = 6;
    cout << k << "!" << " = "  << factorial(k) << endl;

    int result = power(3, 5);
    cout << "3 to the 5th power is " << result << endl;

    int a = 2, d = 3, n = 6;   //2, 5, 8, 11, 14
    cout << "The " << n << "th term of 2, 5, 8, ... is "
         << arithmeticTerm(a, d, n) << endl;

    a = 1; d = 1; n = 10;
    cout << "The " << n << "th sum of 1 + 2 + 3 + ... is "
         << arithmeticSum(a, d, n) << endl;

    return 0;
}