Luet oppimateriaalin englanninkielistä versiota. Mainitsit kuitenkin taustakyselyssä osaavasi suomea. Siksi suosittelemme, että käytät suomenkielistä versiota, joka on testatumpi ja hieman laajempi ja muutenkin mukava.

Suomenkielinen materiaali kyllä esittelee englanninkielisetkin termit.

Kieli vaihtuu A+:n sivujen yläreunan painikkeesta. Tai tästä: Vaihda suomeksi.

# Chapter 12.2: Recursion

Questions Answered: What if a function calls itself? And why would it?

Topics: Recursively defined (self-referential) data. Recursion as an implementation technique for functions. We’ll also touch on some aspects of algorithmic efficiency.

What Will I Do? There are many small assignments and quite a bit of reading to do.

Rough Estimate of Workload:? Around five hours.

Points Available: C150.

Related Modules: Recursion (new), Viinaharava. ## Introduction

An ancient joke

recursion (noun): See recursion.

The basic idea of recursion (rekursio) is to define something in terms of itself. In this chapter, we’re especially interested in defining functions that call themselves.

When you first hear about this notion, it may sound marginally useful at best, but as it turns out, recursion is an extremely versatile programming technique. In fact, let’s highlight that by placing recursive functions in this diagram from Chapter 6.3:

Recursion is a rich topic. In this chapter, we’ll look at it primarily as an implementation technique that relies on frames on the call stack and that you can use instead of loops to implement repetition; we’ll refer to loop-based repetition as iteration (iteraatio).

Most mainstream programming paradigms make use of recursion. This includes imperative, functional, and object-oriented programming (Chapter 11.2). Of these paradigms, functional programming is particularly known for its frequent use of recursion.

Let’s start with a form of recursion that many people find easiest to grasp:

## Structural Recursion

It’s not uncommon to define a data type that refers to itself. For instance:

• A course may have a prerequisite course that is itself also a course (object).

• An employee can have subordinates that are also employees.

• An area in a game may have neighbors that are also areas (as in the text adventure of Chapters 9.3 and 11.1).

We’ll refer to such self-referential data as structurally recursive (rakenteellinen rekursio). In a structurally recursive object-oriented program, objects contain references to other objects of the same type: the objects can thus form a chain of prerequisites, a company’s personnel tree, a network of game areas, or a similar linked structure.

Where you have structurally recursive objects, you can also make use of methods that are recursive.

### Example: courses with prerequisites

Suppose we model university courses as objects. Each course is worth a specific number of credits and may have other courses as prerequisites. To keep this example simple, let’s say that each course can have only a single other course as its immediate prerequisite.

Let’s give our course objects a `totalCredits` method that determines the number of credits that the course and all its prerequisites are worth, in total. That is, the method should sum up the course’s own credit value, plus that of its prerequisite course, plus that of the prerequisite’s prerequisite, and so on.

You can think of the method’s behavior as communication between course objects. Here’s an animated diagram similar to the ones we used in the early weeks of O1:

### The same thing in Scala

Suppose we have a `Course` trait that represents courses in general. We also have two subtypes: `IntroCourse` and `FollowOnCourse`. An intro course has no prerequisites. A follow-on course has exactly one prerequisite.

Usage examples:

```val studyIntro = IntroCourse("Introduction to Studies at Aalto", 2)studyIntro: IntroCourse = Introduction to Studies at Aalto (2cr)
val prog1 = FollowOnCourse("Programming 1", 5, studyIntro)prog1: FollowOnCourse = Programming 1 (5cr)
val prog2 = FollowOnCourse("Programming 2", 5, prog1)prog2: FollowOnCourse = Programming 2 (5cr)
val dataStruct = FollowOnCourse("Data Structures and Algorithms", 5, prog2)dataStruct: FollowOnCourse = Data Structures and Algorithms (5cr)
val databases = FollowOnCourse("Database Programming", 5, prog1)databases: FollowOnCourse = Database Programming (5cr)
```

`totalCredits` should work like this:

```studyIntro.totalCreditsres0: Int = 2
databases.totalCreditsres1: Int = 12
dataStruct.totalCreditsres2: Int = 17
```

Here’s an implementation for the supertype `Course`:

```trait Course(val name: String, val cr: Int):
def totalCredits: Int
override def toString = this.name + " (" + this.cr + "cr)"
```

The abstract method `totalCredits` has no generic implementation for all kinds of courses. Subtypes implement this method in different ways.

The `IntroCourse` subtype is extremely simple. An introductory course doesn’t need to work out the credit values of its prerequisites since there are none. It just returns its own credit value:

```class IntroCourse(name: String, cr: Int) extends Course(name, cr):
def totalCredits = this.cr
```

`FollowOnCourse` isn’t complicated, either. The algorithm for its `totalCredits` method is simple to express in English: “Add the total credits of your prerequisite to your own credit value.” This algorithm translates directly into a recursive method:

