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
About This Page
Questions Answered: What if a function calls itself? And why would it?
Topics: Recursively defined (selfreferential) 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 loopbased repetition as iteration (iteraatio).
Most mainstream programming paradigms make use of recursion. This includes imperative, functional, and objectoriented 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 selfreferential data as structurally recursive (rakenteellinen rekursio). In a structurally recursive objectoriented 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
followon 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 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.
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 innocentlooking
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 isPalindrome("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
multiword 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 palindromechecking 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 palindromechecking 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.
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 highlevel 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 higherlevel 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 chippedaway 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 chippedaway 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 chippedaway 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 squareandprint 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 N1 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:
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.
MiniAssignment: Factorials
A+ presents the exercise submission form here.
MiniAssignment: Gift Tax
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.
A+ presents the exercise submission form here.
Auxiliary Functions and a Recursive favorite
Let’s consider, for the last time, the favoritehandling 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
lowlevel 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 highestrated 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 highestrated 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 highestrated 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 “chippedaway piece of the problem”: the element exactly at
start
.
Combining the solutions: we pick the better of the two.
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 amap
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 compiletime 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
Above, we used the separate subtypes
FollowOnCourse
andIntroCourse
to represent a course either having or not having prerequisites. Another alternative would be a single, concreteCourse
class with aprerequisite
instance variable of typeOption[Course]
; you could then model an intro course as aCourse
object whose prerequisite isNone
. Can you implement this version? What will the recursivetotalCredits
be like? (See the Recursion module for a solution.)Can you reimplement the
Option
basedCourse
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 thereverse
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 existingreverse
method or any other methods onString
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 forStringOps
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 SV?
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 SV 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 (Fibonacci_{0}) zero and the second (Fibonacci_{1}) is one.
The rest of the sequence comes from the formula: Fibonacci_{n} = Fibonacci_{n2} + Fibonacci_{n1}
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 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 followon 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 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 lazylists: collections of potentially infinite size.
The Fibonacci sequence can be represented as a lazylist:
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 lazylist that covers all the Fibonacci numbers starting from the two consecutive ones that we pass in as parameters.
The lazylist 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 tailrecursive 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 tailrecursive method doesn’t need a separate callstack 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 tailrecursive function is recursive, the process that the code defines is iterative. For any iterative process, there is always a loopbased implementation that a compiler can automatically generate from the tailrecursive 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 tailrecursive 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 singlecharacter 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)
else if text1.head == text2.head then
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.
The endofcourse event. Join us there!
Week 13, which opens soon after the Week 12 deadline. It won’t have any normal chapters, but it will contain the mandatory endofcourse feedback form in Chapter 13.1. You’ll need to fill that in by December 14th, 2022.
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, Joonatan Honkamaa, Antti Immonen, Jaakko Kantojärvi, Niklas Kröger, Kalle Laitinen, Teemu Lehtinen, 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 opensource project is now shepherded by the Computer Science department’s edutech 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 opensource 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.
Additional credits for this page
The moneysplitting assignment is a Scala variation of a programming problem discussed in the legendary computerscience textbook Structure and Interpretation of Computer Programs.
The video on Fibonacci and the golden mean was made by Beau Janzen.
The abstract method
totalCredits
has no generic implementation for all kinds of courses. Subtypes implement this method in different ways.