The latest instance of the course can be found at: O1: 2024

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.1: Recursion

About This Page

*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 algorithm 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 10.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.1 and 10.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 an abstract class `Course`

, which represents courses in general. We
also have two subclasses: `IntroCourse`

and `FollowOnCourse`

. An intro course has no
prerequisites. A follow-on course has exactly one prerequisite.

Usage examples:

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

`totalCredits`

should work like this:

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

Here’s an implementation for the superclass `Course`

:

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

The subclass `IntroCourse`

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
}
```

`totalCredits`

contains a recursive method call:
it calls the very same `totalCredits`

method.### How recursion works

### 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. 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 = trueisPalindrome("reader")res4: Boolean = false

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 stepperleftIndexto zero andrightIndexto one less than the candidate string’s length.Keep incrementingleftIndexby one and decrementingrightIndexby oneas long asleftIndexis less thanrightIndex. On each such iteration:1. Check the two characters atleftIndexandrightIndex.2. If they differ, returnfalseand stop running this method.In case all the characters were checked (without returningfalse), returntrue.}

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) {
if (candidate(leftIndex) != candidate(rightIndex)) {
return false
}
leftIndex += 1
rightIndex -= 1
}
true
}
```

`return`

command from Chapter 8.3. 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).`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 firstand 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, returntrue.Otherwise, if its first and last characters are different, returnfalse.In all other cases, take the middle part, leaving out the first and lastcharacters. Use a recursive method call to find out if that middle part isa 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)
true
else if (candidate.head != candidate.last)
false
else
isPalindrome(candidate.substring(1, candidate.length - 1))
}
```

**base cases**(

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

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

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

Advancing the algorithm: | 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 Example: we use two stepper variables to track the two indices within the candidate word. Example: We use a |
We can get the job done using only parameters and other Example: we pass the remaining (middle) part of the string as a parameter to the next frame, higher on the stack. Example: |

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) {
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) {Base case: no positive integers. No need to do anything.} else {A larger problem: Chip off a piece of the problem and callprintSquareson 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) {Chip off a piece of the problem and callprintSquareson 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) {UseprintSquaresto 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) {
printSquares(upperLimit - 1)
println(upperLimit * upperLimit)
}
}
```

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

Here’s an animation of the same:

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: seerecursion.

## Mini-Assignment: Factorials

A+ presents the exercise submission form here.

## Mini-Assignment: Gift Tax

A+ presents the exercise submission form here.

## Assignment: Drinking Water Quickly

Return to Chapter 7.4’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.

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 9.3) some shorter, elegant versions of `favorite`

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) {
None
} else {
var fave = this.experiences(0)
for (currentIndex <- 1 until this.items.size) {
fave = this.items(currentIndex).chooseBetter(fave)
}
Some(fave)
}
}
}
```

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 ofthis.experiencesfrom indexstartonwards.Return the highest rated of the experiences in that part of the buffer.} if (this.experiences.isEmpty) None else Some(this.findBest(0)) }

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 = {Ifstartis the last index, return that last experience.Otherwise, find the “best of the rest”: the highest-rated experience whose index is at leaststart + 1.Return either the element atstartor the best of the rest, whichever is rated higher.}

Translation to Scala:

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

*after*the

`start`

index.`start`

.## Assignment: Generations

### Task description

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 app object for testing.

If you do write a test program, watch out that none of the family members in your app object depend on variables that you introduce only later. That is, don’t do this:

object FamilyTest extends App { val mary = new FamilyMember("Mary", Vector(jesus)) val jesus = new 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. But if 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 11.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.3 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

- Above, we used the separate subclasses
`FollowOnCourse`

and`IntroCourse`

to represent a course either having or not having prerequisites. Another alternative would be to use 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.) - Can you re-implement the
`Option`

-based`Course`

class with a loop instead of recursion? Is the resulting code pretty? - How would you change the code to allow any course to have any number of prerequisite courses?
- 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

- (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? - (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? - (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 “implicit conversions”.

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 = new 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,200Currency.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:

- the number of ways there are to split S without coin C; plus
- 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 8.4)
as well as the `++`

operator, which concatenates collections (Chapter 4.2)

```
def sort(data: Vector[Int]): Vector[Int] =
if (data.isEmpty) {
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 (Fibonacci
_{0}) zero and the second (Fibonacci_{1}) is one. - The rest of the sequence comes from the formula:
Fibonacci
_{n}= Fibonacci_{n-2}+ Fibonacci_{n-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) 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 very 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.

### 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)
thisFibo
else
fiboHelp(nextFibo, thisFibo + nextFibo, stepsRemaining - 1)
}
fiboHelp(0, 1, n)
}
```

`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.1 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 = 34fibonacciSequence(100)res10: BigInt = 354224848179261915075fibonacciSequence(10000)res11: BigInt = 3364476487643178326662161200510754331030214846068006390656476997468008144216666236815559551 363373402558206533268083615937373479048386526826304089246305643188735454436955982749160660209988418393386465 273130008883026923567361313511757929743785441375213052050434770160226475831890652789085515436615958298727968 29875106312005754287834... [Etc. The number is about 2000 digits long.]

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, for instance, 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) {
math.max(text1.length, text2.length)
} else if (text1.head == text2.head) {
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
}
}
```

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.

- Recursive functions don’t
- 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.2, which contains a little RoboSpeak tournament.
- Chapter 12.3, which contains optional material on the Swing GUI library.

- Week 13, which opens soon after the Week 12 deadline. It doesn’t
have any normal chapters, but it does contain
**the mandatory end-of-course feedback form**in Chapter 13.1. You’ll need to fill that in by December 22nd, 2021. - We’ll also publish a final weekly bulletin as Chapter 13.0. It will contain results from the robot tournament, the TAs’ favorite text adventures, follow-on courses, and more.

## Credits

Thousands of students have given feedback that has 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, Joonatan Honkamaa, Jaakko Kantojärvi, Niklas Kröger, Teemu Lehtinen, Strasdosky Otewa, Timi Seppälä, Teemu Sirkiä, 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 was created by Nikolai Denissov, Olli Kiljunen, Nikolas Drosdek, Styliani Tsovou, Jaakko Närhi, and Paweł Stróżański with input from Juha Sorva, Otto Seppälä, Arto Hellas, and others.

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

### Additional credits for this page

The money-splitting assignment is a Scala variation of a programming problem discussed in
the legendary computer-science textbook *Structure and Interpretation of Computer Programs*.

The video on Fibonacci and the golden mean was made by Beau Janzen.

`totalCredits`

has no generic implementation for all kinds of courses. Its subclasses implement this method in different ways.