Recursion and optimizations

As seen in last instalment calculating Fibonacci numbers using naïve implementation creates binary tree of calls and the same subtrees are calculated over and over again what has huge impact on performance. One of ways to improve performance is caching previous results and that is called memoization. In old Java we will do something like this:

private static final Map<Long, Long> memo = new HashMap<>(); static { memo.put(0L, 0L); memo.put(1L, 1L); } public static void main(String[] args) { System.out.println(fibonacci(0)); System.out.println(fibonacci(43)); System.out.println(fibonacci(92)); } static long fibonacci(long n) { if (memo.get(n) == null) { memo.put(n, fibonacci(n - 1) + fibonacci(n - 2)); } return memo.get(n); }

We initialize map container with result for first two cases, to avoid if statements, and later if there is mapping for input, we return it and if there is no mapping for input we calculate it. Without help from memoization naïve implementation will choke and die on input 92. Using Java 8 it becomes even shorter, here is just fibonacci method, everything else is the same:

public static long fibonacci(long n) { return memo.computeIfAbsent(n, m -> fibonacci(m - 1) + fibonacci(m - 2)); }

Signature of computeIfAbsent is the following:

default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)

where n is key and function is interface Function, we defined it recursively and compiler was not upset. Memoization brings speed but takes space.
How do we turn tail call version into lambda. We can do this for example:

static Function<Long, Long> y = new Function<Long, Long>() { private long tailRecursive(long a, long b, long n) { if (n > 0) { return tailRecursive(b, a + b, n - 1); } return a; } public Long apply(Long x) { return tailRecursive(0, 1, x); } }; public static long fibonacciFunctional(long n) { return y.apply(n); }

what does not look very functional and very Java 8 because it is anonymous class. Another more Java 8 option is declaring functional interface with sufficient number of arguments:

interface FewArgs<T, U, V, R> { public R apply(T t, U u, V v); } static FewArgs<Long, Long, Long, Long> tailRecursive; static { tailRecursive = (a, b, n) -> { if (n > 0) return tailRecursive.apply(b, a + b, n - 1); return a; }; }

We also can not initialize it in one go, declare class field and initialize it, it must be done from some of host class methods.
Remaining optimization ideas are strictly related to Fibonacci numbers and not applicable to most other recursions. There is not so obvious way to generate Fibonacci numbers:

| 1 1 | n      | F(n+1) F(n)   |
| 1 0 |    =   | F(n)   F(n-1) |

If we rise matrix on the left, lets call it A, to power of n-1 its A[0][0] is Fn. We can prove it using induction. For n=1 our claim obviously holds, now

| F(n+1) F(n)   |   | 1 1 |
| F(n)   F(n-1) | x | 1 0 | =

|F(n+1)+F(n) F(n+1)+0|   |F(n+2) F(n+1)|
|F(n)+F(n−1) F(n)+0  | = |F(n+1) F(n)  |

Instead of doing chain multiplication we can do squaring and reduce number of multiplications to log(n) multiplications.

| F(n+1) F(n)   |2
| F(n)   F(n-1) | =

| F(n+1)^2+F(n)^2         F(n+1)*F(n)+F(n)*F(n−1)|
| F(n)*F(n+1)+F(n−1)*F(n) F(n)^2+F(n−1)^2        |

From where one can pull more interesting relations.
Here is illustrative implementation of this idea:

private static long square(long n) { if(n==0) return n; long test = n-1; ArrayList<long> arr = new ArrayList<>(); long[] A = new long[]{ 1, 1, 1, 0 }; long[] result = new long[4]; System.arraycopy(A, 0, result, 0, 4); while(test>1){ if(test%2!=0) arr.add(1L); else arr.add(0L); test/=2; } for(int i=arr.size()-1;i>-1;i--){ result=multiply(result,result); if(arr.get(i)==1) result=multiply(result,A); } return result[0]; } private static long[] multiply(long[] a, long[] b) { long[] result = new long[]{ a[0] * b[0] + a[1] * b[2], a[0] * b[1] + a[1] * b[3], a[2] * b[0] + a[3] * b[2], a[2] * b[1] + a[3] * b[3] }; return result; } public static void main(String[] arg) { for (int i = 0; i < 93; i++) { System.out.println("F(" + i + ") = " + square(i)); } }

That ArrayList is mapper, consumes some additional space but makes things easier to debug.