0

So I've got a home task to write a recursive function searching for Binomial coefficient. My answer does not pass the time test. How can I improve it?

Code is here:

int newton ( int N, int K ){
    if ( N < K )
    return 0;

    if ( N > 33 || K > 33 )
    return -1;

    if ( N == K || K == 0 )
    return 1;
    if ( K > N / 2 )
    K = N - K;


    return ( newton ( N - 1, K - 1 ) + newton ( N - 1, K ) );
}
Vladimir Komar
  • 45
  • 5
  • 1
    Are you required to implement via recurrence relation of Pascal's triangle or is any other algorithm allowed, too, as long as it is recursive? – Aconcagua Dec 16 '19 at 17:54
  • Please don't add parentheses around return values: `return` is not a function. In worst case, you can even produce dangling references that way: `decltype(auto) f() { int n = 7; return (n); }` (admitted that's quite specific, but still: you can!). – Aconcagua Dec 16 '19 at 17:59
  • @Aconcagua: Uhg, C++. Do you have a citation for how that happens? – R.. GitHub STOP HELPING ICE Dec 16 '19 at 18:19
  • 1
    @R.. [dcl.type.decltype/1.5](http://eel.is/c++draft/dcl.type.decltype#1.5). For `return n;`, rule 1.3 applies instead. – Daniel Langr Dec 16 '19 at 18:42
  • Off-topic: What's expected output for `newton(-1, -2)`??? As binominal coefficients are not defined for negative inputs, allowing these is pretty meaningless. So better choice for signature would be `unsigned int newton(unsigned int, unsigned int)` – self-documenting that negative input is illegal (well, one could still pass, they'd get converted to very large values, but that's user's error, not yours...). – Aconcagua Dec 17 '19 at 10:04

2 Answers2

3

return ( newton ( N - 1, K - 1 ) + newton ( N - 1, K ) );

These recursive calls will recalculate the result for the same inputs multiple times. You can see this by writing out the call tree for moderate initial values for N and K, for example newton(5, 3).

One way to reduce the number of calls is to use what is called "memoization". The basic concept is that you store a result for a given set of inputs the first time it is calculated. Then the next time those inputs are passed in, you can look up the value and return it immediately without calculating it again.

I suggest you google "memoization" to learn more about it.

Code-Apprentice
  • 81,660
  • 23
  • 145
  • 268
  • Memoization might solve the ridiculously constrained problem OP has, but conceptually it's even more ridiculous. – R.. GitHub STOP HELPING ICE Dec 16 '19 at 18:21
  • @R.. Can you elaborate what you mean by that? – Code-Apprentice Dec 16 '19 at 18:40
  • It's throwing added complexity at a fundamentally wrong solution to make it work. Conceptually, the only reason one should want recursion (vs a closed form solution) is for the mathematical understanding of the problem, or for some sort of dogmatic/ideological purity about replicating that in programming. But introducing memoization is going in the opposite direction of that kind of functional purity towards nasty implementation hacks. – R.. GitHub STOP HELPING ICE Dec 16 '19 at 19:14
  • @R.. Feel free to post your own answer suggesting a better solution. – Code-Apprentice Dec 16 '19 at 20:37
  • I'm not sure there is a good solution within the problem constraints. I'm not trying to detract from your answer as a valid answer to the problem, just trying to convey to OP that the problem is not reasonable and that solving it the way your answer suggests *in a real-world setting outside an artificially-constrained problem* (as opposed to using the right non-recursive solution) would be an awful idea. – R.. GitHub STOP HELPING ICE Dec 16 '19 at 20:39
  • @R.. Agreed that the closed formula is ideal. For pedagogical purposes this is a pretty decent example to show the pitfalls of recursive solutions to problems. – Code-Apprentice Dec 16 '19 at 20:58
  • 1
    I think it's a great example of that until you get into trying to solve the problem while sticking with recursion, rather than realizing recursion is the problem. – R.. GitHub STOP HELPING ICE Dec 16 '19 at 21:20
2

I checked and I think your conditions have problem. Check here:

int newton ( int N, int K ){
    if ( N == K || K == 0 )
        return 1;

    return ( newton ( N - 1, K - 1 ) + newton ( N - 1, K ) );
}

I checked this function with newton(33,16) and it works without timeout. I think your other conditions cause some problem too.

In addition, memorization (some people may call it dynamic programming) can improve answer. Here is with memorization:

int newton_imp(int N, int K, int* mem, int size){
    if ( N == K || K == 0 )
        return 1;

    if ( mem[(N-1)*size + K-1] == 0)
        mem[(N-1)*size + K-1] = ( newton_imp(N - 1, K - 1, mem, size) + newton_imp(N - 1, K, mem, size) );
    return mem[(N-1)*size + K-1];
}

int newton(int N, int K) {
    int res = -1;
    int* mem = calloc(N*K, sizeof(*mem));
    if (mem) {
        res = newton_imp(N, K, mem, K);
        free(mem);
    }
    return res;
}
Afshin
  • 8,839
  • 1
  • 18
  • 53
  • I think memoization and dynamic programming are different things. There are certainly some similarities that your comment has helped me realize. See [this post](https://cs.stackexchange.com/questions/99513/dynamic-programming-vs-memoization) for a discussion of the similarities and differences. – Code-Apprentice Dec 16 '19 at 17:43
  • @Code-Apprentice there are some people that argue with their difference but I have seen that they are used interchangeably. – Afshin Dec 16 '19 at 17:48
  • In this particular case, DP is a great solution since the problem is defined by a recurrence relation. – Code-Apprentice Dec 16 '19 at 17:56
  • 1
    @Code-Apprentice yes, my 2 codes have huge difference in running time for `newton(33,16)`. I think from almost immediate answer to 4-5 second running time on wandbox. – Afshin Dec 16 '19 at 17:58
  • Thank you so much! – Vladimir Komar Dec 16 '19 at 20:13