Problem: ​
Assume you are given blocks of size 1, 2 and 3. Write a C++ program to recursively count the number of ways in which a tower of size n can be built with these blocks, such that exactly k of the blocks are of size 1.

 

Example: If n = 4 and k = 2, then there are three possible ways in which the tower can be built. If L1, L2, L3 represent the lego blocks of sizes 1, 2, 3 respectively, then the tower of size 4 can be built using the following block arrangements:

 

L1, L1, L2

L1, L2, L1

L2, L1, L1

 

HINT: If T(n, k) represents the number of ways in which a tower of size n can be built with exactly k 1-sized blocks, then T(n, k) can be recursively written as:

 

T(n,k) = T(n-1, k-1) + T(n-2, k) + T(n-3, k)

where

T(n-1, k-1) represents the number of ways in which a size 1 block is used first, i.e., the number of ways to build a tower of size (n-1) containing exactly (k-1) blocks of size 1.
T(n-2, k) represents the number of ways in which a size 2 block is used first, i.e., the number of ways to build a tower of size (n-2) containing exactly k blocks of size 1.
T(n-3, k) represents the number of ways in which a size 3 block is used first, i.e., the number of ways to build a tower of size (n-3) containing exactly k blocks of size 1.
Use this recurrence formula to implement the recursive function. Think carefully about the base cases.

 

Note: 

You need to solve this question using recursion only. 
Solutions using any other approach will not be considered and any testcases that pass will be negated i.e. will be given a 0. 
 

Input Format

A line containing two positive integers n and k, separated by a space
 

Output Format

An integer representing the count of valid ways to build a tower.
 

Assumptions on Input

Assume that the value of n entered by the user will be between 1 and 15, both inclusive
Assume that the value of k entered by the user will be between 1 and 10, both inclusive
If it is not possible to construct a tower, return 0.

Student submission:
#include <iostream>
using namespace std;

int recursiveFunction(int n, int k){
    if(n < 0){
        return 0;
    }

    if(n == 0){
        return 1;
    }

    if(n != 0 && k == 0){
        if(n % 3 == 0 && n % 2 == 0){
            int out = 0;
            for(int i = 0; i < (n/3); i++){
                for(int j = 0; j < (n/2); j++){
                    if(n == 3*i + 2*j) out++;
                }
            }
            return out+2;
        }
        if(n % 3 == 0){
            return 1;
        }
        if(n % 2 == 0){
            return 1;
        }
        else{
            int out = 0;
            for(int i = 0; i < (n/3); i++){
                for(int j = 0; j < (n/2); j++){
                    if(n == 3*i + 2*j) out++;
                }
            }
            return out;
        }
    }

    return recursiveFunction(n-1, k-1) + recursiveFunction(n-2, k) + recursiveFunction(n-3, k);
}

int main(){
    int n, k;
    cin >> n >> k;
    cout << recursiveFunction(n, k) << endl;
}

Grading criterion: Implementation of the Recursive Relationship
Rating A: Correctly implements the recursive call as defined in the hint. 

Rating B: some issue
Rating C: major issue
Rating D: 0
Assigned grade: A