```class FollowOnCourse(name: String, cr: Int, val prerequisite: Course) extends Course(name, cr):
def totalCredits = this.prerequisite.totalCredits + this.cr
```

The body of `totalCredits` contains a recursive method call: it calls the very same `totalCredits` method.

### Is it magic?

Compared to, say, a `while` loop that does the same thing, some recursive methods are so simple and elegant that it can seem nigh on supernatural. But let’s keep our feet grounded.

A recursive method can be deceptively short. Consider `totalCredits`. The innocent-looking sum expression actually causes multiple course objects to communicate and the summing to repeat for each object in the chain. Those stages of program execution aren’t directly expressed as code; it’s up to the programmer to perceive them mentally, or perhaps with a visual aid such as the animation above.

You don’t need any new commands to write a recursive program: you do that with ordinary method calls. This is reflected in the animation: there was nothing new about it compared to our earlier animations, except that the call stack simultaneously contained multiple frames associated with the same method. (Each frame targets a different object and thus has a different `this`.)

By now, you’ve seen umpteen examples of a method calling another. When method A calls method B, A stays in wait while B does its work; then A resumes where it left off. In general, recursive methods work just the same. The only difference is that the method calls itself and multiple unfinished activations of the same method exist at the same time.

As long as you understand how method calls work on the call stack, you can also reason about what happens during a recursive program run.

## Recursing without Structural Recursion

### Example: palindromes

Let’s use a function to determine if a given string is a palindrome, that is, if it reads the same forwards and backwards.

```isPalindrome("redivider")res3: Boolean = true
```

We could choose either iteration (loops) or recursion as our implementation strategy. Let’s do both so that we can compare.

On palindromes

The `isPalindrome` methods in this chapter require every single character to be exactly identical forwards and backwards, whitespace and punctuation included. These methods can’t detect multi-word palindromes such as “Borrow or rob?”. In the Recursion module, there is an additional version of the method that ignores everything but actual letters.

### Palindromes: an iterative implementation

Here’s one palindrome-checking algorithm in pseudocode:

```def isPalindrome(candidate: String): Boolean =
Check one pair of characters at a time, starting from left and right at the same time.
At each pair of characters (one from the front, one from the back):
1. If the characters are different, the candidate string is not a palindrome, so stop.
2. If all the pairs have now been checked, the candidate is a palindrome.
(In case there is an odd number of characters, the middle one can be ignored.)```

And here’s a refined version:

```def isPalindrome(candidate: String): Boolean =
Set the stepper leftIndex to zero and rightIndex to one less than the candidate string’s length.
Keep incrementing leftIndex by one and decrementing rightIndex by one
as long as leftIndex is less than rightIndex. On each such iteration:
1. Check the two characters at leftIndex and rightIndex.
2. If they differ, return false and stop running this method.
In case all the characters were checked (without returning false), return true.```

This iterative algorithm repeats operations during a single method call until a specific condition is no longer met; that happens when the growing `leftIndex` meets the reducing `rightIndex`. The algorithm translates directly into a `while` loop:

```def isPalindrome(candidate: String): Boolean =
var leftIndex = 0
var rightIndex = candidate.length - 1
while leftIndex < rightIndex do
if candidate(leftIndex) != candidate(rightIndex) then
return false
leftIndex += 1
rightIndex -= 1
end while
true
```

Recall the `return` command from Chapter 9.1. Executing this command immediately terminates the function call and returns a value. Here, we interrupt the loop immediately if we happen on two different characters (in which case it’s unnecessary to continue).

As also stated in Chapter 9.1, Scala requires you to explicitly annotate the return type of any function that uses `return`.

We reach the final line only if the loop didn’t previously return `false`.

### Palindromes: a recursive implementation

Here’s another palindrome-checking algorithm in pseudocode:

```def isPalindrome(candidate: String): Boolean =
Any string of length zero or one is a palindrome.
A string whose first and last characters are different is not a palindrome.
Otherwise, a string is a palindrome if and only if:
- The shorter string that we get by omitting the first
and last characters is a palindrome.```

Notice the following:

• This pseudocode doesn’t describe commands to be repeated or specific steps of execution. It reads more like description of what a palindrome is. (In other words, the algorithm is declarative.)

• The definition is recursive: the last item refers to the concept of palindrome itself.

We can convert that pseudocode, too, into “commands”:

```def isPalindrome(candidate: String): Boolean =
If the candidate’s length is no more than one, return true.
Otherwise, if its first and last characters are different, return false.
In all other cases, take the middle part, leaving out the first and last
characters. Use a recursive method call to find out if that middle part is
a palindrome, then return the same truth value as the recursive call did.```

The same as Scala code:

```def isPalindrome(candidate: String): Boolean =
if candidate.length <= 1 then
true
else if candidate.head != candidate.last then
false
else
isPalindrome(candidate.substring(1, candidate.length - 1))
```

Our function has two base cases (perustapaus): cases where we don’t need a recursive call to determine the result. (Cf. the intro courses in our earlier example.)

The `head` method gives us the first character (Chapter 5.2) and `last` gives the last one.

The function has one recursive branch where it calls itself, passing in a different value. The function generates the appropriate parameter string for the recursive call.

This `isPalindrome` implementation, too, needs a return type annotation. This is because Scala demands such an annotation on all recursive methods.

This animation details how the function works:

As the animation shows, the same algorithm is applied to a different parameter value in each frame. Those values have been generated by the algorithm itself: the algorithm uses `substring` to obtain a new string and calls itself on it. `String`s aren’t recursively defined but the algorithm nevertheless keeps creating new strings — smaller problems to solve — and applying itself to them.

Assume the computer deals with `isPalindrome` as shown in the animation above. You then call `isPalindrome("redder")`. How many frames associated with `isPalindrome` calls appear on the call stack as a consequence? (The bottom frame that initiates the first call does not count.)

How about if you call `isPalindrome("deferred")` instead?

### What about `reverse`?

Didn’t strings also have a `reverse` method that we could have used?

They do. Above, we conveniently forgot this fact in order to compare the iterative and recursive solutions. Below is another solution, which is both compact and directly expresses what palindromes are about:

```def isPalindrome(candidate: String) = candidate == candidate.reverse
```

But do notice this: `reverse` is not really an alternative to iteration and recursion. It’s a high-level tool for a more specific need than those techniques (and places fairly high up in the diagram at the top of the chapter). The reversing method itself can be implemented using either iteration or recursion.

Even though we happened to have a higher-level tool available for this example problem, that isn’t always the case.

## Iteration vs. Recursion

We’ve demonstrated that recursion can be useful even where there is no structural recursion. In fact, any programming problem that can be solved iteratively (with loops) can be alternatively solved via recursion — and vice versa. The two approaches differ in how easy it is to formulate a solution and how readable and efficient that solution will be. Which approach is better depends on the problem, the programming toolkit, and the program’s human readership.

The table below highlights some of the main features of iterative and recursive algorithms.

Iteration with loops

Recursion

We step through the problem by repeating an operation. Each iterative cycle continues where the previous one left off.

Example: we repeatedly check pairs of letters before moving to the next pair within the candidate palindrome.

Example: we loop through a chain of courses, repeatedly checking the credit values and adding them to an accumulating sum.

We chip off a piece of the problem that is easy to solve and apply the same algorithm to the reduced problem. .

Example: we remove the first and last characters (a piece of the problem that is easily dealt with) and apply the same algorithm to the remaining middle part (the reduced problem).

Example: we take the target course’s own redit value (a piece of the problem) and apply the same algorithm to its prerequisites (the reduced problem).

Use of variables:

We keep track of an algorithm’s state with `var`s and mutable collections.

Example: we use two stepper variables to track the two indices within the candidate word.

Example: We use a `var` to track which of the chained courses we’re currently working on. We modify that `var` on each iterative cycle. Another `var` serves as a gatherer where we accumulate the sum as we loop through the courses.

We can get the job done using only parameters and other `val` variables.

Example: we pass the remaining (middle) part of the string as a parameter to the next frame, higher on the stack.

Example: `this` points to a different course in each stack frame. The intermediate sums are produced and returned by different frames; we don’t need to modify the value of any variable.

Termination:

We stop repeating when we have advanced through the entire problem.

Example: we exit the loop when the increasing “left index” meets the decreasing “right index”.

Example: we loop until we hit a course that has no prerequisite.

When we’ve chipped away enough that only a little crumb of the original problem (a base case) remains, the solution is obvious and doesn’t need another recursive call.

Example: when we have a string of at most one character, the solution is obvious.

Example: if the course is an intro course, its total credits are obvious.

Constructing the solution:

Once we’ve gone through the entire problem, we have accumulated a solution.

Example: by the time we’ve checked the whole string, we know if it’s a palindrome.

Example: we track the sum in a gatherer variable, adding to it at each step. Once we’re done, the variable contains the final result.

We form an overall solution from the solution of the chipped-away piece and the solution of the reduced problem. Often, the overall solution will be some kind of combination of the two (such as a sum).

Example: if the first and last characters are different (solution of chipped-away piece), the string is not a palindrome. Otherwise, the solution equals that of the remaining middle part (the reduced problem).

Example: the “total credits” of a course is the sum of its own credit value (solution of chipped-away piece) and the total credits of the prerequisites (the reduced problem).

Recursion and induction

Do you know the mathematical concept of induction? It’s a proof technique that is closely related to recursion.

## Writing a Recursive Method

Let’s take another example that showcases how recursion and iteration are equivalent in power: we’ll take a small function implemented using a loop and write a recursive version of it. While we’re at it, we’ll reflect on the things that one must remember when writing a recursive method.

This toy function uses a loop to print out the squares of all positive integers up to a given limit:

```def printSquares(upperLimit: Int) =
for number <- 1 to upperLimit do
println(number * number)
```

That implementation exemplifies the iterative principles from the above table: we keep repeating the square-and-print operation and advancing to the next number, one number at a time, until we reach the upper limit.

