// Arup Guha
// 6/7/2023
// Examples of Recursion for SI@UCF CP Class

using namespace std;
#include <iostream>
typedef long long ll;

int fact(int n);
ll pow(ll b, ll e);
void towers(int n, int s, int e);
ll modpow(ll b, ll e, ll m);

int main() {

    // Test some things out.
    cout << fact(8) << endl;
    cout << pow(4, 20) << endl;
    towers(5,1,3);
    cout << modpow(1234567, 998877656, 1000000007) << endl;
    return 0;
}

// Returns n!
int fact(int n) {

    // Base case.
    if (n == 0) return 1;

    // Recursive break down.
    return n*fact(n-1);
}

// Returns b raised to the power e.
ll pow(ll b, ll e) {

    // Base case.
    if (e == 0) return 1;

    // Typical recursive break down.
    return b*pow(b,e-1);
}

// Prints out the solution to the Towers of Hanoi with n disks starting at tower s, moving to
// tower e. Towers must be numbered 1, 2, 3 and s and e must be distinct.
void towers(int n, int s, int e) {

    // We only have work to do if n is positive.
    if (n > 0) {

        // Move the rest of the disks to the "other" tower.
        towers(n-1, s, 6-s-e);

        // Move the bottom disk to the right place.
        cout << "Moving disk " << n << " from tower " << s << " to tower " << e << endl;

        // Move the rest of the disks to their final tower.
        towers(n-1, 6-s-e, e);
    }
}

// Return b raised to the power e mod m.
ll modpow(ll b, ll e, ll m) {

    // Base case.
    if (e == 0) return 1%m;

    // Savings are here. Raise to e/2 power and then square.
    if (e%2 == 0) {
        ll tmp = modpow(b, e/2, m);
        return (tmp*tmp)%m;
    }

    // Usual breakdown.
    return (b*modpow(b,e-1,m))%m;
}