Functional interface and recursion

Question

I need to return a function that returns the result of applying the function f to its result n times. My code:

public <T> Function<T, T> fN(Function<T, T> f, int n) {
       return (T t) -> fN(f, n - 1).apply(t);
}

When I run the code, I get java.lang.StackOverflowError. How would I write this code so it passes the following tests?

Function<Integer, Integer> f1 = (x) -> x + 1;
    assertEquals(13, (int)tasks.fN(f1, 13).apply(0));
    assertEquals(2, (int)tasks.fN(f1, 1).apply(1));

Thanks for the help.

Answer 1

The non recursive, trivial approach:

public <T> Function<T, T> nonRecursiveFN(Function<T, T> f, int n) {
  return (T t) -> {
      T result = t;
      for (int i = 0; i < n; i++) {
        result = f.apply(result);
      }
      return result;
    };
}

If you need to use recursion you need some stop condition as Andreas commented. We can implement it by using internal function that takes already constructed function as argument:

public <T> Function<T, T> fN(Function<T, T> f, int n) {
  return fNInternal(f, n, (x) -> x); //we start with identity function
}

public <T> Function<T, T> fNInternal(Function<T, T> f, int remaining, Function<T, T> functionSoFar) {
  //stop condition - that's how we manage to avoid StackOverflow, you were experiencing
  if (remaining == 0) {
    return functionSoFar;
  }
  //here we apply function to the result of all previous applications
  return fNInternal(f, remaining - 1, (T t) -> f.apply(functionSoFar.apply(t)));
}