concept recursion in category java

This is an excerpt from Manning's book Modern Java in Action: Lambdas, streams, reactive and functional programming. Login to get full access to this book.

Recursion is a technique promoted in functional programming to let you think in terms of what-to-do style. Pure functional programming languages typically don’t include iterative constructs such as while and for loops. Such constructs are often hidden invitations to use mutation. The condition in a while loop needs to be updated, for example; otherwise, the loop would execute zero times or an infinite number of times. In many cases, however, loops are fine. We’ve argued that for functional style, you’re allowed mutation if no one can see you doing it, so it’s acceptable to mutate local variables. When you use the for-each loop in Java, for(Apple apple : apples) { }, it decodes into this Iterator:

Now we’ll turn to efficiency. As Java users, beware of functional-programming zealots who tell you that you should always use recursion instead of iteration. In general, making a recursive function call is much more expensive than issuing the single machine-level branch instruction needed to iterate. Every time the factorialRecursive function is called, a new stack frame is created on the call stack to hold the state of each function call (the multiplication it needs to do) until the recursion is done. Your recursive definition of factorial takes memory proportional to its input. For this reason, if you run factorialRecursive with a large input, you’re likely to receive a StackOverflowError:

Exception in thread "main" java.lang.StackOverflowError

copy

Is recursion useless? Of course not! Functional languages provide an answer to this problem: tail-call optimization. The basic idea is that you can write a recursive definition of factorial in which the recursive call is the last thing that happens in the function (or the call is in a tail position). This different form of recursion style can be optimized to run fast. The next listing provides a tail-recursive definition of factorial.

This is an excerpt from Manning's book Functional Programming in Java: How functional techniques improve your Java programs. Login to get full access to this book.

Recursive functions are a ubiquitous feature in most functional programming languages, although recursion and functional programming aren’t connected. Some functional programmers even say that recursion is the goto feature of functional programming, and thus should be avoided as much as possible. Nevertheless, as functional programmers, you must master recursion, even if eventually you decide to avoid it.

As you may know, Java is limited in terms of recursion. Methods can call themselves recursively, but this implies that the state of the computation is pushed on the stack for each recursive call, until a terminal condition is reached, at which time all preceding states of the computation are popped out of the stack, one after the other, and evaluated. The size of the stack can be configured, but all threads will use the same size. The default size varies according to the implementation of Java, from 320 KB for a 32-bit version to 1,064 KB for a 64-bit implementation, both of which are very small compared to the size of the heap, where objects are stored. The end result is that the number of recursive steps is limited.

4.1. Understanding corecursion and recursion

Corecursion is composing computing steps by using the output of one step as the input of the next one, starting with the first step. Recursion is the same operation, but starting with the last step. In recursion, you have to delay evaluation until you encounter a base condition (corresponding to the first step of corecursion).