CODEWITHSUNDEEP
javarecursiontail-recursion
Jonas Jacob Biermann
Jonas Jacob Biermann

Reputation: 139

Tail-Recursive Binomial Coefficient Function in Java

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);
    }

Upvotes: 0

Views: 101

Answers (3)

rzwitserloot
rzwitserloot

Reputation: 103823

TCR in java.

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.

Your specific code

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:

  • make intuitive to you that there is no simple 'recipe' for turning non-TCR recursive algorithms into TCR recursive algorithms.
  • What TCR algorithms look like.

Upvotes: 2

teapot418
teapot418

Reputation: 2578

If you want an efficient implementation that does not grow the stack, you are out of luck, java does not do the tail-call optimization as explained by @rzwitserloot.

If you just want to satisfy the 'last call to itself' rule for whatever reason, you could do something like

public static long binomCoeffRecursive(int n, int k) {
    return binomCoeffRecursiveInternal(n, k, 0);
}

private static long binomCoeffRecursiveInternal(int n, int k, long offset) {
    if (n == k) {
        return 1+offset;
    }
    if (k > n) {
        return offset;
    }
    if (k == 0) {
        return 1+offset;
    }
    offset += binomCoeffRecursiveInternal(n-1, k-1, 0);
    return binomCoeffRecursiveInternal(n - 1, k, offset);
}

which is a mix of ordinary and tail recursion.

Upvotes: 0

Louis Wasserman
Louis Wasserman

Reputation: 198471

You can't get a tail recursive implementation with that formula because you cannot "connect the two calculations into one recursive call" like you're hoping for. Tail recursion is only possible when there's only one recursive call, and you can't fuse them together.

There are tail-recursive implementations for calculating binary coefficients, however, that only use one recursive call. An iterative implementation suitable for conversion to tail recursion can be found, for example, in Guava. (Disclosure: I wrote it.) That depends on the multiplicative formula.

Upvotes: 1

Related Questions