scala

Learning Functional Programming in Scala (book) alvin May 29, 2017 - 11:22am

If you like “works in progress,” I’m currently in the process of moving the HTML version of my new book to this website (alvinalexander.com). You can find the first page here at Learning Functional Programming in Scala.

(The motivation for moving it here is that I want to a) make my life easier, and b) make it so I can find my own content by just searching this website.)

A Visual Look at JVM Stacks and Frames

Given the background information of the previous lesson, let’s take a visual look at how the JVM stack and stack frames work by going back to our recursive sum function from the previous lesson.

Before the sum function is initially called, the only thing on the call stack is the application’s main method:

Then main calls sum with List(1,2,3), which I show here without the “List” to keep things simple:

JVM Stacks and Stack Frames alvin May 29, 2017 - 11:14am

For functions without deep levels of recursion, there’s nothing wrong with the algorithms shown in the previous lessons. I use this simple, basic form of recursion when I know that I’m working with limited data sets. But in applications where you don’t know how much data you might be processing, it’s important that your recursive algorithms are tail-recursive, otherwise you’ll get a nasty StackOverflowError.

For instance, if you run the sum function from the previous lessons with a larger list, like this:

Recursion: Thinking Recursively

“To understand recursion,
one must first understand recursion.”

Stephen Hawking

Goal

This lesson has one primary goal: to show that the thought process followed in writing the sum function follows a common recursive programming “pattern.” Indeed, when you write recursive functions you’ll generally follow the three-step process shown in this lesson.

Recursion: A Conversation Between Two Developers

As an homage to one of my favorite Lisp books — an early version of what is now The Little Schemer — this lesson shows a little question and answer interaction that you can imagine happening between two Scala programmers.

Given this sum function:

def sum(list: List[Int]): Int = list match {
    case Nil => 0
    case x :: xs => x + sum(xs)
}

I hope this “conversation” will help drive home some of the points about how recursion works:

Recursion: How Recursive Function Calls Work

An important point to understand about recursive function calls is that just as they “wind up” as they are called repeatedly, they “unwind” rapidly when the function’s end condition is reached.

In the case of the sum function, the end condition is reached when the Nil element in a List is reached. When sum gets to the Nil element, this pattern of the match expression is matched:

Recursion: Motivation

What is recursion?

Before getting into the motivation to use recursion, a great question is, “What is recursion?”

Simply stated, a recursive function is a function that calls itself. That’s it. As you’ll see in this lesson, a common use of recursive functions is to iterate over the elements in a list.