# recursion

A Scala ‘foldLeft’ function written using recursion alvin January 20, 2018 - 4:25pm

As a short note, here’s some Scala source code that shows how to write a `foldLeft` function using recursion:

This is a page from my book, Functional Programming, Simplified

## Appendix: Recursion is Great, But ... (Scala’s fold and reduce)

“Folds can be used to implement any function where you traverse a list once, element by element, and then return something based on that. Whenever you want to traverse a list to return something, chances are you want a fold. That’s why folds are, along with maps and filters, one of the most useful types of functions in functional programming.”

From the book, Learn You a Haskell for Great Good!

This is a page from my book, Functional Programming, Simplified

## Scala Recursion Lessons (Section)

This section contains lessons on recursion (recursive programming) in Scala. The lessons in this section are listed below.

This is a page from my book, Functional Programming, Simplified

## Tail-Recursive Algorithms in Scala

“Tail recursion is its own reward.”

From the “Functional” cartoon on xkcd.com.

## Goals

The main goal of this lesson is to solve the problem shown in the previous lessons: Simple recursion creates a series of stack frames, and for algorithms that require deep levels of recursion, this creates a `StackOverflowError` (and crashes your program).

This is a page from my book, Functional Programming, Simplified

## 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:

This is a page from my book, Functional Programming, Simplified

## JVM Stacks and Stack Frames

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:

This is a page from my book, Functional Programming, Simplified

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

This is a page from my book, Functional Programming, Simplified

## 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: