CODEWITHSUNDEEP
c++functionrecursionoptimization
Just_a_newbie
Just_a_newbie

Reputation: 99

Optimizing a recursive function

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

Upvotes: 2

Views: 1524

Answers (3)

Hermann D&#246;ppes
Hermann D&#246;ppes

Reputation: 1373

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.

Upvotes: 6

Tahlil
Tahlil

Reputation: 2721

Your recursion needs a memoization to avoid repetitive calculation. And no need for the second and third parameter of the recursion. I have updated and put explanation on your code. Let me know if you have any confusion.

#include <iostream>
#include <string.h>
#define INF 999999

using namespace std;

int cal(int inp);
int mem[502];
int main (void)
{
    //Gets input
    int n;
    cin >> n;

    //initialzing the array for using with memoization
    memset(mem,-1,sizeof(mem));

    //Calls the function
    //Prints the best result
    cout << cal(n) << endl;

    return 0;
}

//returns the minimum quantity of sum operations to get inp.
int cal(int inp)
{
    //Breaks recursion if it finds an answer.
    //Return cost 0. As in this stage no processing was done.
    if(!inp)
        return 0;

    // Returning infinite cost for invalid case.
    if(inp < 0)
        return INF;

    int _ret = mem[inp];

    // If already visited here before then no need to calcuate again.
    // Just return previous calculation. This is called memoisation.
    // If not visited then _ret would have equal to -1.
    if(_ret >=0 )
        return _ret;

    _ret = INF;

    //Tries every combination and takes the minimum cost.
    _ret = min(_ret, cal(inp-13)+1);
    _ret = min(_ret,cal(inp-6)+1);
    _ret = min(_ret,cal(inp-2)+1);
    _ret = min(_ret,cal(inp-1)+1);

    // Updating the value so that can be used for memoization.
    mem[inp] = _ret;

    return _ret;
}

This will also work for larger numbers. Complexity is 4*n.

Upvotes: 2

tchelidze
tchelidze

Reputation: 8308

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

Upvotes: 4

Related Questions