Recursion if Condition

Question

The following is an implementation of the problem from spoj:- http://www.spoj.com/problems/COINS/

#include <stdio.h>

#define ll long long

ll arr[100000];

ll max(ll n)
{
    if(n < 49999)// Doubt
    {
        if(!arr[n])
            return arr[n] = max(n/2) + max(n/3) + max(n/4);
        else
            return arr[n];
    }
    else
        return max(n/2) + max(n/4) + max(n/3);
}


int main()
{
    ll n, c = 0, i;

    for(i = 0; i < 12; i++) // Also why 12 when the input can be <12
    {
        arr[i] = i;
    }

    while(scanf("%lld", &n) != EOF)
    {
        printf("%lld\n", max(n));

    }

    return 0;
}

Why does the if condition contain n<49999?

Answer 1

without having examined each possibility, other than the first 20+ values and the max and min values:

MY expectation is

the first 12 entries in the arr[] are pre-calculated to help reduce the depth of a recursion however the dollar value is not the same as the calculated value for those first 12 entries.

for coin values <= 49999, check to see if value already calculated, if not then break the coin into the /2 /3 /4 values and recurse each of those resulting values.

This limit value (49999) could be extended to 100000 as that is the available size of the arr[] array.

the presetting and the saving into the arr[] array are to help reduce execution time taken and the depth of the recursion.

the use of the array is so any previously calculated values (in the posted code, up to 49999) can be immediately returned by the max() function, without further recursion.

I would modify the code slightly for better documentation and robustness and faster execution as follows:

#include <stdio.h>
#include <stdint.h>

#define MAX_ARRAY_LEN (100000)

uint32_t arr[ MAX_ARRAY_LEN ] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};

uint32_t max(uint32_t n)
{
    if(n < MAX_ARRAY_LEN)
    { // value of 'n' within the range of the learning array arr[]

        if(!arr[n] && n)
        { // then learning array arr[] not yet set
            return arr[n] = max(n/2) + max(n/3) + max(n/4);
        }

        else
        { // else learning array arr[] already set for 'this' value of 'n'
            return arr[n];
        }
    }

    else
    { // value of 'n' is greater than the learning array arr[]
        return max(n/2) + max(n/4) + max(n/3);
    }
} // end function: max


int main( void )
{
    uint32_t n;

    int status;
    while( (status = scanf("%u", &n)) == 1 && EOF != status)
    {
        if( 1000000000 >= n)
        {
            printf("%u\n", max(n) );
        }

        else
        {
            printf(" invalid value entered, must be in the range 0...1 000 000 000\n");
        } // end if
    } // end while

    return 0;
} // end function: main