How would a recursive version work? For one thing, we need a base case: a case where the problem is so small that it’s trivial to solve. Moreover, we’re supposed to “chip off a piece of the problem that’s easily dealt with” and to “apply the same algorithm to the reduced problem” until we find ourselves at the base case.

Let’s write this in pseudocode first. Our base case is the one where we don’t need to do anything, because there are no positive integers smaller than the given number:

```def printSquares(upperLimit: Int) =
if upperLimit == 0 then
Base case: no positive integers. No need to do anything.
else
A larger problem: Chip off a piece of the problem and call
printSquares on the reduced problem.```

Since we don’t need to do anything at the base case, we can simplify the algorithm:

```def printSquares(upperLimit: Int) =
if upperLimit > 0 then
Chip off a piece of the problem and call printSquares on the reduced problem.```

If the problem is “print N squares”, an identical but slightly smaller problem is “print N-1 squares”. The smaller problem is exactly the same, except that the last part of printing the square of N has been “chipped off”. Let’s use thought:

```def printSquares(upperLimit: Int) =
if upperLimit > 0 then
Use printSquares to print out the squares of all but the last number.
Then print the square of the last number, too.```

Here’s the Scala code:

```def printSquares(upperLimit: Int): Unit =
if upperLimit > 0 then
printSquares(upperLimit - 1)
println(upperLimit * upperLimit)
```

The recursive call uses a smaller number as a parameter. After a sufficient number of recursions, the program reaches the base case where the parameter equals zero.

In general, when you write a recursive method, you must be careful to ensure that the recursive calls bring the program closer to a base case so that the process eventually converges on a final result. (Cf. advancing a loop; Chapter 9.1.)

We again remember to give our recursive Scala method an explicit return type.

Here’s an animation of the same:

Think about running the function below on a parameter value of, say, 10.

```def printSquares(upperLimit: Int): Unit =
if upperLimit > 0 then
printSquares(upperLimit)
println(upperLimit * upperLimit)
```

Which of the following claims accurately describe what happens? Please select all that apply.

```def printSquares(upperLimit: Int): Unit =
printSquares(upperLimit - 1)
println(upperLimit * upperLimit)
```

Remember the base case

Unless the problem reduces to a base case, the outcome is “infinite” recursion, as in the timeworn joke that started this chapter. That definition, too, would be made more practical by the addition of a base case:

recursion (noun): If you know what recursion is, why are you reading this? Otherwise: see recursion.

## Mini-Assignment: Factorials

A+ presents the exercise submission form here.

A+ presents the exercise submission form here.

## Assignment: Drinking Water Quickly

Return to Chapter 8.1’s Viinaharava program. Edit the `drink` method of `GameBoard` objects so that whenever the player drinks a water glass whose danger level is zero (meaning there are no booze glasses nearby), all the neighboring water glasses are instantly emptied as well. If any of those neighbors are similarly safe, their neighbors are also emptied, and so on.

Instructions and hints:

• Use recursion: call `drink` from within itself.

• Avoid this infinite recursion: first you drink all the neighbors of glass A, one of which is glass B; then you drink all of B’s neighbors including A; then all of A’s neighbors including B; etc.

• The only change is to what happens when a water of zero danger is drunk. In all other cases, the method should behave as before.

A+ presents the exercise submission form here.

## Auxiliary Functions and a Recursive `favorite`

Let’s consider, for the last time, the favorite-handling code of class `Category` in the GoodStuff app. Let’s write a recursive implementation for it.

You’ve already seen (e.g., in Chapter 10.1) some versions of `favorite` that are shorter and more elegant than the recursive one that you’re about to see. This new implementation is worth a look nonetheless. Apart from being an additional example of recursion as a low-level implementation tool comparable to iterative loops, this example also introduces a common trick: we’ll put the recursion in an auxiliary function and use it within the primary function that we’re implementing.

Remember our objective. The `favorite` method should return the highest-rated experience in the category object’s `experiences` buffer. That experience should be wrapped in an `Option` so that `None` signals that there are no experiences and no favorite.

For comparison, here’s one way to implement the method iteratively:

```class Category(val name: String, val unit: String):

private val experiences = Buffer[Experience]()

def favorite =
if this.experiences.isEmpty then
None
else
var fave = this.experiences(0)
for currentIndex <- 1 until this.items.size do
fave = this.items(currentIndex).chooseBetter(fave)
Some(fave)
end if

end Category
```

Like the iterative version above, the recursive version too should check each element in the `experiences` buffer. As the method does that, it needs to track 1) which part of the buffer is currently being checked, and 2) what the highest-rated experience found so far is. In the iterative version above, everything takes place in a single frame on the call stack, and both of those things are tracked in local variables within that frame. We can also use local variables in our recursive implementation, but since each recursive call has its own separate frame with its own separate local variables, we’ll need to pass information from one recursive call to the next via parameters and return values.

However, we’ve specified `favorite` to be a parameterless method and we mean to keep it that way.

