[ FP with Java ] Ch4 - Recursion, corecursion, and memoization - Part2

Composing a huge number of functions 
In chapter 2, you saw that you’ll overflow the stack if you try to compose a huge number of functions. The reason is the same as for recursion: because composing functions results in methods calling methods. Having to compose more than 7,000 functions may be something you don’t expect to do soon. On the other hand, there’s no reason not to make it possible. If it’s possible, someone will eventually find something useful to do with it. And if it’s not useful, someone will certainly find something fun to do with it. 

Let's write a function, composeAll, taking as its argument a list of functions from T to T and returning the result of composing all the functions in the list (Exercise 4.6). To get the result you want, you can use a right fold, taking as its arguments the list of functions, the identity function (obtained by a call to the statically imported Function.identity() method), and the compose method written in chapter 2: 

view plaincopy to clipboardprint?

1. static <T> Function<T, T> composeAll(List<Function<T, T>> list) {  
2.     return foldRight(list, Identity(), x -> y -> x.compose(y));  
3. }  

To test this method, you can statically import all the methods from your Collection-Utilities class (developed in chapter 3) and write the following: 

view plaincopy to clipboardprint?

1. package test.fp.utils;  
2.   
3. import java.util.ArrayList;  
4. import java.util.List;  
5. import org.junit.Test;  
6. import fp.utils.Function;  
7. import static fp.utils.Function.*;  
8. import static org.junit.Assert.*;  
9.   
10. public class TestFunction {  
11.     @Test  
12.     public void testComposeAll() {        
13.         List> list = new ArrayList<>();  
14.         for (int i = 0; i < 500; i++) {  
15.           list.add(x -> x + 1);  
16.         }  
17.         int result = composeAll(list).apply(0);  
18.         assertEquals(result, 500);  
19.     }  
20. }  

Running this code displays 500, as it’s the result of composing 500 functions incrementing their argument by 1. What happens if you replace 500 with 10,000? You’ll get a StackOverflowException. The reason should be obvious. By the way, on the machine I used for this test, the program breaks for a list of 2,856 functions. 

Let's fix this problem so you can compose an (almost) unlimited number of functions (Exercise 4.7). The solution to this problem is simple. Instead of composing the functions by nesting them, you have to compose their results, always staying at the higher level. This means that between each call to a function, you’ll return to the original caller. If this isn’t clear, imagine the imperative way to do this: 

view plaincopy to clipboardprint?

1. T y = identity;  
2.   
3. for (Function<T, T> f : list) {  
4.   y = f.apply(y);  
5. }  

Here, identity means the identity element of the given function. This isn’t composing functions, but composing function applications. At the end of the loop, you’ll get a T and not a Function. But this is easy to fix. You create a function from T to T, which has the following implementation: 

view plaincopy to clipboardprint?

1. static <T> Function<T, T> composeAll(List> list) {  
2.     return x -> {  
3.         T y = x;  // A copy of x is made while it must be effectively final.  
4.         for(Function<T,T> f:list)  
5.         {  
6.             y = f.apply(y);  
7.         }  
8.         return y;  
9.     };        
10. }  

You can’t use x directly, because it would create a closure, so it should be effectively final. That’s why you make a copy of it. This code works fine, except for two things. The first is that it doesn’t look functional. This can be fixed easily by using a fold. It can be either a left fold or a right fold: 

view plaincopy to clipboardprint?

1. static <T> Function<T, T> composeAllViaFoldLeft(List<Function> list) {    
2.       return x -> foldLeft(list, x, a -> b -> b.apply(a));    
3. }  
4.   
5. static <T> Function<T, T> composeAllViaFoldRight(List> list) {    
6.       return x -> foldRight(list, x, a -> a::apply);    
7. }  

You’re using a method reference for the composeAllViaFoldRight implementation. This is equivalent to the following: 

view plaincopy to clipboardprint?

1. static <T> Function<T, T> composeAllViaFoldRight(List<Function<T, T>> list) {  
2.   return x -> FoldRight.foldRight(list, x, a -> b -> a.apply(b));  
3. }  

If you have trouble understanding how it works, think about the analogy with sum. When you defined sum, the list was a list of integers. The initial value (x here) was 0; a and b were the two parameters to add; and the addition was defined as a + b. Here, the list is a list of functions; the initial value is the identity function; a and b are functions; and the implementation is defined as b.apply(a) or a.apply(b). In the foldLeft version, b is the function coming from the list, and a is the current result. In the foldRight version, a is the function coming from the list, and b is the current result. 

