concept recursion in category functional programming

This is an excerpt from Manning's book Functional Programming with Kotlin MEAP V07. Login to get full access to this book.

In order to adapt our existing program to demonstrate HOFs, we should introduce some new behaviour. We will do so by adding a new function that calculates the nth factorial. To write this simple function, we will need to take a short detour by showing how loops are written in a purely functional way. We do this by introducing recursion.

Listing 5.6. The foldRight function on Stream is used to generalize recursion.

fun <A, B> Stream<A>.foldRight(
    z: () -> B,
    f: (A, () -> B) -> B
): B = #1
    when (this) {
        is Cons -> f(this.head()) { tail().foldRight(z, f) } #2
        else -> z()
    }

copy

This is an excerpt from Manning's book Functional Programming in JavaScript. Login to get full access to this book.

Table 2.1. Comparing some important qualities of object-oriented and functional programming. These qualities are themes that are discussed throughout this book. (view table figure)

	Functional	Object-oriented
Unit of composition	Functions	Objects (classes)
Programming style	Declarative	Imperative
Data and behavior	Loosely coupled into pure, standalone functions	Tightly coupled in classes with methods
State management	Treats objects as immutable values	Favors mutation of objects via instance methods
Control flow	Functions and recursion	Loops and conditionals
Thread safety	Enables concurrent programming	Difficult to achieve
Encapsulation	Not needed because everything is immutable	Needed to protect data integrity

Sometimes a problem is difficult and complex to tackle head on. When this occurs, you should immediately look for ways to decompose it. If the problem can be broken down into smaller versions of itself, you may be able to solve the smaller version and build it up to solve the entire problem. Recursion is essential for array traversal in pure functional programming languages like Haskell, Scheme, and Erlang because they don’t have looping constructs.

In JavaScript, recursion has many applications, such as parsing XML or HTML documents, graphs, and so on. In this section, I’ll explain what recursion is and then work through an exercise that will teach you how to think recursively. Then we’ll take a quick look at a few data structures you can parse through using recursion.

Recursion and iteration are two sides of the same coin. In the absence of mutation, recursion offers a more expressive, powerful, and excellent alternative to iteration. In fact, pure functional languages don’t even have standard looping constructs like do, for, and while, since all looping is done recursively. Recursion also leads to code that’s easier to understand because it’s premised on repeating the same actions multiple times on smaller input. The recursive solution in the following listing uses the Lodash _.first and _.rest functions to access the first element of the array or all but the first, respectively.

Listing 3.10. Performing recursive addition

function sum(arr) {
   if(_.isEmpty(arr)) {                               #1
      return 0;
   }
   return _.first(arr) + sum(_.rest(arr));            #2
}
sum([]); //-> 0
sum([1,2,3,4,5,6,7,8,9]); //->45

copy

Adding the empty array triggers the base case, naturally returning zero. Otherwise, for non-empty arrays, you proceed to recursively extract and sum the first elements together with the rest of the array. Behind the scenes, recursive calls are stacked on top of each other. As soon as the algorithm reaches the terminating condition, all the return statements are executed as the runtime unwinds the stack to let the addition take place. This is the mechanism by which recursion cedes looping to the language runtime. Here’s a step-by-step view of the sum algorithm you just implemented:

1 + sum[2,3,4,5,6,7,8,9]
1 + 2 + sum[3,4,5,6,7,8,9]
1 + 2 + 3 + sum[4,5,6,7,8,9]
1 + 2 + 3 + 4 + sum[5,6,7,8,9]
1 + 2 + 3 + 4 + 5 + sum[6,7,8,9]
1 + 2 + 3 + 4 + 5 + 6 + sum[7,8,9]
1 + 2 + 3 + 4 + 5 + 6 + 7 + sum[8,9]
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + sum[9]
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + sum[]
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0     -> halts, stack unwinds
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
1 + 2 + 3 + 4 + 5 + 6 + 7 + 17
1 + 2 + 3 + 4 + 5 + 6 + 24
1 + 2 + 3 + 4 + 5 + 30
1 + 2 + 3 + 4 + 35
1 + 2 + 3 + 39
1 + 2 + 42
1 + 44
45

copy

At this point, it’s natural to think about the performance of recursion versus manual iteration. After all, compilers have become extremely smart at optimizing loops. ES6 JavaScript brings an optimization feature called tail-call optimization that can bring the performance of these two features closer together. Consider this slightly different implementation of sum:

3.5.1. What is recursion?

Recursion is a technique designed to solve problems by decomposing them into smaller, self-similar problems that, when combined, arrive at the original solution. A recursive function has two main parts:

Figure 7.3. How the function context grows when running nested functions. Because each function produces a new stack frame, the stack grows in proportion to the level of nesting in functions. Both currying and recursion rely on nested function calls.

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).