So, what we’ll do is define an auxiliary function that 1) is recursive; 2) takes a parameter; and 3) is meant for internal use by the `favorite` method only. Let’s call this function `findBest` and define it as a local function within `favorite`:

```class Category(val name: String, val unit: String):

private val experiences = Buffer[Experience]()

def favorite =
def findBest(start: Int): Experience =
Check the contents of this.experiences from index start onwards.
Return the highest rated of the experiences in that part of the buffer.
if this.experiences.isEmpty then None else Some(this.findBest(0))

end Category```

In this algorithm, `favorite` itself only takes care of the special case of zero experiences. Apart from that, it delegates the task to `findBest`: “Start searching from index zero up and return the best one you find.”

`findBest` needs a proper implementation. Here’s a more detailed pseudocode:

```def findBest(start: Int): Experience =
If start is the last index, return that last experience.
Otherwise, find the “best of the rest”: the highest-rated experience whose index is at least start + 1.
Return either the element at start or the best of the rest, whichever is rated higher.```

Translation to Scala:

```def findBest(start: Int): Experience =
if start == this.experiences.size - 1 then
this.experiences(start)
else
val bestOfRest = findBest(start + 1)
this.experiences(start).chooseBetter(bestOfRest)
```

Base case: if we start searching from the last index, the best experience is obviously the last element.

The reduced problem that we solve recursively: all the experiences after the `start` index.

The “chipped-away piece of the problem”: the element exactly at `start`.

Combining the solutions: we pick the better of the two.

Suppose `favorite` is implemented as just described and that `this.experiences` contains references to three `Experience` objects with ratings of 3, 7, and 2, in that order. We then call `favorite`. Which of the following claims are correct?

## Assignment: Generations

Study package `o1.family` in the Recursion module. It contains a single class, `FamilyMember`. Implement the missing methods of that class. Use recursion.

### Instructions and hints

• You may want to combine recursion with the `map` method: you can deal with all the children collectively with a `map` call that progresses deeper into the family tree.

• You may wish to write a small program for testing.

A potential pitfall while testing

If you test with an `App` object, watch out that none of the family members in the object depend on variables that you introduce only later. That is, don’t do this:

```object FamilyTest extends App:
val mary  = FamilyMember("Mary", Vector(jesus))
val jesus = FamilyMember("Jesus")
println(mary.numberOfDescendants)
```

This code gets past the Scala compiler (albeit accompanied by a warning), but it crashes at runtime with a `NullPointerException`. If you swap the first two lines inside the app object, “Jesus” exists before “Mary” is created and the program works. (Let’s not get caught on the biological oddity of that or any theological or etiological implications that may occur to you.)

A closer look at that `NullPointerException`

How can it be that `FamilyTest`, above, causes a runtime error? Isn’t it so that a variable’s scope begins where that variable is defined and so you should get an error for trying to access `jesus` before the `val` that defines it?

Indeed you would get a compile-time error if that code was inside a method and the variables were local to that method. For example, if you put that code in a `@main` function instead of an object, you’ll get a proper error message rather than “just” a warning.

But when you write that code directly into a singleton object, the variables `mary` and `jesus` become members of that object. The scope of an object’s member variables extends over the entire object; all those variables receive default values as soon as the object is created, even before the object’s state is properly initialized. (The reasons for this sometimes awkward behavior have to do with the way Scala has been made compatible with Java.) The variables’ default values are the same as the default values of array elements (Chapter 12.1).

So, what happens here is that the variables `mary` and `jesus` already exist by the time the computer starts running `FamilyTest`’s contents. Those variables don’t initially have any sensible values; they’re just `null`. Things go wrong when the “Mary” object is created: the variable `jesus` still has the default value of `null`, which gets stored as Mary’s child. Even though `jesus` is later linked with a `FamilyMember`, Mary remains untouched. The instruction `mary.numberOfDescendants` then attempts the inconceivable — to access the descendants of a nonexistent child — and crashes the program.

This goes to show that despite the existence of the `Option` type, `NullPointerException`s can happen in Scala. Don’t lie in error pining; keep an eye out for this issue and heed IntelliJ’s warnings.

A+ presents the exercise submission form here.

## Practice on Recursion

All the activities in this section are optional.

Items inside items inside items

In a Chapter 7.5 example, `Container` was a subclass of `Item` and you could put items inside items. Spot the recursion. Then edit the code you wrote earlier so that when you ask a bag or other container to count its contents, the count also includes the contents of the immediate contents, and their contents, etc.

Course prerequisites revisited

1. Above, we used the separate subtypes `FollowOnCourse` and `IntroCourse` to represent a course either having or not having prerequisites. Another alternative would be a single, concrete `Course` class with a `prerequisite` instance variable of type `Option[Course]`; you could then model an intro course as a `Course` object whose prerequisite is `None`. Can you implement this version? What will the recursive `totalCredits` be like? (See the Recursion module for a solution.)

