I'm looking to implement a tail-recursive function to calculate the binomial coefficient of two numbers n and k. If k > n then 0 should be returned. Similarly if n == k or k == 0 it should return 1. I implemented it recursively like this but obviously this doesn't use the logic of a tail-call but I can't seem to figure out how to connect the two calculations into one recursive call. Any help would be greatly appreciated, also an explanation how to go from a normal recursive function to the tail-recursive implementation. Thanks!
public static long binomCoeffRecursive(int n, int k) {
// TODO: Implement binomCoeff recursively.
if (n == k) {
return 1;
}
if (k > n) {
return 0;
}
if (k == 0) {
return 1;
}
return binomCoeffRecursive(n-1, k-1) + binomCoeffRecursive(n - 1, k);
}
to implement a tail-recursive function
java does not apply TCR and is unlikely that it ever will; it was part of 'near future java plans' for quite a while, has since been thoroughly investigated, and the benefits do not outweigh the costs of delivering it. It complicates bookkeeping for stacks, for example - that's just one example of where there's a cost associated.
Hence, no matter what you write here, you will not end up with a TCR version because neither javac nor the JVM (java) knows what that is.
Various other languages do have it, and perhaps some that run on the JVM have it, so you could look there.
In principle you can rewrite any recursive algorithm in one that isn't recursive and uses a loop instead; when TCR can apply, that loop concept doesn't require state.
Think about it like that and that should help.
We're now going to talk hypotheticals. Let's say your program was written in qava, which is exactly like java except it does have TCR. Would your app be TCRed in qava?
No, because that is not compatible with the needs of TCR.
Imagine you rewrote this as a loop, then, when 'looping' to end up producing what binomCoeffRecursive(n-1, k-1) would produce, you need to remember someplace that you also need to figure out what binomCoeffRecursive(n - 1, k) would produce and add that.
TCR requires that your app ends in literally just return self(args). Not return self(args) + self(more args);.
That's the 'trick' you need to work on. There is no formulaic way to translate some non-TCR recursive code into TCR-able recursive code. Some jobs can't be rewritten like that all (if there's no way to avoid having state for each call and you have to do at least 2, then TCR is not possible; TCR can run forever, any algorithm that requires infinite memory thus couldn't fit in TCR unless you manage to shift the endlessly growing thing into the shape of a parameter).
As an alternative example, here is a trivial fibonacci in recursive form:
static int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
it's recursive, but not TCRable. Here's a TCRable one:
static int fib(int n) {
return fib0(n, 0, 1);
}
private static int fib0(int n, int a, int b) {
if (n == 0) return a;
if (n == 1) return b;
return fib0(n - 1, b, a + b);
}
It's completely different, appears to approach the problem mostly from the other direction (we build 'up' from 0/1 instead of building 'down'). That should do a few things: