Optimizing a recursive function

Question

I'm creating a program that returns the least quantity of sums required to get to a number (n) using only 1, 2, 6 and 13. It works perfectly for small values of n, but once n gets to values like 200 it takes the program too much time to calculate the result.

Therefore, I have two questions:

1. Is there any way to make the recursion faster?

2. Should I avoid using recursion and use a loop instead?

Here's the commented code:

#include <iostream>
#define MAX 500000

using namespace std;

void cal(int inp, int &mini, int counter = 0);

int main (void)
{
    //Gets input
    int n;
    cin >> n;

    //Defines mini as the MAX result we can get
    int mini = MAX;

    //Calls the function
    cal(n, mini);

    //Prints the best result
    cout << mini << endl;

    return 0;
}

void cal(int inp, int &mini, int counter)
{
    //Breaks recursion if it finds an answer
    if(!inp)
    {
        if(counter<mini) mini = counter;
        return;
    }

    //Breaks recursion if the input is negative
    //or the counter is more than the best result
    else if((inp<0) || (counter>mini)) return;

    //Counts amount of recursions
    counter++;

    //Tries every combination
    cal(inp-13, mini, counter);
    cal(inp-6, mini, counter);
    cal(inp-2, mini, counter);
    cal(inp-1, mini, counter);

    return;
}

Thank you

Answer 1

The problem is your brute force. Let me suggest something better:

Preliminaries: If you have two 1s, it is always better to use a 2. If you have three 2s, it is better to use a 6. If you have thirteen 6s, it is better to use six thirteens.

So the any admissable sum will always look like n = 13m+k where k is written as a sum of 1, 2, and 6. With the preliminaries, we know that for the optimal sum k will never exceed 1+2*2+12*6 = 77. (The reverse doesn't hold. Not any number below 78 is best written without 13s of course.) So brute forcing those is good enough. You can then use a lookup table.

This could still be optimized further, but it should not break down at 200.

Assuming you have found your first 77 entries (which can be optimized as well) you can do this (still unoptimized ;-):

int num_13 = ((n-78) / 13) + 1;
int sum_length = MAX;
for (i = num_13; i*13 < n; i++) {
    int tmp = entries_77[n-i*13]+i;
    if (tmp < sum_length) {
        num_13 = i;
        sum_length = tmp;
    }
}

I would be even quicker to compile an array for the equivalence classes modulo 13, since for any given equivalence class any number exceeding 78 will have the same k.

Answer 2

You can use DP (Dynamic Programming) approach to solve your problem. It's well known Coins Problem