2. Can you re-implement the `Option`-based `Course` class with a loop instead of recursion? Is the resulting code pretty?

3. How would you change the code to allow any course to have any number of prerequisite courses?

4. What happens if the same course appears multiple times among the prerequisites? What if there’s a cycle in the prerequisite chain: A requires B and vice versa?

The `reverse` method

1. (Easiest:) Earlier in this chapter, we noted that it’s possible to implement `isPalindrome` simply by using the `reverse` method on strings. From an efficiency perspective, that solution isn’t optimal, though. Why?

2. (Harder:) Consider how you would implement a function like `reverse`. It should take a string parameter and return the same characters in reverse order. Don’t use the existing `reverse` method or any other methods on `String` that process the entire string. Can you come up with an iterative implementation and a recursive one?

3. (Intended mostly for readers who have prior programming experience and want to delve deeper into Scala’s implementation:) The source code of Scala’s core API is linked to its Scaladocs. Dig into that code and find out whether the API authors have used iteration or recursion to implement `reverse`. Warning: this isn’t as straightforward as one might first think; there are incidental complications that arise from the API’s design and documentation. Hint: do a web search for `StringOps` and “extension methods”.

Making change

The Recursion module contains a `Currency` class, which we’ll use for representing the types of coins in different currencies. For instance, here’s how to create a currency with coins in denominations of 1 penny, 2 pence, 5 pence, 10 pence, 20 pence, 50 pence, 1 pound (= 100 pence), and 2 pounds.

```val britishPound = Currency(Vector(1, 2, 5, 10, 20, 50, 100, 200))britishPound: o1.money.Currency = 1, 2, 5, 10, 20, 50, 100, 200
```

`Currency` has a companion object that comes with a couple of predefined currencies:

```Currency.EURres5: o1.money.Currency = 1,2,5,10,20,50,100,200
Currency.USDres6: o1.money.Currency = 1,5,10,25,50
```

We’d like `Currency` to have a method that counts the number of ways that a given sum can be split into coins. Here’s an example:

```Currency.EUR.waysToSplit(5)res7: Int = 4
```

The answer is four, because there are four ways to split five euro cents: 1+1+1+1+1, 1+1+1+2, 1+2+2, and 5.

Implement `waysToSplit` and use it to determine, for instance, how many ways there are to split a single US dollar (`Currency.USD.waysToSplit(100)`). You’ll find some starter code in package `o1.money`.

Instructions and hints:

• Write an auxiliary function that takes an additional parameter. When calling this function, you should tell it 1) which amount of money should be divided; and 2) which denominations of coins it may use to divide that amount.

• Have `waysToSplit` call the auxiliary. Pass in the initial parameters: the amount is the entire original sum, and all the denominations are available.

• Implement the auxiliary function with recursion. Remember that a recursive method needs to reduce the problem somehow. In this problem, there are two different dimensions to reduce: the amount of money and the denominations of coins.

• Try solving the assignment on your own first. You can reveal additional hints below if you get stuck.

A first hint about recursive calls

Let’s call the original sum S. Now pick any denomination of coin, C, whose value is V.

Consider the following:

• How many ways are there to split S if you don’t use C at all?

• How many ways are there to split the smaller amount S-V?

• Are there any other ways of splitting S?

A second hint about recursive calls

There are exactly this many ways to split S:

1. the number of ways there are to split S without coin C; plus

2. the number of ways there are to split the smaller amount S-V using all the permitted types of coins.

Turn these two cases into recursive calls in the auxiliary function.

What are the base cases?

There is exactly one way to split zero.

There is no way to split a negative amount.

There is no way to split any amount of money if you can’t use any coins.

A+ presents the exercise submission form here.

A recursive sorting algorithm

The code below sorts the given collection. Study the code and figure out how it works.

This implementation uses pairs and the `partition` method (Chapter 9.2) as well as the `++` operator, which concatenates collections (Chapter 4.2)

```def sort(data: Vector[Int]): Vector[Int] =
if data.isEmpty then
data
else
val (pivot, rest) = (data.head, data.tail)
val (smaller, larger) = rest.partition( _ <= pivot )
sort(smaller) ++ Vector(pivot) ++ sort(larger)
```

This is one way to implement an algorithm known as quicksort. For more information, see Wikipedia.

## A Few Words on Efficiency

### Example: Fibonacci numbers

The Fibonacci sequence is the sequence 0, 1, 1, 2, 3, 5, 8, 13, etc., which is defined as follows.

• The first Fibonacci number (Fibonacci0) zero and the second (Fibonacci1) is one.

• The rest of the sequence comes from the formula: Fibonaccin = Fibonaccin-2 + Fibonaccin-1

This is a recursive definition: each Fibonacci number is defined in terms of the preceding Fibonacci numbers.

An interesting if tangential video

### One way to compute Fibonacci numbers in Scala

We can turn the recursive definition above into this recursive Scala function that computes the `n`th Fibonacci number:

```def fibo(n: Int): Long =
if n <= 1 then n else fibo(n - 1) + fibo(n - 2)
```

