Recursion
Recursion first appeared in this book in chapter 6 when it was used to provide basic iteration. This was extended upon in chapter 15 where the memory of the stack was utilized with recursive functions that call themselves more than once. This chapter will revisit the concept of recursion to help solidify it in your mind.1 The next three chapters will utilize recursion, making this an ideal time to provide a refresher and integrate it into our project.
28.1 Refresher
A recursive function is nothing more than a function that calls itself. This means that it is defined in terms of itself. This seemingly circular type of definition works because all recursive functions need some form of base case where they do not call themselves. The other cases should progress toward the base case. Recursive functions that only call themselves once provide iteration and are typically replaced with loops in most programming languages.2
The real power of recursion comes out when a function calls itself more than once. This allows a recursive function to test multiple alternatives. The memory of the stack is essential to this as what really happens is that one call is executed, and after it has finished, the stack keeps track of where the code was and it is done again. Functions like this can be converted into loops, but it typically requires significantly more effort. We saw in chapter 15 how certain problems that would be quite challenging to solve using normal loops, could be dealt with very easily by means of recursive code.
28.2 Project Integration: A Maze
One of the problems that we considered in chapter 15 was that of completing a maze. In particular, we wanted to find the length of the shortest path through the maze. The recursive approach that was taken also lent itself well to similar problems like finding the longest path through the maze or finding how many paths there were through the maze. Mazes are something that humans like to represent graphically. As such, they lend themselves to being put into our drawing program.
To do this we will create a drawable for the maze. The final code put together is shown here. We will go through different parts of it in the subsections that follow.
package scalabook.drawing
import java.awt.{Graphics2D,Color}
import java.awt.geom._
import scala.swing._
import scala.swing.event._
import actors.Actor
class DrawMaze(p:DrawTransform,m:Seq[Seq[Int]],
private var ex:Int,
private var ey:Int) extends DrawLeaf with Clickable {
val parent = p
private var maze = m.map(_.toArray).toArray
@transient private var propPanel:Component = null
@transient private var clickAction:(Int,Int)=>Unit = null
def draw(g:Graphics2D) {
lastTransform = g.getTransform()
g.setPaint(Color.black)
g.drawRect(-1,-1,20∗maze.length+1,20∗maze(0).length+1)
for(i <- 0 until maze.length; j <- 0 until maze(i).length) {
g.setPaint(maze(i)(j) match {
case -1 => Color.black
case -2 => Color.yellow
case 0 => Color.white
case s => new Color(0,(255-s) max 0,0)
})
g.fillRect(i∗20,j∗20,20,20)
}
g.setPaint(Color.green)
g.fillOval(ex∗20,ey∗20,20,20)
}
def propertiesPanel() : Component = {
if(propPanel == null) {
import BorderPanel.Position._
propPanel = new BorderPanel {
layout += new BorderPanel {
layout += new GridPanel(2,1) {
contents += new Label("Width")
contents += new Label("Height")
} -> West
layout += new GridPanel(2,1) {
contents += new TextField(maze.length.toString) {
listenTo(this)
reactions += {case e:EditDone =>
val size = text.toInt
if(size>5) resize(size,maze(0).length)
}
}
contents += new TextField(maze(0).length.toString) {
listenTo(this)
reactions += {case e:EditDone =>
val size = text.toInt
if(size>5) resize(maze.length,size)
}
}
} -> Center
val radioButtons = Seq(
new RadioButton {action = Action("Draw Walls") {
clickAction = (x,y) => {
maze(x)(y) = if(maze(x)(y) == -1) 0 else -1
drawing.refresh
}
}},
new RadioButton {action = Action("Place Exit") {
clickAction = (x,y) => {
ex = x
ey = y
drawing.refresh
}
}},
new RadioButton {action = Action("Shortest Path") {
clickAction = (x,y) => Actor.actor {
Dialog.showMessage(propPanel,"The shortest path has length " +
shortestPath(x,y) + ".")
drawing.refresh
}
}},
new RadioButton {action = Action("Shortest Path Fast") {
clickAction = (x,y) => Actor.actor {
Dialog.showMessage(propPanel,"The shortest path has length " +
shortestPathFast(x,y,0) + ".")
drawing.refresh
}
}}
)
val group = new ButtonGroup(radioButtons:_∗)
layout += new GridPanel(radioButtons.length+1,1) {
radioButtons.foreach(rb => contents += rb)
contents += Button("Clear Breadcrumbs") {
for(i <- maze.indices; j <- maze(i).indices)
if(maze(i)(j)>0) maze(i)(j) = 0
drawing.refresh
}
} -> South
} -> North
}
}
propPanel
}
override def toString() = "Maze"
def toXML : xml.Node = {
<drawMaze ex={ex.toString} ey={ey.toString}>
{maze.map(_.mkString(",")).mkString("
")}
</drawMaze>
}
def react(evt:Event,cx:Double,cy:Double) {
evt match {
case mc:MouseClicked =>
val x = cx.toInt/20
val y = cy.toInt/20
if(x>=0 && x<maze.length && y>=0 && y<maze(x).length && clickAction!=null) {
clickAction(x,y)
}
case _ =>
}
}
private def resize(w:Int,h:Int) {
maze = Array.tabulate(w,h)((i,j) => {
if(i<maze.length && j<maze(i).length) maze(i)(j) else 0
})
drawing.refresh
}
private def shortestPath(x:Int,y:Int):Int = {
if(x==ex && y==ey) 0
else if(x<0 || x>=maze.length || y<0 || y>=maze(x).length || maze(x)(y)<0) {
1000000000
} else {
maze(x)(y) = -2
drawing.refresh
Thread.sleep(10)
val ret = 1+(shortestPath(x+1,y) min
shortestPath(x-1,y) min
shortestPath(x,y+1) min
shortestPath(x,y-1))
maze(x)(y) = 0
ret
}
}
private def shortestPathFast(x:Int,y:Int,steps:Int):Int = {
if(x==ex && y==ey) 0
else if(x<0 || x>=maze.length || y<0 || y>=maze(x).length || maze(x)(y)<0) {
1000000000
} else if(maze(x)(y)>0 && maze(x)(y)<=steps) {
1000000000
} else {
maze(x)(y) = steps
drawing.refresh
Thread.sleep(10)
val ret = 1+(shortestPathFast(x+1,y,steps+1) min
shortestPathFast(x-1,y,steps+1) min
shortestPathFast(x,y+1,steps+1) min
shortestPathFast(x,y-1,steps+1))
ret
}
}
}
object DrawMaze {
def apply(p:DrawTransform,data:xml.Node) = {
new DrawMaze(p,
data.text.trim.split("
").map(_.split(",").map(_.toInt).toSeq).toSeq,
(data"@ex").text.toInt,
(data"@ey").text.toInt)
}
def apply(p:DrawTransform) = {
new DrawMaze(p,
Seq(Seq(0,-1, 0, 0, 0, 0, 0, 0, 0, 0),
Seq(0,-1, 0,-1,-1,-1,-1,-1,-1, 0),
Seq(0,-1, 0,-1, 0, 0, 0, 0, 0, 0),
Seq(0,-1, 0,-1, 0,-1,-1,-1,-1,-1),
Seq(0, 0, 0,-1, 0, 0, 0, 0, 0, 0),
Seq(0,-1,-1,-1,-1,-1,-1,-1,-1, 0),
Seq(0,-1, 0, 0, 0, 0, 0, 0,-1, 0),
Seq(0,-1, 0,-1, 0, 0,-1, 0, 0, 0),
Seq(0,-1, 0,-1,-1, 0,-1,-1,-1,-1),
Seq(0, 0, 0,-1, 0, 0, 0, 0, 0, 0)),
9,9)
}
}
Clicking on the maze in the drawing activates different functionality depending on what the user selects. This includes finding the shortest path through the maze.
28.2.1 Revisiting the Basic Approach
The shortestPath method uses the approach that we covered previously. This tests all paths through the maze and returns the length of the shortest one. The code for this method is shown here.
private def shortestPath(x:Int,y:Int):Int = {
if(x==ex && y==ey) 0
else if(x<0 || x>=maze.length || y<0 || y>=maze(x).length || maze(x)(y)<0) {
1000000000
} else {
maze(x)(y) = -2
drawing.refresh
Thread.sleep(10)
val ret = 1+(shortestPath(x+1,y) min
shortestPath(x-1,y) min
shortestPath(x,y+1) min
shortestPath(x,y-1))
maze(x)(y) = 0
ret
}
}
The base cases are getting to the exit, which returns 0 as the number of steps that need to be taken to get to the exit, and going out of bounds, which returns 1000000000 as a number that can not be the solution and will not ever be the minimum. That is significant because the recursive case makes recursive calls in the four different directions and takes the minimum of them.
The line maze(x)(y) = -2 is dropping a "breadcrumb" on the maze so that the computer does not run in loops. You can think of this as moving the recursion toward a base case. Negative values in squares are bases cases and this line makes another square negative before calling the recursion. That can only happen a finite number of times before the recursion runs out of empty squares. This action is reversed when the four recursive calls are done so that a square can be revisited on a future path that gets to it in a different way. The lines of code to refresh the drawing and sleep the thread are there simply to animate the search process. You can reduce the sleep length or remove that line completely to speed things up for mazes that take too long to solve.
28.2.2 Graphical Editing
This is the first drawable that truly needs to have the user interact with it using the mouse. Solving the maze requires a starting location that would be nice to be able to adjust. A proper maze should also be editable, allowing us to change the locations of walls as well as where the exit is. It would be possible to put this type of editing into the properties panel, but that is a bit silly considering that the maze is already being drawn in the drawing. There is no reason we should not be able to make it so that the user can interact with the maze through mouse activity on the maze in the drawing.
Of course, there are some challenges. These arise from three different sources. The most obvious challenge is that the panel the user will be clicking on is in the Drawing class, not in the DrawMaze or other Drawable types that we might want to have performing the reaction. Another challenge is that the elements in the drawing can be transformed so that the location of the click on the panel is very indirectly linked to the location of the click relative to the drawn object. The most obscure challenge, and perhaps the one that is hardest to figure out how to solve, is that we do not want to implement changes that break the serialization. All three of these problems can be partially addressed by adding the following trait and making some changes to the Drawing class.
package scalabook.drawing
import scala.swing._
import scala.swing.event._
import java.awt.geom._
trait Clickable {
@transient private var lReactor:Reactor = null
@transient protected var lastTransform:AffineTransform = null
def reactor = {
if(lReactor==null) {
lReactor = new Reactor {}
lReactor.reactions += {
case me:MouseEvent =>
val dest = new Point2D.Double
lastTransform.inverseTransform(me.point,dest)
react(me,dest.x,dest.y)
}
lastTransform = new AffineTransform
}
lReactor
}
def react(evt:Event,cx:Double,cy:Double)
}
The idea is that this trait should be inherited by any drawable that we want the user to be able to interact with using the mouse. The call to inverseTransform takes a click location from the screen coordinates to the coordinates of that drawable. In order to make this work, the line lastTransform = g.getTransform() has to be included in the draw method of that drawable.
The trait itself includes code for making a Reactor that deals well with serialization and keeps track of the transform the drawable was last drawn with. It also provides a special type that we can look for in the Drawing to determine if mouse information should be sent somewhere. To make this work, the following code has to be added to Drawing.
// This was added in the declarations at the top.
@transient private var currentReactor:Reactor = null
// It is used in this code that was added at the end of the executeOnSelection
// code in the TreeSelectionListener.
if(currentReactor!=null) {
currentReactor.deafTo(drawPanel.mouse.moves,
drawPanel.mouse.clicks,
drawPanel.mouse.wheel)
}
d match {
case r:Clickable =>
currentReactor = r.reactor
currentReactor.listenTo(drawPanel.mouse.moves,
drawPanel.mouse.clicks,
drawPanel.mouse.wheel)
case _ =>
}
The type information is significant for the match expression that checks if the selected Drawable is a subtype of Clickable. If it is, it remembers the reactor and sets it to listen for mouse events on the panel. When something else is selected, this reactor will be made deaf to those events.
Instead of creating a Clickable type, it is tempting to simply have the drawable inherit from Reactor directly. Indeed, this is what the author did originally. However, that breaks serialization as the Reactor type includes a link to non-serializable data. The code was reworked with the newly created Clickable trait to fix serialization, and it had the added benefit of allowing the transformation code to be consolidated. The full Event is passed through to the react method to allow matching as well as to provide screen coordinates in case those are desired.
Inside of the DrawMaze class, the react method uses integer division to find the block that was clicked, then uses a function variable called clickAction to determine what happens on a click. The value of clickAction is set when the user selects a radio button from the properties panel. This approach abstracts the behavior away from the react method and puts it directly into the radio button code so that the names shown to the user and the code for the behaviors are adjacent. Note that the path finding calls use Actor.actor to run in a separate thread because those actions can take a significant amount of time, and we want the event handling thread free to repaint for the animations.
28.2.3 Optimizing the Maze
If you played around with the maze some back in chapter 15 or with this code here, you might have noticed something. If you keep taking out wall after wall and run the shortest path function, as you remove walls, the function will start to run more and more slowly. At a certain point, you will make the maze empty enough that the function will take longer than you have the patience to let it run. This happens because the basic algorithm tests all possible paths to find the shortest. The number of possible paths is extremely large for an empty maze. The DrawMaze allows you to change the size as well. A 10 by 10 maze is sufficient to take many times longer than a human life if left empty, going to 20 by 20 or larger makes things far worse.
There are ways around this. The way we will discuss here makes the breadcrumbs smarter so that they can provide additional information so that paths which have no chance of being ideal are eliminated from consideration before they have been fully explored. The code for doing this is shown here.
private def shortestPathFast(x:Int,y:Int,steps:Int):Int = {
if(x==ex && y==ey) 0
else if(x<0 || x>=maze.length || y<0 || y>=maze(x).length || maze(x)(y)<0) {
1000000000
} else if(maze(x)(y)>0 && maze(x)(y)<=steps) {
1000000000
} else {
maze(x)(y) = steps
drawing.refresh
Thread.sleep(10)
val ret = 1+(shortestPathFast(x+1,y,steps+1) min
shortestPathFast(x-1,y,steps+1) min
shortestPathFast(x,y+1,steps+1) min
shortestPathFast(x,y-1,steps+1))
ret
}
}
This looks very similar to the earlier version, but there is an extra argument to the function, one extra base case, and the breadcrumbs are not picked up. The extra argument keeps track of how many steps have been taken along the current path. The breadcrumbs, instead of just marking that you have been to a square, keep track of how many steps it took to get there on the shortest path so far. The extra base case is for a room that is reached taking more steps than the current step count. In that situation, the path can not possibly be the shortest and the recursion is terminated.
If you make the maze big enough, even this approach will be insufficient. If you test an empty 30 by 30 maze you will discover this for yourself. An alternate approach is to abandon recursion completely and do a breadth-first search of the maze. By its nature, recursion is depth-first . This means that it goes as far down one path as possible before trying another path. For a shortest-path algorithm, the first solution reached is the winner. For that reason, it is more efficient to try all paths at the same time, taking one step forward on each. That approach works very well of a maze, but there are some problems for which the number of independent paths is so large that you can not keep track of all the different paths without running out of memory. The breadth-first approach also does not help with problems such as finding the longest path or counting the number of paths.
How Many Paths Are There?
You can empirically check to see that an empty maze takes a long time to solve. With a little work we can estimate more accurately how long it would take. Imagine a 10 by 10 empty maze. In the recursive case, the function calls itself four times. Some of those will lead to base cases and immediately return. For our estimate we will say that two of the calls are not base cases. So the initial call splits to two, which split to four, and so on. After n steps in the recursion, there are roughly 2n paths being worked on. The longest path in a 10 by 10 maze is 100 steps. To keep things simple we will stick with that number for how deep the recursion goes. It is an overestimate, but it is somewhat offset by assuming only two branches. This implies on the order of 2100 paths.
Hopefully, it is clear that 2100 is a very big number. Such big numbers can be hard for people to really comprehend. After all, computers are really fast. Modern computers run at clock frequencies of several gigahertz. To help us put this number into perspective, assume that your computer can do 109 recursive calls each second.3 We then use two other rough estimates: 210 ~ 103 and 1yr ~ 3 × 107sec. This gives us the following:
That is a few times longer than the best estimates for the current age of the Universe.
This type of exponential growth is common for recursive algorithms. If each non-base case calls the function m times and this goes n calls deep, then there will be mn total calls. For some problems, this seems to be unavoidable. A lot of effort goes into trying to find ways of getting around this. You should learn about approaches to dealing with this later in your studies.
28.3 Graph Traversals
A maze is a special case of a very general data structure called a graph. If you draw a bunch of dots and put lines between them, you have made a graph. If you are following the end-of-chapter projects, you might well have a form of a graph in the code that you are writing. For example, the multiuser text game has rooms that are connected by exits. That is an example of a graph. For a graphical game you might have different rooms/levels that have doors or other connections between them. This is also a graph.
Using the foundation of code that we created for the maze, it is not to hard to make a DrawGraph type which the user can interact with by clicking on the drawing. The full code is shown here. It is fairly long in large part because of the ability to interactively edit the graph. There is a text field that can be used to enter an integer weight for edges that are added to the graph.
package scalabook.drawing
import java.awt.{Graphics2D,Color}
import java.awt.geom._
import scala.swing._
import scala.swing.event._
import actors.Actor
import collection.mutable
class DrawGraph(p:DrawTransform,nloc:Seq[Point2D],edges:Seq[(Int,Int,Int)],en:Int)
extends DrawLeaf with Clickable {
val parent = p
import DrawGraph.{Node,Edge}
private val nodes = mutable.Buffer[Node]()
for(p <- nloc) nodes += new Node(p.getX(),p.getY())
for((f,t,w) <- edges) nodes(f).edges ::= new Edge(nodes(f),nodes(t),w)
private var endNode = if(en<0) {
if(nodes.nonEmpty) nodes(0) else null
} else nodes(en)
@transient private var propPanel:Component = null
@transient private var weight:TextField = null
@transient private var clickAction:(MouseEvent,Double,Double)=>Unit = null
@transient private var hoverNode:Node = null
@transient private var hoverEdge:Edge = null
@transient private var startNode:Node = null
@transient private var (dx,dy) = (0.0, 0.0)
@transient private var pathSet:Set[Node] = null
def draw(g:Graphics2D) {
def drawNode(n:Node) {
g.setColor(if(n == endNode) Color.green else Color.black)
g.fill(new Ellipse2D.Double(n.x-5,n.y-5,10,10))
if(n==hoverNode) {
g.setColor(Color.red)
g.fill(new Ellipse2D.Double(n.x-4,n.y-4,8,8))
}
}
def drawEdge(e:Edge) {
g.setColor(if(e==hoverEdge) Color.red else Color.black)
g.draw(new Line2D.Double(e.from.x,e.from.y,e.to.x,e.to.y))
g.drawString(e.weight.toString,0.5f∗(e.from.x+e.to.x).toFloat,
0.5f∗(e.from.y+e.to.y).toFloat)
}
for(n <- nodes) {
drawNode(n)
for(e <- n.edges; if(nodes.indexOf(e.from)<nodes.indexOf(e.to))) {
drawEdge(e)
}
g.setPaint(Color.black)
if(startNode!=null) g.draw(new Line2D.Double(startNode.x,startNode.y,dx,dy))
}
if(pathSet!=null) {
g.setPaint(Color.blue)
for(n <- pathSet) {
g.fill(new Ellipse2D.Double(n.x-2,n.y-2,4,4))
}
}
}
def propertiesPanel() : Component = {
if(propPanel == null) {
import BorderPanel.Position._
propPanel = new BorderPanel {
val radioButtons = Seq(
new RadioButton {action = Action("Add Node") {
clickAction = (e,x,y) => e match {
case mc:MouseClicked =>
nodes += new Node(x,y)
if(nodes.length==1) endNode = nodes(0)
case _ =>
}
}},
new RadioButton {action = Action("Add Edge") {
clickAction = (e,x,y) => e match {
case mp:MousePressed =>
if(hoverNode!=null) {
startNode = hoverNode
dx = startNode.x
dy = startNode.y
}
case mp:MouseDragged =>
if(startNode!=null) {
dx = x
dy = y
}
case mp:MouseReleased =>
if(startNode!=null && hoverNode!=null) {
startNode.edges ::= new
Edge(startNode,hoverNode,weight.text.toInt)
hoverNode.edges ::= new
Edge(hoverNode,startNode,weight.text.toInt)
}
startNode = null
case _ =>
}
}},
new RadioButton {action = Action("Move Node") {
clickAction = (e,x,y) => e match {
case mp:MousePressed =>
if(hoverNode!=null) {
startNode = hoverNode
dx = startNode.x
dy = startNode.y
}
case mp:MouseDragged =>
if(startNode!=null) {
startNode.x = x
startNode.y = y
dx = x
dy = y
}
case mp:MouseReleased =>
if(startNode!=null && hoverNode!=null) {
startNode.x = x
startNode.y = y
}
startNode = null
case _ =>
}
}},
new RadioButton {action = Action("Remove") {
clickAction = (e,x,y) => e match {
case mc:MouseClicked =>
if(hoverNode!=null) {
nodes -= hoverNode
for(n <- nodes) n.edges = n.edges.filter(_.to != hoverNode)
if(hoverNode==endNode && nodes.nonEmpty) endNode = nodes(0)
pathSet = null
} else if(hoverEdge!=null) {
hoverEdge.from.edges = hoverEdge.from.edges.filterNot(_ sameAs
hoverEdge)
hoverEdge.to.edges = hoverEdge.to.edges.filterNot(_ sameAs
hoverEdge)
}
case _ =>
}
}},
new RadioButton {action = Action("Set End") {
clickAction = (e,x,y) => e match {
case mc:MouseClicked =>
if(hoverNode!=null) {
endNode = hoverNode
}
case _ =>
}
}},
new RadioButton {action = Action("Reachable") {
clickAction = (e,x,y) => e match {
case mc:MouseClicked =>
if(hoverNode!=null) Actor.actor {
if(endNode!=null) {
Dialog.showMessage(propPanel,"The end node is"+
(if(canReach(hoverNode,mutable.Set())) "" else " not")+"
reachable.")
} else Dialog.showMessage(propPanel,"There must be an end node.")
}
case _ =>
}
}},
new RadioButton {action = Action("Shortest Path") {
clickAction = (e,x,y) => e match {
case mc:MouseClicked =>
if(hoverNode!=null) Actor.actor {
if(endNode!=null) {
shortestPath(hoverNode,Set()) match {
case None =>
Dialog.showMessage(propPanel,"There is no path.")
case Some((len,ps)) =>
Dialog.showMessage(propPanel,"There is a path of length
"+len+".")
pathSet = ps
drawing.refresh
}
} else Dialog.showMessage(propPanel,"There must be an end node.")
}
case _ =>
}
}}
)
val group = new ButtonGroup(radioButtons:_∗)
layout += new GridPanel(radioButtons.length+1,1) {
radioButtons.foreach(rb => contents += rb)
weight = new TextField("1")
contents += weight
} -> North
}
}
propPanel
}
override def toString() = "Graph"
def toXML : xml.Node = {
<drawGraph en={nodes.indexOf(endNode).toString}>
{nodes.map(n => <node x={n.x.toString} y={n.y.toString}/>)}
{for(n <- nodes; e <- n.edges) yield
<edge from={nodes.indexOf(e.from).toString}
to={nodes.indexOf(e.to).toString} weight={e.weight.toString}/>
}
</drawGraph>
}
def react(evt:Event,cx:Double,cy:Double) {
evt match {
case me:MouseEvent =>
hoverNode = null
hoverEdge = null
var lastDist = 1e100
for(n <- nodes) {
val dx = cx-n.x
val dy = cy-n.y
val dist = math.sqrt(dx∗dx+dy∗dy)
if(dist<10 && dist<lastDist) {
hoverNode = n
lastDist = dist
}
if(lastDist>3) for(e <- n.edges;
if(nodes.indexOf(e.from)<nodes.indexOf(e.to))) {
val line = new Line2D.Double(e.from.x,e.from.y,e.to.x,e.to.y)
val edist = line.ptSegDist(me.point).abs
if(edist<3 && edist<lastDist) {
hoverEdge = e
}
}
}
if(hoverNode!=null) hoverEdge = null
if(clickAction!=null) clickAction(me,cx,cy)
drawing.refresh
case _ =>
}
}
private def canReach(n:Node,visited:mutable.Set[Node]):Boolean = {
if(n==endNode) true
else if(visited(n)) false
else {
visited += n
n.edges.exists(e => canReach(e.to,visited))
}
}
private def shortestPath(n:Node,visited:Set[Node]):Option[(Int,Set[Node])] = {
if(n==endNode) Some(0 -> visited)
else if(visited(n)) None
else {
val newVisited = visited+n
n.edges.foldLeft(None:Option[(Int,Set[Node])])((last,e) => {
(last,shortestPath(e.to,newVisited)) match {
case (None,Some((len,v))) => Some((len+e.weight,v))
case (_,None) => last
case (Some((len1,_)), Some((len2,v))) => if(len1<=len2+e.weight) last
else Some(len2+e.weight,v)
}
})
}
}
}
object DrawGraph {
def apply(p:DrawTransform) = new DrawGraph(p,List(new
Point2D.Double(100,100)),List(),-1)
def apply(p:DrawTransform,n:xml.Node) = {
val end = (n "@en").text.toInt
val pnts = (n "node").map(pn => {
val x = (pn "@x").text.toDouble
val y = (pn "@y").text.toDouble
new Point2D.Double(x,y)
})
val edges = (n "edge").map(en => {
val from = (en "@from").text.toInt
val to = (en "@to").text.toInt
val weight = (en "@weight").text.toInt
(from,to,weight)
})
new DrawGraph(p,pnts,edges,end)
}
private class Node(var x:Double,var y:Double) extends Serializable {
var edges = List[Edge]()
}
private class Edge(val from:Node,val to:Node,val weight:Int) extends Serializable
{
def sameAs(e:Edge):Boolean = {
weight==e.weight && ((from==e.from && to==e.to) || (from==e.to && to==e.from))
}
}
}
In general, the edges in graphs can be directed so that they only go from one node to another, and not back. The way we store the nodes in the example would allow that flexibility, but the code maintains two-way linkages so that the user interface does not have to be able to distinguish two connections between the same two nodes.
The similarity to the DrawMaze type should enable you to read most of this code fairly easily. You should put this into your project, add appropriate code to Drawing and DrawTransform to handle adding this type and loading it from XML, then play with it for a while. The main aspect that we want to focus on here are the two methods that recursively run through the graph as some of the project options include adding similar functionality to your code.
The first method simply checks if the end node can be reached from the one that you click on. This method uses a mutable set to keep track of the nodes that have been visited. This set serves the purpose of "breadcrumbs" in this algorithm. The use of a Set type is for the purposes of efficiency. Having the set be mutable gives us a behavior like an algorithm that does not pick back up the breadcrumbs. This is fine here because we only want to know if a node can be reached. We are completely unconcerned with the path that is taken.
private def canReach(n:Node,visited:mutable.Set[Node]):Boolean = {
if(n==endNode) true
else if(visited(n)) false
else {
visited += n
n.edges.exists(e => canReach(e.to,visited))
}
}
The base cases are reaching the end node and hitting a node that has already been visited. Each time a node is visited, that node is added into the set. The recursion occurs in a call to exists on the edges coming out of the current node. The exists method is ideal for us because it will stop execution if any of the elements that are run through produce a value of true. So if the first edge from a node manages to reach the end, none of the other edges need to be taken.
The second method is another shortest path algorithm, but this time on a weighted graph instead of a maze. Here again a set is passed in to keep track of the visited elements. In this case, it is immutable because the path is significant and we need to pick up the breadcrumbs. This method also has a significantly more complex return type. It is Option[(Int,Set[Node])]. The Option part indicates that it is possible that there is no solution. This would be the case if the end were not reachable from the selected start node. This approach is generally preferred over using null to indicate that nothing worked. The Int is the length of the path, and the Set[Node] is all the nodes that were visited on the path that was found. This technically is not the same as returning a path, but it provides enough information that the user can easily figure out the path taken in most situations. It was also easy to build as we are keeping track of the visited nodes using immutable sets anyway.
private def shortestPath(n:Node,visited:Set[Node]):Option[(Int,Set[Node])] = {
if(n==endNode) Some(0 -> visited)
else if(visited(n)) None
else {
val newVisited = visited+n
n.edges.foldLeft(None:Option[(Int,Set[Node])])((last,e) => {
(last,shortestPath(e.to,newVisited)) match {
case (None,Some((len,v))) => Some((len+e.weight,v))
case (_,None) => last
case (Some((len1,_)), Some((len2,v))) => if(len1<=len2+e.weight) last
else Some(len2+e.weight,v)
}
})
}
}
The base cases here are the same as for the reachable method. They simply return slightly different values. The recursive case is also a bit longer to deal with the different options. It uses a fold to compile an answer, running through the different edges out of the current node. The fold starts with a value of None specifying the appropriate type. The function in the fold does a match on the incoming value and the recursive call of the current edge. When there is a None, the other value is used. If both of the values are a Some, a pattern is used to pull out the length so the shorter one can be returned. The patterns for the match here display the use of to produce names for the minimum number of values.
This shortest path solution for the graph is just like the original solution to the maze and has the same pitfalls in that it can take exponentially long for large graphs. Here again, there are alternate approaches that can produce superior performance. Graphs can be used to represent many different systems and algorithms on them are a significant concept that you should see much more of during your computing career.
28.4 Divide and Conquer
One standard problem-solving technique that uses recursion is the divide and conquer approach. The idea is to take a big problem, and cut it into two or more smaller pieces, solve those pieces, then combine the results into a complete solution. This is similar to the idea behind problem decomposition that we first talked about in chapter 5. The standard approach to solving hard problems is that they should be broken down into easier problems. It is an essential aspect of programming, as programs can be arbitrarily complex. A similar approach can be used in programs to solve problems.
Divide and conquer is recursive, because the function that solves the whole problem is used to solve the pieces as well. The base case is whenever you get down to a size that you can solve without breaking it down. Often this has you go all the way down to the point of being trivial. The recursion moves you toward the base case as each recursive call is on a smaller problem than what you started with. We will explore several different examples of divide and conquer algorithms to see how this approach works.
The first examples of divide and conquer that we will consider are sorting algorithms that we looked at briefly in chapter 15, mergesort and quicksort. Both of these sorts work by taking a sequence of numbers and breaking it into two pieces that are handled recursively. The default base case is a single element as an array with one element is always properly sorted. However, it can be more efficient to stop the recursion at some larger number of elements and switch to one of the sorts that we have explored previously to finish off the smaller segments.
28.4.1 Merge Sort
Merge sort works by recursively dividing the array in two equal parts4 and recursively calls on those two parts. The real work in a merge sort happens as the code pops back up the call stack and the sorted subsections are merged together. One of the key advantages of a merge sort is that it is remarkably stable in how much work it does. It always divides down the middle so the recursion always goes log2(n) levels deep. The merge operation for two lists of n/2 elements requires n − 1 comparisons and n memory moves. Given this, a merge sort will always scale as O(n log2(n)), regardless of the form of the input.
The primary disadvantage of a merge sort is that it can not be done in-place. This is because you can not merge an array with two halves that are independently sorted into a single sorted array without using extra space. This make a merge sort rather well suited for lists, which merge easily, but are immutable so the idea of in-place operations does not make sense. Writing a merge sort that works with arrays and does not consume more than O(n) memory is a bit trickier.
We begin with the simplest form of merge sort. This is a sort of a List that uses a recursive merge. The code for that functions is shown here.
def mergeSort[A](lst:List[A])(comp:(A,A)=>Int):List[A] = {
def merge(l1:List[A],l2:List[A]):List[A] = (l1,l2) match {
case (_,Nil) => l1
case (Nil,_) => l2
case (_,_) =>
if(comp(l1.head,l2.head)<=0) l1.head :: merge(l1.tail,l2)
else l2.head :: merge(l1,l2.tail)
}
val len = lst.length
if(len<2) lst
else {
val (front,back) = lst.splitAt(len/2)
merge(mergeSort(front)(comp),mergeSort(back)(comp))
}
}
Note that the merge function is nested inside of mergeSort. This works well as it prevents it from being accessed by outside code and gives it implicit access to the comparison function. The body of the primary method appears at the bottom which has a base case for lists with a length of less than two. Otherwise it splits the list at the midpoint, recursively calls sort on the halves, and merges the result. The length of the list is stored in a variable because it is an O(n) call that we do not want to repeat more than is required.
The merge here is recursive with three cases. If either list is empty, the result is the other list. When neither is empty, a comparison of the two heads is performed and the lesser is consed on the front of the merge of what remains. This is fairly simple code for a sort that promises O(n log(n)) performance, but unfortunately, it will not work well for long lists. The recursive merge function is not tail recursive and, as a result, it can overflow the stack if the lists being merged are too long. This limitation can be removed by using a merge function that employs a while loop.
def merge(l1:List[A],l2:List[A]):List[A] = {
var (lst1,lst2,ret) = (l1,l2,List[A]())
while(lst1.nonEmpty || lst2.nonEmpty) {
if(lst2.isEmpty || (lst1.nonEmpty && comp(lst1.head,lst2.head)<=0)) {
ret ::= lst1.head
lst1 = lst1.tail
} else {
ret ::= lst2.head
lst2 = lst2.tail
}
}
ret.reverse
}
This function builds the merged list in reverse order, then calls the reverse method to turn it around. This might seem odd, but remember that adding to the head of a List is O(1) while adding to the tail is O(n). For this reason, it is significantly more efficient to take the approach shown here than to append and not reverse.
This gives us a reasonably good merge sort for lists. The use of an immutable type for sorting forces us to create a separate storage for the result. When dealing with an array, however, the mutability means that many sorts can use no more memory than the provided array and one temporary space holder. As was mentioned above, that is not an option for the merge operation. However, using the style we used for the list when dealing with an array would be extremely inefficient, requiring O(n log(n)) memory. It turns out that we can fairly easily create an array-based version that uses 2n ∈ O(n) memory by making a second array and doing merges from the original array to the second array and back. The following code demonstrates that.
def mergeSort[A : Manifest](a:Array[A])(comp:(A,A)=>Int) {
val data = Array(a,new Array[A](a.length))
def mergeSortRecur[A](start:Int,end:Int,dest:Int) {
val src = 1-dest
if(start==end-1) {
if(dest==1) data(dest)(start) = data(src)(start)
} else {
val mid = (start+end)/2 // Can fail for arrays over 2^30 in length
mergeSortRecur(start,mid,src) mergeSortRecur(mid,end,src)
var (p1,p2,pdest) = (start,mid,start)
while(pdest<end) {
if((p2>=end || comp(data(src)(p1),data(src)(p2))<=0) && p1<mid) {
data(dest)(pdest) = data(src)(p1)
p1 += 1
} else {
data(dest)(pdest) = data(src)(p2)
p2 += 1
}
pdest += 1
}
}
}
mergeSortRecur(0,a.length,0)
}
Here the first line creates an Array[Array[A]] that holds the original array and our second array which is allocated to be the same size. There is a nested recursive function declared that takes the start and end of the range we are sorting as well as the index of the destination in data. That destination alternates between 0 and 1 as we go down the call stack. The merge is done from src into dest. The initial call uses a destination of 0 so the final sorted version winds up being in the original array.
The comment on the calculation of mid is worth noting. For arrays with a bit more than a billion elements, the quantity start+end can overflow and Int. This will lead to a negative value for mid. You can get around this by using mid = start+(end-start)/2 instead. This expression will work for all legal array sizes.
28.4.2 Quicksort
A second sorting example of divide and conquer is the quicksort. Unlike merge sort, the quicksort can be done in-place and, when written that way, it does all of its work going down the stack instead of on the way back up. Unlike merge sort, the quicksort is less stable and can degrade to O(n2) performance. This happens due to poor selection of a pivot. Recall from chapter 15 that a quicksort works by selecting one element to be the "pivot" and then moves elements around so that the pivot is in the correct location. If pivots are selected which belong near the middle of the array, this produces O(n log(n)) performance. However, if you consistently pick elements near the edges, the recursion has to go O(n) levels deep and the resulting performance is truly horrible. The version written back in chapter 15 will do exactly that for sorted data, in addition to the overhead of not occurring in-place. Just selecting a pivot at random makes this type of behavior unlikely. With a bit more logic, we can make it almost impossible.
We will start with a general version of an in-place quicksort that can be easily modified in regards to picking a pivot. This first version always uses the first element, but it has that pulled off in a function so that it is easy to modify.
def quicksort[A](a:Array[A])(comp:(A,A)=>Int) {
def pickPivot(start:Int,end:Int) = start
def qsRecur(start:Int,end:Int) {
if(start<end-1) {
val pivot = pickPivot(start,end)
val p = a(pivot)
a(pivot) = a(start)
a(start) = p
var (low,high) = (start+1,end-1)
while(low<=high) {
if(comp(a(low),p)<=0) {
low += 1
} else {
val tmp = a(low)
a(low) = a(high)
a(high) = tmp
high -= 1
}
}
a(start) = a(high)
a(high) = p
qsRecur(start,high)
qsRecur(low,end)
}
}
qsRecur(0,a.length)
}
This code retains that unfortunate characteristic that is used on a sorted array, it will have O(n2) performance. However, that can be corrected by making the following change.
def pickPivot(start:Int,end:Int) = start + util.Random.nextInt(end-start)
This modified pickPivot function picks a random value for the pivot. It can still have O(n2) behavior, but the odds are very low, especially for large arrays, as it requires randomly picking elements that are near the smallest or the largest in a range repeatedly.
The behavior of quicksort can be improved further by incorporating a bit more logic into the pivot selection and by using insertion sort when the segment we are sorting gets small enough. It might seem counterintuitive to rely on a sort that we know is O(n2) to help improve a sort that is supposed to be O(n log(n)), however, this can be understood by remembering that order notation is really only relevant for large values of n. When n is small, the sorts that we normally think of as being inferior can actually demonstrate significantly better performance. Code that incorporates both of these improvements is shown here.
def quicksort[A](a:Array[A])(comp:(A,A)=>Int) {
def insertionSort(start:Int,end:Int) {
for(i <- start+1 until end) {
val tmp = a(i)
var j = i-1
while(j>=0 && comp(a(j),tmp)>0) {
a(j+1) = a(j)
j -= 1
}
a(j+1) = tmp
}
}
def pickPivot(start:Int,end:Int) = {
val mid = start + (end-start)/2
val sm = comp(a(start),a(mid))
val se = comp(a(start),a(end-1))
if(sm<=0 && se>=0 || sm>=0 && se<=0) start
else {
val me = comp(a(mid),a(end-1))
if(sm<=0 && me<=0 || sm>=0 && me>=0) mid else end-1
}
}
def qsRecur(start:Int,end:Int) {
if(start<end-7) {
val pivot = pickPivot(start,end)
val p = a(pivot)
a(pivot) = a(start)
a(start) = p
var (low,high) = (start+1,end-1)
while(low<=high) {
if(comp(a(low),p)<=0) {
low += 1
} else {
val tmp = a(low)
a(low) = a(high)
a(high) = tmp
high -= 1
}
}
a(start) = a(high)
a(high) = p
qsRecur(start,high)
qsRecur(low,end)
} else {
insertionSort(start,end)
}
}
qsRecur(0,a.length)
}
The pivot selection works by finding the median of the first, middle, and last elements in the range. While technically this only eliminates selecting the smallest or largest element, it improves the probability of picking an element near the middle dramatically. It also provides ideal performance for arrays that were already sorted.
This method of picking a pivot also calls for using something other than quicksort below three elements. After all, the pivot selection process does not make sense if the first, middle, and last elements are not different. In this code, we have switched over to an insertion sort for any array with fewer than seven elements. This value was selected using some empirical testing to count the number of comparisons that were performed on random data sets.
28.4.3 Formula Parser
The last divide and conquer problem we will consider in this chapter is the problem of formula parsing. Consider an application where you want the user to be able to type in basic math formulas for evaluation. This would give you applications somewhat like graphing calculators, which can evaluate expressions the way you would write them on paper. So if the user were to enter "3+5∗2" you want a function that can take that as a String and return the value 13.5
There are a number of different approaches to this. One approach divides the formula at the lowest precedence operator, recurses on the two sides of that operator, and then applies the operator to the two return values at get an answer. If no operator is found, we have a base case for a number or we could write code to support parentheses, in which case the function should recurse on the contents of the parentheses.
An object with a method called eval for doing just this is shown here. It simply calls the recursive function, passing the formula with all spaces removed. The parse defines some variables, then has a loop that finds the lowest precedence operator. It ends with a set of ifs to deal with different possibilities.
package scalabook.util
object Formula {
val ops = "+-∗/".toSet
def eval(form:String):Double = evalParse(form.filter(_!=’ ’))
private def evalParse(f:String):Double = {
var opLoc = -1
var parensCount = 0
var i = f.length-1
while(i>0) {
if(f(i)==’(’) parensCount += 1
else if(f(i)==’)’) parensCount -= 1
else if(parensCount==0 && (f(i)==’+’ || f(i)==’−’ && !ops.contains(f(i-1)))) {
opLoc = i
i = -1
} else if(parensCount==0 && opLoc == -1 && (f(i)==’∗’ || f(i)==’/’)) {
opLoc = i
}
i -= 1
}
if(opLoc<0) {
if(f(0)==’(’) {
evalParse(f.substring(1,f.length-1))
} else f.toDouble
} else {
f(opLoc) match {
case ’+’ => evalParse(f.take(opLoc))+evalParse(f.drop(opLoc+1))
case ’−’ => evalParse(f.take(opLoc))-evalParse(f.drop(opLoc+1))
case ’∗’ => evalParse(f.take(opLoc))∗evalParse(f.drop(opLoc+1))
case ’/’ => evalParse(f.take(opLoc))/evalParse(f.drop(opLoc+1))
}
}
}
}
The first variable is opLoc, which should store the location of the operator. It is initialized to -1 and if no operator is found, it will still have that value at the end. After that is parensCount, which keeps track of how deeply nested we are in parentheses. The function is written so that no operator that is in parentheses can be considered to be top level. Last is a loop variable, i, which starts at the end of the string. The operators we are using are all left-associative, so the lowest precedence operator will be the furthest right.
The while loop starts off with checks to see if there is a parentheses. After that are checks to see if we have found different operators. There are some details to these that are worth noting. Both of the operator checks require that the parentheses count be zero. The check for a minus sign also requires that the character in front of it not be an operator. This is to make sure that formulas like "5+-3" work. In this situation, the '-' is negation, not a binary operator. When either '+' or '-' are found, the location is stored in opLoc, and the value of i is set to be negative so the loop will stop. This is because the first addition or subtraction that is found will always be the lowest precedence operator.
For multiplication and division, the behavior is a bit different. That characters only matter if opLoc is -1 and they do not change the value of i. This is because finding a '∗' or '/' does not automatically mean we have found the lowest precedence operator. There could still be a '+' or '-' further left that would have lower precedence. For that reason, the loop must continue working. However, if another '∗' or '/' is found to the left of the first one seen, it should be skipped over because of the associativity.
We will continue playing with the formula parser in later chapters. In the next chapter we will add the ability to handle variables. That will let us include formulas in our project. We do not want to do it with this code, because string parsing is fundamentally slow and we do not want to use code that parses the string every time a formula is evaluated.
28.5 End of Chapter Material
28.5.1 Summary of Concepts
This chapter was intended to give you another look at recursion and to explore some algorithms that use it in a bit more detail.
- Algorithms for optimal path finding through a maze.
- The brute force method checks all paths and picks the shortest. There can be a huge number of paths making this impractical for some situations.
- Using "smart breadcrumbs" allows for certain paths to be ignored as soon as it is found that they can not be correct.
- A drawable can be made to respond to mouse clicks on the drawing.
- We took our first look at graphs. These combine nodes and edges and can be used to represent many different types of problems.
- Code for a reachability algorithm does recursive edge following with a mutable set of visited nodes.
- Code for a shortest-path algorithm does recursive edge following with an immutable set of visited nodes.
- Divide and conquer algorithms. These take a large problem and break it into pieces, solve the pieces, and combine the solutions to get a final answer. The base case it typically when you get down to a size that the solution is trivial.
- Revisited merge sort and quicksort and explored a number of implementations of them.
- Wrote a divide and conquer solution to formula parsing that allows basic operators and parentheses.
28.5.2 Exercises
- Add a longest path function and Graphical User Interface (GUI) option to the DrawMaze.
- Add a path count function and GUI option to the DrawMaze.
- Make the animations thread safe by preventing clicks from going through while a maze solution is being calculated.
- Compare the speed of the different mergesort and quicksort versions.
- Extend the formula parser so that it can also do square roots and the three basic trigonometric functions.
28.5.3 Projects
- It is now time to implement a number of additional commands in your MUD. Hopefully you have been adding things to make it playable and working on having a real map. In a real MUD, map editing is something that can be done by certain users using standard commands from inside the MUD. You should not have to go out and edit XML by hand or anything like that. If you have not yet added this functionality to your MUD, you should now.
There are some other commands that will be very handy for anyone trying to build a map, mainly to check that the result looks the way you want. In particular, you need to be able to jump to random rooms, check if you can get from one room to another, and see how many paths there are between rooms. These are not normal commands. They should only be available to users who have the rights for creating rooms. The last two can be written as recursive algorithms that run from room to room following the exits that connect them.
- A good recursive problem for the web spider is to determine how many clicks it takes to get from one page to another. Closely related to that, you can measure distances, in clicks, between different data elements in a data set.
- Recursion can be used for a number of different tasks in graphical games. Which you pick really depends on what your game is like. All are at least roughly related to the maze algorithm. If your game has multiple screens that are connected (picture classic Zelda) it could be useful to have a tool that tells you how different screens are connected.
If your game has computer-controlled characters and obstacles that can block movement, then a recursive algorithm can be used to find a route from the character to the player. Note that in general, you do not want to allow an Artificial Intelligence (AI) to follow the shortest route to the player. The reason being that it becomes impossible for the player to evade the enemy.
- If you are doing the math worksheet project, you should add the ability for the user to define functions with names. Then make it so that the definition of one function can include a call to another function. This will use recursion in your code. You do not have to go all the way of including conditionals in the functions so that the functions themselves can be recursive. You are certainly allowed to try, but that is functionality that you will be able to add in later.
- Every good paint program needs a flood fill option. Your Photoshopn® project is no exception. Flood fill can be written in a very compact form using recursion. You should implement this and try it. What you will find if you have a large image is that you can easily overflow the stack by clicking in an open area.
To avoid this, you have to switch from using recursion to using a loop with a manual stack or queue for keeping track of things. If you use a stack, the order of the fill will match what happens in recursion. If you use a queue, you get a breadth-first ordering instead. For this application, the difference will not be significant.
- In chapter 26 you added a collisional simulation to the simulation workbench using a priority queue. That code has two different aspects that force every step to take O(n2) time, the comparison of particles to determine collision times, and the inserting of items into a sorted linked list priority queue. We will look at one way to improve on the first of these.
Currently your code finds collisions by doing comparisons between every pair of particles in the simulation. In reality, collisions are localized. During the fairly short period of time represented by a timestep in the simulation, it generally is not possible for a particle to collide with other particles on the opposite side of the simulation area. Technically, you can only collide with particles where , where d is the distance between the particles, is the length of the timestep, and and are the velocities of the two particles. For this reason, you really only need to compare to things that are close by. The problem is, you do not know in advance what is close by.
One way to deal with this is to maintain in each particle knowledge of its nearest neighbors. Have each particle keep track of the closest m other particles. The value of m should probably be at least four for a 2-D simulation and six to eight for a 3-D simulation. Building those connections initially requires a full search and O(n2) checks. After it has been built, searches for particles to do collision checks against can be done with a recursive search running through the connections. The search can stop anytime it gets to a particle that is too far away.
This same method can also be used to maintain the closest m particles. If the recursive search ever hits a particle that is closer than one of the one currently being tracked, the new one can replace it. Every so often another O(n2) search can be done to make sure the connections are all good, but this allows most of the steps to be done with each particle compared to a significant smaller number of other particles.
1Recursion is a topic many students struggle with, but which is very powerful, so there is value in returning to it several times.
2It is worth noting that even if a function only calls itself once, it can still benefit from being recursive if it does some work as it pops back up the stack. We will see examples of this in chapter 29.
3It is very unlikely your computer can do this as going through our function requires hundreds of clock cycles, but it is a reasonable assumption for the level of detail being considered here.
4Or within one of being equal in the case of odd numbers of elements.
5This example was chosen because it illustrates that we want to have proper order of operations so that multiplication is done before addition.