Transcript Recursion

Recursion in Scala
Definitions



A recursive method is a method that calls itself
A method is indirectly recursive if it calls a method that
calls a method ... that calls the original method
Mutually recursive methods are methods that call each
other
2
Recursive functions...er, methods

The mathematical definition of factorial is:
factorial(n) is

We can define this in Scala as:



1, if n <= 1
n * factorial(n-1) otherwise
def factorial(n: Long) = {
if (n <= 1) 1
else n * factorial(n – 1);
}
This is a recursive function because it calls itself
Recursive functions are legal in almost all languages
3
Anatomy of a recursion
Base case: does some work
without making a recursive
call
def factorial(n: Long) = {
if (n <= 1) 1
else
n * factorial(n – 1)
}
Extra work to convert the
result of the recursive call
into the result of this call
Recursive case: recurs
with a simpler
parameter
4
The four rules



Do the base cases first
Recur only with simpler cases
Don't modify and use non-local variables



You can modify them or use them, just not both
Remember, parameters count as local variables,
but if a parameter is a reference to an object, only the
reference is local—not the referenced object
Don't look down
5
Another simple example

The following counts the number of elements in a list



scala> def count(list: List[Any]): Int = {
|
if (list.isEmpty) 0
|
else 1 + count(list.tail)
|}
count: (list: List[Any])Int
scala> count(List("ace", "deuce", "trey"))
res2: Int = 3
Note: For a recursive method, you must specify the return type
6
Parts of the simple example
def count(list: List[Any]): Int = {
| if (list.isEmpty) 0
| else 1 + count(list.tail)
|}
Extra work to
convert the result
of the recursive
call into the result
of this call
Base case: does some
work without making a
recursive call
Recursive case: recurs
with a simpler
parameter
7
Infinite recursion

The following is the recursive equivalent of an infinite loop:



def toInfinityAndBeyond (x: Int): Int = toInfinityAndBeyond(x)
This happened because we recurred with the same case!
While this is obviously foolish, infinite recursions can happen
by accident in more complex methods

def collatz(n: Int): Int =
if (n == 1) 1
else if (n % 2 == 0) collatz(n / 2)
else collatz(3 * n - 1)
8
Why recursion?

As long as we are dealing with linear data structures
(sequences), there isn’t much need for recursion


Although it can be very handy for lists
Next semester we will be working with many
recursively-defined data structures

Example: A binary tree is a data structure consisting of




A value
An optional left binary tree, and
An optional right binary tree
The best way to work with recursively-defined data
structures is with recursive functions
9
Binary trees

scala> class BinaryTree(value: Any, left: Option[BinaryTree],
right: Option[BinaryTree]) {
|
override def toString = s"($value $left $right)"
| }
defined class BinaryTree
scala> val l = new BinaryTree("I'm left", None, None)
l: BinaryTree = (I'm left None None)
scala> val r = new BinaryTree("I'm right", None, None)
r: BinaryTree = (I'm right None None)
scala> val root = new BinaryTree("I'm the root!", Some(l), Some(r))
root: BinaryTree = (I'm the root! Some((I'm left None None))
Some((I'm right None None)))
10
Merging sorted lists

scala> def merge(list1: List[Int], list2: List[Int]): List[Int]
= {
| if (list1 isEmpty) list2
| else if (list2 isEmpty) list1
| else if (list1.head < list2.head) list1.head ::
merge(list1.tail, list2)
| else list2.head :: merge(list1, list2.tail)
| }
warning: there were 2 feature warning(s); re-run with -feature
for details
merge: (list1: List[Int], list2: List[Int])List[Int]
scala> merge(List(1, 4, 5, 7, 11), List(2, 3, 5, 10, 20))
res1: List[Int] = List(1, 2, 3, 4, 5, 5, 7, 10, 11, 20)
11
Reprise




Do the base cases first
Recur only with a simpler case
Don't modify and use nonlocal variables
Don't look down
12
The End
13