What an exquisite little piece of code! And it works, too, in the sense that it returns the correct Fibonacci numbers. Sadly, however, this implementation is quite problematic.

### The problem with `fibo`

Some recursive implementations are inefficient in their use of the computer’s memory and processing power. (Of course, there are inefficient iterative solutions, too.) Even though efficiency is largely a topic for O1’s follow-on courses, let’s take an instructive look at this example from that perspective.

How many times in total will the function be invoked if you call `fibo(7)`?

Is the function inefficient enough to bring a computer to its knees?

### A more efficient recursive solution

The above doesn’t imply that recursion is unavoidably inefficient for implementing `fibo`; it’s just that naïve implementation that’s inefficient. You may want to take a look at the better implementations below.

A better `fibo`

The code below isn’t as elegant or compact as the original, but it’s remarkably more efficient.

```def fibo(n: Int) =
def fiboHelp(thisFibo: Int, nextFibo: Int, stepsRemaining: Int): Long =
if stepsRemaining <= 0 then
thisFibo
else
fiboHelp(nextFibo, thisFibo + nextFibo, stepsRemaining - 1)
fiboHelp(0, 1, n)
```

This implementation uses a recursive auxiliary function named `fiboHelp`. (Cf. `findBest` in `favorite` earlier.)

`fiboHelp` is given two consecutive Fibonacci numbers so that it doesn’t need to recompute the same numbers over and over again. As a third parameter, the function is told how many steps it’s supposed to advance in the Fibonacci sequence before reaching the target number.

`fibo` calls `fiboHelp`: “Start at the Fibonacci number that equals zero and that is followed by the Fibonacci number that equals one. Move `n` steps forward in the sequence and return the Fibonacci number you stopped at.”

This sort of programming — storing partial solutions in in memory and then composing larger solutions from those partial solutions — is known as dynamic programming (dynaaminen ohjelmointi). You can do dynamic programming in recursive programs, as above, and in iterative programs, too.

For additional practice, try writing an iterative implementation for `fibo`. Use this recursive solution for inspiration.

A recursive `LazyList` and a lazy Fibonacci

Chapter 7.2 introduced you to lazy-lists: collections of potentially infinite size.

The Fibonacci sequence can be represented as a lazy-list:

```def fibonacciSequence =
def fiboFrom(first: BigInt, second: BigInt): LazyList[BigInt] =
first #:: fiboFrom(second, first + second)
fiboFrom(0, 1)fibonacciSequence: LazyList[BigInt]
fibonacciSequence.take(10).toVectorres8: Vector[BigInt] = Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
fibonacciSequence(9)res9: BigInt = 34
fibonacciSequence(100)res10: BigInt = 354224848179261915075
fibonacciSequence(10000)res11: BigInt = 3364476487643178326662161200510754331030214846068006390656476997468008144216666236815559551
363373402558206533268083615937373479048386526826304089246305643188735454436955982749160660209988418393386465
273130008883026923567361313511757929743785441375213052050434770160226475831890652789085515436615958298727968
29875106312005754287834... [Etc. The number is about 2000 digits long.]
```

Our auxiliary function constructs a lazy-list that covers all the Fibonacci numbers starting from the two consecutive ones that we pass in as parameters.

The lazy-list is recursively defined: the list’s first element is known; that first element is followed by a list of Fibonacci numbers that begins with the second known number.

This implementation is rather elegant, and efficient too. Since the list is lazy, it doesn’t recompute the earlier numbers in the sequence but stores them as long as they are needed. Computing the 10000th Fibonacci number takes but a brief moment.

Tail recursion

Frequently asked question: doesn’t recursion always eat up memory unnecessarily, since it needs memory for all those frames on the call stack?

It’s true that it’s possible to write recursive programs that use a lot of memory. However, there are many, many scenarios where the recursive frames on the stack don’t actually cause a problem in practice. This is in part because of optimizations that involve tail recursion (häntärekursio).

A tail-recursive function is written such that any recursive calls happens as the very last thing when then function body is run. For instance, our implementation of `isPalindrome` was tail recursive, since it doesn’t do anything after calling itself: it just passes on whichever value it received from the recursive call. On the other hand, our `printSquares` function isn’t tail recursive, since it squares and prints a number after calling itself.

A tail-recursive method doesn’t need a separate call-stack frame for each invocation. Various tools (such as compilers) automatically optimize programs and avoid creating frames unnecessarily. As an example, consider `isPalindrome` again; this animation shows an optimized version of its execution:

The standard Scala tools are capable of this optimization.

Here’s one way to put the matter: even though the code of a tail-recursive function is recursive, the process that the code defines is iterative. For any iterative process, there is always a loop-based implementation that a compiler can automatically generate from the tail-recursive program.

Questions for you to think about: Why isn’t the `factorial` function, above, tail recursive? Which of the functions in this chapter are? Can you come up with a tail-recursive implementation for `factorial`? (Hint: use an auxiliary function.)

