recursion

// 1

/*
 * Returns the binomial coefficient n "choose" k
 * MUST BE RECURSIVE
 */
int nChooseK(int n, int k) {
    if (k == 0 || k == n) {
        return 1;
    } else {
        return nChooseK(n - 1, k - 1) + nChooseK(n - 1, k);
    }
}


// 2

/*
 * You must find recursively the number of ways that a given integer can be expressed as the sum
 * of the unique, natural numbers.
 *
 * Example: the number of ways to get the number 6 by combining unique natural numbers is 4.
 * 1) 1 + 5 = 6
 * 2) 2 + 4 = 6
 * 3) 6 = 6
 * 4) 1 + 2 + 3 = 6
 */

int powerSumHelper(int n, int start) {
    if (n == 0) return 1;
    if (n < 0 || start > n) return 0;

    int x = powerSumHelper(n - start, start + 1);
    int y = powerSumHelper(n, start + 1);
    return x + y;
}

int powerSum(int n) {
    return powerSumHelper(n, 1);
}


// 3

#include <iostream>
using namespace std;

void move(int disk, char source, char destination) {
    cout << "Move disk " << disk << " from rod " << source << " to rod " << destination << endl;
}

void towersOfHanoi(int n, char source, char destination, char auxiliary) {
    if (n == 1) {
        move(n, source, destination);
        return;
    }

    towersOfHanoi(n - 1, source, auxiliary, destination);
    move(n, source, destination);
    towersOfHanoi(n - 1, auxiliary, destination, source);
}

// int main() {
//     // cout << powerSum(6) << endl;
//     // cout << powerSum(8) << endl;
//     towersOfHanoi(3, 'A', 'C', 'B');

//     return 0;
// }