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. Myös suomenkielisessä materiaalissa käytetään ohjelmien koodissa englanninkielisiä nimiä kurssin alkupään johdantoesimerkkejä lukuunottamatta.

Voit vaihtaa kieltä A+:n valikon yläreunassa olevasta 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: C115.

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 the 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, and 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 abstract method totalCredits has no generic implementation for all kinds of courses. Its subclasses implement this method in different ways.

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

}

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

How recursion works

Is it magic?

Sometimes, a recursive method implementation is so simple and elegant (compared to, say, a while loop that does the same thing) 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
}

Recall the 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).

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

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

Palindromes: a recursive implementation

Here’s another palindrome-checking algorithm in pseudocode:

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

Notice:

• 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))
}

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. Strings aren’t recursively defined but the algorithm nevertheless keeps creating new strings — smaller problems to solve — and applying itself to them.

Question 1

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

Question 2

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

What about reverse?

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

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

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

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

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

Iteration vs. Recursion

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

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

	Iteration with loops	Recursion
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 vars and mutable collections. Example: we use two stepper variables to track the two indices within the candidate word. Example: We use a var to track which of the chained courses we’re currently working on. We modify that var on each iterative cycle. Another var serves as a gatherer where we accumulate the sum as we loop through the courses.	We can get the job done using only parameters and other val variables. Example: we pass the remaining (middle) part of the string as a parameter to the next frame, higher on the stack. Example: this points to a different course in each stack frame. The intermediate sums are produced and returned by different frames; we don’t need to modify the value of any variable.
Termination:	We stop repeating when we have advanced through the entire problem. Example: we exit the loop when the increasing “left index” meets the decreasing “right index”. Example: we loop until we hit a course that has no prerequisite.	When we’ve chipped away enough that only a little crumb of the original problem (a base case) remains, the solution is obvious and doesn’t need another recursive call. Example: when we have a string of at most one character, the solution is obvious. Example: if the course is an intro course, its total credits are obvious.
Constructing the solution:	Once we’ve gone through the entire problem, we have accumulated a solution. Example: by the time we’ve checked the whole string, we know if it’s a palindrome. Example: we track the sum in a gatherer variable, adding to it at each step. Once we’re done, the variable contains the final result.	We form an overall solution from the solution of the chipped-away piece and the solution of the reduced problem. Often, the overall solution will be some kind of combination of the two (such as a sum). Example: if the first and last characters are different (solution of chipped-away piece), the string is not a palindrome. Otherwise, the solution equals that of the remaining middle part (the reduced problem). Example: the “total credits” of a course is the sum of its own credit value (solution of chipped-away piece) and the total credits of the prerequisites (the reduced problem).

Recursion and induction

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

Writing a Recursive Method

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

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

def printSquares(upperLimit: Int) = {
  for (number <- 1 to upperLimit) {
    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)
  }
}

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

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

Here’s an animation of the same:

Question 1

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

def printSquares(upperLimit: Int): Unit = {
  if (upperLimit > 0) {
    printSquares(upperLimit)
    println(upperLimit * upperLimit)
  }
}

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

The code doesn’t print out any squares.

The compiler issues a complaint. The program cannot be run.

The program “runs in place” without requiring much memory but without stopping, either.

The program consumes additional memory until it can allocate no more: it attempts to create an “infinite” number of frames on the call stack before crashing.

The code doesn’t define a base case, so the recursion continues into negative parameter values.

There is a base case but the program never reaches it.

Question 2

What about this program?

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

The code doesn’t print out any squares.

The compiler issues a complaint. The program cannot be run.

The program “runs in place” without requiring much memory but without stopping, either.

The program consumes additional memory until it can allocate no more: it attempts to create an “infinite” number of frames on the call stack before crashing.

The code doesn’t define a base case, so the recursion continues into negative parameter values.

There is a base case but the program never reaches it.

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

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

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

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

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

Question 1

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

findBest gets called exactly three times.

findBest gets called some other number of times.

Each of the resulting findBest calls has a different value for its start parameter.

Each of the resulting findBest calls returns the same value.

Each of the resulting findBest calls returns a different value than the others.

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

1. 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.)
2. Can you re-implement the Option-based Course class with a loop instead of recursion? Is the resulting code pretty?
3. How would you change the code to allow any course to have any number of prerequisite courses?
4. What happens if the same course appears multiple times among the prerequisites? What if there’s a cycle in the prerequisite chain: A requires B and vice versa?

The reverse method

1. (Easiest:) Earlier in this chapter, we noted that it’s possible to implement isPalindrome simply by using the reverse method on strings. From an efficiency perspective, that solution isn’t optimal, though. Why?
2. (Harder:) Consider how you would implement a function like reverse. It should take a string parameter and return the same characters in reverse order. Don’t use the existing reverse method or any other methods on String that process the entire string. Can you come up with an iterative implementation and a recursive one?
3. (Intended mostly for readers who have prior programming experience and want to delve deeper into Scala’s implementation:) The source code of Scala’s core API is linked to its Scaladocs. Dig into that code and find out whether the API authors have used iteration or recursion to implement reverse. Warning: this isn’t as straightforward as one might first think; there are incidental complications that arise from the API’s design and documentation. Hint: do a web search for StringOps and “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 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

  Show the hintHide the hint

  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

  Show the hintHide the hint

  There are exactly this many ways to split S:

  1. the number of ways there are to split S without coin C; plus
  2. the number of ways there are to split the smaller amount S-V using all the permitted types of coins.

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

  What are the base cases?

  Show the hintHide the hint

  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₀) zero and the second (Fibonacci₁) 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 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.

Question 1

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

Question 2

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

Surely not.

Depends a lot on the computer.

Sure, if you pass in a ridiculously big number.

Yes, and you don’t even need a huge number as a parameter.

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

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

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

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

This implementation is rather elegant, and efficient too. Since the list is lazy, it doesn’t recompute the earlier numbers in the sequence but stores them as long as they are needed. Computing the 10000th Fibonacci number, 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.

One way to put this is: 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
  }
}

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.

Time spent: (*) Required

Please estimate the total number of minutes you spent on this chapter (reading, assignments, etc.). You don’t have to be exact, but if you can produce an estimate to within 15 minutes or half an hour, that would be great.

“I feel that I have understood the most important things in this chapter.” (*) Required

fully agree

somewhat agree

somewhat disagree

fully disagree

I’m unable to answer or don’t want to comment.

Written comment or question:

You aren’t required to give written feedback. Nevertheless, please do ask something, give feedback, or reflect on your learning! (However, the right place to ask urgent questions about programs that you’re currently working on isn’t this form but Piazza or the lab sessions. We can’t guarantee that anyone will even see anything you type here before the weekly deadline.)

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, and Nikolas Drosdek 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.

Posting submission...

×

Identical submission

This submission is identical to the previous submission . Are you sure you want to submit it?

Cancel Submit