The spring course Programming 2 will discuss this topic further. You may also want to take a look at the relevant article on Wikipedia.

Levenshtein distance and efficiency

Below is an elegant but inefficient function that computes Levenshtein distances. As mentioned in Chapter 1.6, the Levenshtein distance of two strings is the minimum number of single-character insertions, deletions, and substitutions that are needed for turning one string into the other.

```def editDistance(text1: String, text2: String): Int =
if text1.isEmpty || text2.isEmpty then
math.max(text1.length, text2.length)
editDistance(text1.tail, text2.tail)
else
val deletion     = editDistance(text1.tail, text2     )
val insertion    = editDistance(text1,      text2.tail)
val substitution = editDistance(text1.tail, text2.tail)
Vector(deletion, insertion, substitution).min + 1
```

Base case: the distance between the empty string and any other string equals the length of the other string.

Recursive case: the distance between two strings that begin with the same character equals the distance between the other characters in those two strings.

Another recursive case: the first characters are different. Let’s consider deleting, adding, and substituting the first character. We try each of those three alternatives, and...

... pick the option that results in the shortest distance. Since we did a single deletion, addition, or substitution, we add one to the result.

Read the Wikipedia article on Levenshtein distance and reflect on the efficiency of the above algorithm. Find out what tricks people have used for narrowing down the problem and producing more efficient implementations, whether recursive or otherwise.

## Summary of Key Points

• A recursive function is a function that calls itself.

• A recursive algorithm chips off a small piece of the problem that’s easy to solve, then applies itself to the remaining slightly smaller problem. Eventually, this reduces the problem to a trivial base case.

• You can use recursion as a generic implementation technique. It is an alternative to loops as a means of repetition. Many problems have very elegant recursive solutions.

• A program can be structurally recursive: you can define a data type in terms of itself. It is then often natural to write recursive functions that operate on that data.

• Recursive functions don’t need to operate on recursively defined data, however: a function may generate new values and apply itself to them.

• In principle, when a recursive function runs, multiple separate frames for the same function are simultaneously present on the call stack; each corresponds to a different activation of the function.

• In some circumstances, programming tools optimize resources by reusing the same frame for multiple activations.

• Links to the glossary: recursion, structural recursion, base case; iteration.

## Feedback

Please note that this section must be completed individually. Even if you worked on this chapter with a pair, each of you should submit the form separately.

What now?

O1 ends here — almost. Here’s what’s left:

• Chapter 12.3, which contains a voluntary RoboSpeak tournament.

• Chapter 12.4, which contains optional material on the Swing GUI library.

• Week 13, which opens soon after the Week 12 deadline. It won’t have any normal chapters, but it will contain the mandatory end-of-course feedback form in Chapter 13.1. You’ll need to fill that in by December 13th, 2023.

• We’ll also publish a final weekly bulletin as Chapter 13.0. Like the other bulletins, it will hopefully contain various fun and useful things.

## Credits

Thousands of students have given feedback and so contributed to this ebook’s design. Thank you!

The ebook’s chapters, programming assignments, and weekly bulletins have been written in Finnish and translated into English by Juha Sorva.

The appendices (glossary, Scala reference, FAQ, etc.) are by Juha Sorva unless otherwise specified on the page.

The automatic assessment of the assignments has been developed by: (in alphabetical order) Riku Autio, Nikolas Drosdek, Kaisa Ek, Joonatan Honkamaa, Antti Immonen, Jaakko Kantojärvi, Niklas Kröger, Kalle Laitinen, Teemu Lehtinen, Mikael Lenander, Ilona Ma, Jaakko Nakaza, Strasdosky Otewa, Timi Seppälä, Teemu Sirkiä, Anna Valldeoriola Cardó, and Aleksi Vartiainen.

The illustrations at the top of each chapter, and the similar drawings elsewhere in the ebook, are the work of Christina Lassheikki.

The animations that detail the execution Scala programs have been designed by Juha Sorva and Teemu Sirkiä. Teemu Sirkiä and Riku Autio did the technical implementation, relying on Teemu’s Jsvee and Kelmu toolkits.

The other diagrams and interactive presentations in the ebook are by Juha Sorva.

The O1Library software has been developed by Aleksi Lukkarinen and Juha Sorva. Several of its key components are built upon Aleksi’s SMCL library.

The pedagogy of using O1Library for simple graphical programming (such as `Pic`) is inspired by the textbooks How to Design Programs by Flatt, Felleisen, Findler, and Krishnamurthi and Picturing Programs by Stephen Bloch.

The course platform A+ was originally created at Aalto’s LeTech research group as a student project. The open-source project is now shepherded by the Computer Science department’s edu-tech team and hosted by the department’s IT services. Markku Riekkinen is the current lead developer; dozens of Aalto students and others have also contributed.

The A+ Courses plugin, which supports A+ and O1 in IntelliJ IDEA, is another open-source project. It has been designed and implemented by various students in collaboration with O1’s teachers.

For O1’s current teaching staff, please see Chapter 1.1.