To see this in action, refer to the unit tests in the code available from the book’s site (https://github.com/fpinjava/fpinjava). 

The code has two problems, and you fixed only one. Can you see another problem and fix it (Exercise 4.8)? The second problem isn’t visible in the result because the functions you’re composing are specific. They are, in fact, a single function from integer to integer. The order in which they’re composed is irrelevant. Try to use the composeAll method with the following function list: 

view plaincopy to clipboardprint?

1. package fp.ch4;  
2.   
3. import fp.utils.Function;  
4. import static fp.utils.Function.*;  
5. import static fp.utils.CollectionUtilities.*;  
6.   
7. public class TestP22_1 {  
8.     public static void main(String args[])  
9.     {  
10.         Function<String, String> f1 = x -> "(a" + x + ")";  
11.         Function<String, String> f2 = x -> "{b" + x + "}";  
12.         Function<String, String> f3 = x -> "[c" + x + "]";  
13.         System.out.println(composeAllViaFoldLeft(list(f1, f2, f3)).apply("x"));  
14.         System.out.println(composeAllViaFoldRight(list(f1, f2, f3)).apply("x"));  
15.     }  
16. }  

Execution output: 

[c{b(ax)}] // f3(f2(f1("x")))
(a{b[cx]}) // f1(f2(f3("x"))) which is correct and expected!

We’ve implemented andThenAll rather than composeAll! To get the correct result, you first have to reverse the list: 

view plaincopy to clipboardprint?

1. static <T> Function<T, T> composeAllViaFoldLeft(List<Function<T, T>> list) {  
2.     return x -> foldLeft(reverse(list), x, a -> b -> b.apply(a));  
3. }  
4.   
5. static <T> Function<T, T> composeAllViaFoldRight(List<Function<T, T>> list) {  
6.     return x -> foldRight(list, x, a -> a::apply);  
7. }  
8.   
9. static <T> Function<T, T> andThenAllViaFoldLeft(List<Function<T, T>> list) {  
10.     return x -> foldLeft(list, x, a -> b -> b.apply(a));  
11. }  
12.   
13. static <T> Function<T, T> andThenAllViaFoldRight(List<Function<T, T>> list) {  
14.     return x -> foldRight(reverse(list), x, a -> a::apply);  
15. }  

Using memoization 
In previous section, you implemented a function to display a series of Fibonacci numbers. One problem with this implementation of the Fibonacci series is that you want to print the string representing the series up to f(n), which means you have to compute f(1), f(2), and so on, until f(n). But to compute f(n), you have to recursively compute the function for all preceding values. Eventually, to create the series up to n, you’ll have computed f(1) n times, f(2) n – 1 times, and so on. The total number of computations will then be the sum of the integers 1 to n. Can you do better? Could you possibly keep the computed values in memory so you don’t have to compute them again if they’re needed several times? 

Memoization in imperative programming 
In imperative programming, you wouldn’t even have this problem, because the obvious way to proceed would be as follows: 

view plaincopy to clipboardprint?

1. package fp.ch4;  
2.   
3. import java.math.BigInteger;  
4.   
5. public class TestP23_1 {  
6.     public static String fibo(int limit)  
7.     {  
8.         switch(limit)  
9.         {  
10.         case 0:  
11.             return "0";  
12.         case 1:  
13.             return "0, 1";  
14.         case 2:  
15.             return "0, 1, 1";  
16.         default:  
17.             BigInteger fibo1 = BigInteger.ONE;  
18.             BigInteger fibo2 = BigInteger.ONE;  
19.             BigInteger fibonacci;  
20.             StringBuilder builder = new StringBuilder("0, 1, 1");  
21.             for(int i=3; i<=limit; i++)  
22.             {  
23.                 fibonacci = fibo1.add(fibo2);  
24.                 builder.append(", ").append(fibonacci);  
25.                 fibo1 = fibo2; fibo2 = fibonacci;                 
26.             }  
27.             return builder.toString();  
28.         }  
29.     }  
30.       
31.     public static void main(String args[])  
32.     {  
33.         System.out.printf("Fibo(10)=%s\n", fibo(10));  
34.     }  
35. }  

Although this program concentrates most of the problems that FP is supposed to avoid or to solve, it works and is much more efficient than your functional version. The reason is memoization. Memoization is a technique that keeps in memory the result of a computation so it can be returned immediately if you have to redo the same computation in the future. Applied to functions, memoization makes the functions memorize the results of previous calls, so they can return the results much faster if they’re called again with the same arguments. 

This might seem incompatible with functional principles, because a memoized function maintains a state. But it isn’t, because the result of the function is the same when it’s called with the same argument. (You could even argue that it’s more the same, because it isn’t computed again!) The side effect of storing the results must not be visible from outside the function. In imperative programming, this might not even be noticed. Maintaining state is the universal way of computing results, so memoization isn’t even noticed. 

Memoization in recursive functions 
Recursive functions often use memoization implicitly. In your example of the recursive Fibonacci function, you wanted to return the series, so you calculated each number in the series, leading to unnecessary recalculations. A simple solution is to rewrite the function in order to directly return the string representing the series. 

Let's Write a stack-safe tail recursive function taking an integer n as its argument and returning a string representing the values of the Fibonacci numbers from 0 to n, separated by a comma and a space (Exercise 4.9). One solution is to use StringBuilder as the accumulator. StringBuilder isn’t a functional structure because it’s mutable, but this mutation won’t be visible from the outside. Another solution is to return a list of numbers and then transform it into a String. This solution is easier, because you can abstract the problem of the separators by first returning a list and then writing a function to turn the list into a comma-separated string. 

The following listing shows the solution using List as the accumulator: 
Listing 4.5. Recursive Fibonacci with implicit memoization 

view plaincopy to clipboardprint?

1. public static String fibo(int number)  
2. {  
3.     List list = fibo_(list(BigInteger.ZERO), BigInteger.ONE, BigInteger.ZERO, BigInteger.valueOf(number)).eval();  
4.     return MakeString(list, ", ");  
5. }  
6.   
7. public static  TailCall> fibo_(List acc, BigInteger acc1, BigInteger acc2, BigInteger x)  
8. {  
9.     return x.equals(BigInteger.ZERO)  
10.             ? ret(acc)  
11.             : x.equals(BigInteger.ONE)  
12.                 ? ret(append(acc, acc1.add(acc2)))  
13.                 : sus(() -> fibo_(append(acc, acc1.add(acc2)), acc2, acc1.add(acc2), x.subtract(BigInteger.ONE)));  
14. }  
15.   
16. public static  String MakeString(List list, String sep)  
17. {  
18.     return list.isEmpty()  
19.             ? ""  
20.             : tail(list).isEmpty()  
21.                 ? head(list).toString()  
22.                 : head(list) + foldLeft(tail(list), "", x -> y -> x + sep + y);  
23. }  

Recursion or corecursion? 
This example demonstrates the use of implicit memoization. Don’t conclude that this is the best way to solve the problem. Many problems are much easier to solve when twisted. So let’s twist this one. Instead of a suite of numbers, you could see the Fibonacci series as a suite of pairs (tuples). Instead of trying to generate this, 

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

you could try to produce this: 

(0, 1), (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), (13, 21), ...

In this series, each tuple can be constructed from the previous one. The second element of tuple n becomes the first element of tuple n + 1. The second element of tuple n + 1 is equal to the sum of the two elements of tuple n. In Java, you can write a function for this: 

view plaincopy to clipboardprint?

1. x -> new Tuple<>(x._2, x._1.add(x._2));  

You can now replace the recursive method with a corecursive one: 

view plaincopy to clipboardprint?

1. public static String fiboCorecursive(int number) {  
2.     Tuple seed = new Tuple<>(BigInteger.ZERO, BigInteger.ONE);  
3.     Function, Tuple> f = x -> new Tuple<>(x._2,  
4.             x._1.add(x._2));  
5.     List list = map(fp.utils.List.iterate(seed, f, number), x -> x._1);  
6.     return MakeString(list, ", ");  
7. }  

The iterate method takes a seed, a function, and a number n, and creates a list of length n by applying the function to each element to compute the next one. Here’s its signature: 

view plaincopy to clipboardprint?

1. public static  List iterate(B seed, Function f, int n)  

This method is available in the fpinjava-common module. Below is a simple implementation example: 

view plaincopy to clipboardprint?

1. package fp.utils;  
2.   
3. import java.util.ArrayList;  
4.   
5. public class List {  
6.     public static  java.util.List iterate(T seed, Function fun, int loop)  
7.     {  
8.         java.util.List list = new ArrayList(); list.add(seed);  
9.         T tmp = seed;  
10.         for(int i=0; i1; i++)  
11.         {  
12.             tmp = fun.apply(tmp); list.add(tmp);  
13.         }  
14.           
15.         return list;  
16.     }  
17. }  

Automatic memoization 
Memoization isn’t mainly used for recursive functions. It can be used to speed up any function. Think about how you perform multiplication. If you need to multiply 234 by 686, you’ll probably need a pen and some paper, or a calculator. But if you’re asked to multiply 9 by 7, you can answer immediately, without doing any computation. This is because you use a memoized multiplication. A memoized function works the same way, although it needs to make the computation only once to retain the result. 

Imagine you have a functional method doubleValue that multiplies its argument by 2: 

view plaincopy to clipboardprint?

1. Integer doubleValue(Integer x) {  
2.   return x * 2;  
3. }  

You could memoize this method by storing the result into a map: 

view plaincopy to clipboardprint?

1. Map cache = new ConcurrentHashMap<>();  
2. Integer doubleValue(Integer x)  
3. {  
4.     if(cache.containsKey(x)) return cache.get(x);  
5.     else  
6.     {  
7.         Integer rst = x * 2;  
8.         cache.put(x,  rst);  
9.         return rst;  
10.     }  
11. }  

In Java 8, this can be made much shorter: 

view plaincopy to clipboardprint?

1. Map cache = new ConcurrentHashMap<>();  
2.   
3. Integer doubleValue(Integer x) {  
4.   return cache.computeIfAbsent(x, y -> y * 2);  
5. }  

If you prefer using functions (which is likely, given the subject of this book), you can apply the same principle: 

view plaincopy to clipboardprint?

1. Function doubleValue =   
2.                       x -> cache.computeIfAbsent(x, y -> y * 2);  

But two problems arise: 

* You have to repeat this modification for all functions you want to memoize.
* The map you use is exposed to the outside.

The second problem is easy to address. You can put the method or the function in a separate class, including the map, with private access. Here’s an example in the case of a method: 

view plaincopy to clipboardprint?

1. public class Doubler {  
2.   
3.   private static Map cache = new ConcurrentHashMap<>();  
4.   
5.   public static Integer doubleValue(Integer x) {  
6.     return cache.computeIfAbsent(x, y -> y * 2);  
7.   }  
8. }  

You can then instantiate that class and use it each time you want to compute a value: 

view plaincopy to clipboardprint?

1. Integer y = Doubler.doubleValue(x);  

With this solution, the map is no longer accessible from the outside. You can’t do the same for functions, because functions can’t have static members. One possibility is to pass the map to the function as an additional argument. This can be done through a closure: 

view plaincopy to clipboardprint?

1. class Doubler {  
2.   private static Map cache = new ConcurrentHashMap<>();  
3.   
4.   public static Function doubleValue =  
5.                                x -> cache.computeIfAbsent(x, y -> y * 2);  
6. }  

You can use this function as follows: 

view plaincopy to clipboardprint?

1. Integer y = Doubler.doubleValue.apply(x);  

This gives no advantage compared to the method solution. But you can also use this function in more idiomatic examples, such as this: 

view plaincopy to clipboardprint?

1. map(range(1, 10), Doubler.doubleValue);  

This is equivalent to using the method version with the following syntax: 

view plaincopy to clipboardprint?

1. map(range(1, 10), Doubler::doubleValue);  

The requirements 
What you need is a way to do the following: 

view plaincopy to clipboardprint?

1. Function f = x -> x * 2;  
2. Function g = Memoizer.memoize(f);  

Then you can use the memoized function as a drop-in replacement for the original one. All values returned by function g will be calculated through the original function f the first time, and returned from the cache for all subsequent accesses. By contrast, if you create a third function, 

view plaincopy to clipboardprint?

1. Function f = x -> x * 2;  
2. Function g = Memoizer.memoize(f);  
3. Function h = Memoizer.memoize(f);  

the values cached by g won’t be returned by h; g and h will use separate caches. 

Implementation 
The Memoizer class is simple and is shown in the following listing. 

view plaincopy to clipboardprint?

1. package fp.utils;  
2.   
3. import java.util.Map;  
4. import java.util.concurrent.ConcurrentHashMap;  
5.   
6. public class Memorizer {  
7.     private final Map cache = new ConcurrentHashMap<>();  
8.       
9.     private Memorizer(){}  
10.       
11.     public static  Function memorize(Function fun)  
12.     {  
13.         return new Memorizer().doMemorize(fun);  
14.     }  
15.       
16.     private Function doMemorize(Function fun)  
17.     {  
18.         return input -> cache.computeIfAbsent(input, fun::apply);  
19.     }  
20. }  

The following listing shows how this class can be used. The program simulates a long computation to show the result of memoizing the function. 
Listing 4.7. Demonstrating the memoizer 

view plaincopy to clipboardprint?

1. package fp.ch4;  
2.   
3. public class List4_7 {  
4.     private static Integer longCalculation(Integer x)  
5.     {  
6.         try  
7.         {  
8.             Thread.sleep(1000);  
9.         }   
10.         catch(InterruptedException ignored){}  
11.         return x * 2;  
12.     }  
13.       
14.     private static Function f = List4_7::longCalculation;  
15.     private static Function g = Memorizer.memorize(f);  
16.       
17.     public static void main(String args[])  
18.     {  
19.         long startTime = System.currentTimeMillis();  
20.         Integer result1 = g.apply(1);  
21.         long time1 = System.currentTimeMillis() - startTime;  
22.         startTime = System.currentTimeMillis();  
23.         Integer result2 = g.apply(1);  
24.         long time2 = System.currentTimeMillis() - startTime;  
25.         System.out.println(result1);  
26.         System.out.println(result2);  
27.         System.out.println(time1);  
28.         System.out.println(time2);        
29.     }  
30. }  

Running the above example on my computer produces the following result: 

2
2
1000
0

Note that the exact result will depend on the speed of your computer. You can now make memoized functions out of ordinary ones by calling a single method, but to use this technique in production, you’d have to handle potential memory problems. This code is acceptable if the number of possible inputs is low, so you can keep all results in memory without causing memory overflow. Otherwise, you can use soft references or weak references to store memoized values. 

Memoization of “multiargument” functions 
As I said before, there’s no such thing in this world as a function with several arguments. Functions are applications of one set (the source set) to another set (the target set). They can’t have several arguments. Functions that appear to have several arguments are one of these: 

* Functions of tuples
* Functions returning functions returning functions ... returning a result

In either case, you’re concerned only with functions of one argument, so you can easily use your Memoizer class. Using functions of tuples is probably the simplest choice. You could use the Tuple class written in previous chapters, but to store tuples in maps, you’d have to implement equals and hashcode. Besides this, you’d have to define tuples for two elements (pairs), tuples for three elements, and so on. Who knows where to stop? 


The second option is much easier. You have to use the curried version of the functions, as you did in previous chapters. Memoizing curried functions is easy, although you can’t use the same simple form as previously. You have to memoize each function: 

view plaincopy to clipboardprint?

1. Function> mhc =  
2.                                   Memoizer.memoize(x ->  
3.                                           Memoizer.memoize(y -> x + y));  

You can use the same technique to memoize a function of three arguments: 

view plaincopy to clipboardprint?

1. Function>> f3 =  
2.                                                 x -> y -> z -> x + y - z;  
3. Function>> f3m =  
4.                   Memoizer.memoize(x ->  
5.                           Memoizer.memoize(y ->  
6.                                   Memoizer.memoize(z -> x + y - z));  

The following listing shows an example of using this memoized function of three arguments. 
Listing 4.8. Testing a memoized function of three arguments for performance 

view plaincopy to clipboardprint?

1. package fp.ch4;  
2.   
3. import fp.utils.Function;  
4. import fp.utils.Memorizer;  
5.   
6. public class List4_8 {  
7.     public static Integer longCalculation(Integer x)  
8.     {  
9.         try  
10.         {  
11.             Thread.sleep(1000);  
12.         }   
13.         catch(InterruptedException ignored){}  
14.         return x * 2;  
15.     }  
16.   
17.     public static void main(String[] args) {  
18.         Function>> f3m =  
19.                     Memorizer.memorize(x ->  
20.                         Memorizer.memorize(y ->  
21.                             Memorizer.memorize(z ->  
22.                                 longCalculation(x) + longCalculation(y) - longCalculation(z))));  
23.   
24.         long startTime = System.currentTimeMillis();  
25.         Integer result1 = f3m.apply(2).apply(3).apply(4);  
26.         long time1 = System.currentTimeMillis() - startTime;  
27.         startTime = System.currentTimeMillis();  
28.         Integer result2 = f3m.apply(2).apply(3).apply(4);  
29.         long time2 = System.currentTimeMillis() - startTime;  
30.         System.out.println(result1);  
31.         System.out.println(result2);  
32.         System.out.println(time1);  
33.         System.out.println(time2);  
34.     }     
35. }  

This program produces the following output: 

2
2
3002
0

This shows that the first access to the longCalculation method has taken 3,000 milliseconds, and the second has returned immediately. On the other hand, using a function of a tuple may seem easier after you have the Tuple class defined. The following listing shows an example of Tuple3. 
Listing 4.9. An implementation of Tuple3 

view plaincopy to clipboardprint?

1. package fp.utils;  
2.   
3. import java.util.Objects;  
4.   
5. public class Tuple3<T, U, V> {  
6.     public final T _1;  
7.     public final U _2;  
8.     public final V _3;  
9.   
10.     public Tuple3(T t, U u, V v) {  
11.         _1 = Objects.requireNonNull(t);  
12.         _2 = Objects.requireNonNull(u);  
13.         _3 = Objects.requireNonNull(v);  
14.     }  
15.   
16.     @Override  
17.     public boolean equals(Object o) {  
18.         if (!(o instanceof Tuple3))  
19.             return false;  
20.         else {  
21.             Tuple3 that = (Tuple3) o;  
22.             return _1.equals(that._1) && _2.equals(that._2) && _3.equals(that._3);  
23.         }  
24.     }  
25.   
26.     @Override  
27.     public int hashCode() {  
28.         final int prime = 31;  
29.         int result = 1;  
30.         result = prime * result + _1.hashCode();  
31.         result = prime * result + _2.hashCode();  
32.         result = prime * result + _3.hashCode();  
33.         return result;  
34.     }  
35. }  

The following listing shows an example of testing a memoized function taking Tuple3 as its argument. 
Listing 4.10. A memoized function of Tuple3 

view plaincopy to clipboardprint?

1. package fp.ch4;  
2.   
3. import fp.utils.Function;  
4. import fp.utils.Memorizer;  
5. import fp.utils.Tuple3;  
6.   
7. public class List4_10 {  
8.     public static Integer longCalculation(Integer x)  
9.     {  
10.         try  
11.         {  
12.             Thread.sleep(1000);  
13.         }   
14.         catch(InterruptedException ignored){}  
15.         return x * 2;  
16.     }  
17.   
18.     public static void main(String[] args) {  
19.         Function<Tuple3<Integer, Integer, Integer>, Integer> ft =  
20.                 x -> longCalculation(x._1)  
21.                                 + longCalculation(x._2)  
22.                                           - longCalculation(x._3);  
23.         Function<Tuple3<Integer, Integer, Integer>, Integer> ftm = Memorizer.memorize(ft);  
24.   
25.         long startTime = System.currentTimeMillis();  
26.         Integer result1 = ftm.apply(new Tuple3<>(2, 3, 4));  
27.         long time1 = System.currentTimeMillis() - startTime;  
28.         startTime = System.currentTimeMillis();  
29.         Integer result2 = ftm.apply(new Tuple3<>(2, 3, 4));  
30.         long time2 = System.currentTimeMillis() - startTime;  
31.         System.out.println(result1);  
32.         System.out.println(result2);  
33.         System.out.println(time1);  
34.         System.out.println(time2);  
35.     }  
36. }  

Are memoized functions pure? 
Memoizing is about maintaining state between function calls. A memoized function is a function whose behavior is dependent on the current state. But it’ll always return the same value for the same argument. Only the time needed to return the value will be different. So the memoized function is still a pure function if the original function is pure. A variation in time may be a problem. A function like the original Fibonacci function needing many years to complete may be called nonterminating, so an increase in time may create a problem. On the other hand, making a function faster shouldn’t be a problem. If it is, there’s a much bigger problem somewhere else! 

Summary 

* A recursive function is a function that’s defined by referencing itself.
* In Java, recursive methods push the current computation state onto the stack before recursively calling themselves.
* The Java default stack size is limited. It can be configured to a larger size, but this generally wastes space because all threads use the same stack size.
* Tail recursive functions are functions in which the recursive call is in the last (tail) position.
* In some languages, recursive functions are optimized using tail call elimination (TCE).
* Java doesn’t implement TCE, but it’s possible to emulate it.
* Lambdas may be made recursive.
* Memoization allows functions to remember their computed values in order to speed up later accesses.
* Memoization can be made automatic.

Supplement 
* Ch4 - Recursion, corecursion, and memoization - Part1 
* Ch4 - Recursion, corecursion, and memoization - Part2