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 = 2 databases.totalCreditsres1: Int = 12 dataStruct.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 = 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
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) {
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 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)
true
else if (candidate.head != candidate.last)
false
else
isPalindrome(candidate.substring(1, candidate.length - 1))
}
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. Strings 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 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) {
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) {
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) {
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: see recursion.
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
drinkfrom 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 of this.experiences from index start onwards.
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 = {
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) {
this.experiences(start)
} else {
val bestOfRest = findBest(start + 1)
this.experiences(start).chooseBetter(bestOfRest)
}
}
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
mapmethod: you can deal with all the children collectively with amapcall 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,
NullPointerExceptions 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
FollowOnCourseandIntroCourseto represent a course either having or not having prerequisites. Another alternative would be to use a single concreteCourseclass with aprerequisiteinstance variable of typeOption[Course]; you could then model an intro course as aCourseobject whose prerequisite isNone. Can you implement this version? What will the recursivetotalCreditsbe like? (See the Recursion module for a solution.) - Can you re-implement the
Option-basedCourseclass 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
isPalindromesimply by using thereversemethod 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 existingreversemethod or any other methods onStringthat 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 forStringOpsand “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,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
waysToSplitcall 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 (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 nth 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 = 34
fibonacciSequence(100)res10: BigInt = 354224848179261915075
fibonacciSequence(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.
- 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.
totalCreditshas no generic implementation for all kinds of courses. Its subclasses implement this method in different ways.