[Tutorial] Recursion

[zylum]

Recursion:

Introduction:

"a computer programming technique involving the use of a procedure, subroutine, function, or
algorithm that calls itself in a step having a termination condition so that successive
repetitions are processed up to the critical step until the condition is met at which time
the rest of each repetition is processed from the last one called to the first" - Webster

What exactly does this mean? Well in simpler terms, recursion is a function or procedure
which may call itself untill a condition is met and the function ends. All recursive
functions need a condition to be met otherwise it will keep calling itself forever. This is
called infinite recursion and will result in a stack overflow. This means that since each
time the function calls itself, memory is used to store the previous stated. Therefore if
you have infinite recursion, all the memory will be used up and the program will crash.

Recursion is a very usefull programming technique and has many applications, some of which
are not so obvious. Some of these include fractals, binary search, graph traversal(path
finding), and certain data structures such as trees.


Beginners:

The main concept of recursion is breaking down a large problem into smaller more managable
problems. To solve the smaller problems you call the function again but this time to solve
the smaller problems. You keep doing this recursively untill you reach a point where the
problem cannot be simplified any further. To illustrate this concept lets look at an
example:

Fibonacci Sequence:

A fibonacci sequence is a sequence of numbers where each successive number is the sum of the
last two numbers in the sequence. ie {0, 1, 1, 2, 3, 5, 8, 13...}

How would you go about finding the Nth number in the sequence? You can find it iteratively
(using loops) or you can find it recursively. Lets first take a look at the iterative
solution:

code:

%iterative solution to fibonacci problem fcn fibonacci1 (n : int) : int     if n <= 2 then         result n - 1     end if     var secondLastNum, lastNum, nextNum : int     secondLastNum := 0     lastNum := 1     for i : 3 .. n         nextNum := secondLastNum + lastNum         secondLastNum := lastNum         lastNum := nextNum     end for     result lastNum end fibonacci1

first we check whether n is less than or equal to 2 because we already know the first two
numbers in the sequence, 0 and 1. Next we declare some variables to store our values of the
last two numbers we know in the sequence. These are initialized to 0 and 1. secondLastNum is our second
last number and lastNum is our last number. nextNum will just be a place holder variable for when we
calculate the next number in the sequence. Now we iterate from 3 to n. We start at 3 because
we already have the first two elements. In our loop we calculate the value of the next
element and update our a abd b variables. After the loop we return our value.

Simple enough... Now lets look at the recursive solution:

code:

%recursive solution to fibonacci problem fcn fibonacci2 (n : int) : int     if n <= 2 then         result n - 1     end if     result fibonacci2 (n - 1) + fibonacci2 (n - 2) end fibonacci2

Wow! A lot less code right? You must be wondering how this could possibly work. Lets go
through it step by step. Lets for example find the 5th number in the fibonacci sequence:

1) First we call fibonacci2(5)

2) We check if n is 1 or 2 (we know the value of the first two numbers in the sequence)
Since n is greater than 2 we dont know what the answer is. So we return the sum of the
values of the two previous numbers:
result fibonacci2 (n - 1) + fibonacci2 (n - 2)

3) In our return statement, we first call fibonacci2(n-1). In this case n-1 is equal to 5-1
or 4. So we repeat step 2 and we find that we still dont know the value of the 4th number
in the sequence. So we return the sum of the previous two numbers (numbers 3 and 2). Our
first call is fibonacci2(n-1) which in this case n-1 = 3. Again we dont know what the 3rd
number is and we again sum the previous two numbers in the sequence. We sum the 2nd and 1st
numbers in the sequence.

4) We call fibonacci2(n-1) + fibonacci2(n-2). We are looking for the 2nd and 1st numbers.
We have finally reached our terminating condition. We are looking for the value of the
2nd number and we know it is 1. So we return 1. And secondly we are looking for the 1st
value which we know is 0. We return 0. So the result of fibonacci2(n-1) + fibonacci2(n-2) is
1 + 0 = 1. This is the 3rd number in the sequence. This number gets passed back to where
we were calculating the 3rd number which happened to be when we called fibonacci2(4). We
did not know the fourth value so we tried to sum the previous two numbers which happen to
be 3 and 2.

5) So now we are back finishing our calculation of the 4th fibonacci number. We called:
fibonacci2(n-1) + fibonacci2(n-2) and have found the value of fibonacci(n-1) (where n-1 =3)
and it's value is 1. So now we have:
result 1 + fibonacci2(n-2) where n-2 = 2. When we call fibonacci(2) we get the value of 1
because in the call we meet the terminating condition again.

6) So now we return our value of the 4th fibonacci number back to where we calculate the 5th
number. There we have:
result 2 + fibonacci2(n-2) where n-2 = 3. We go back to step 4 and calculate our 3rd number.

7)We finally know the two numbers in the sequence preceding the 5th number. We sum them and
finally return the value to where the function was originally called.


There! We recursively calculated the 5th fibonacci number. The explanation is sort of hard
to understand so here is a list or our function calls:

code:

1) fibonacci2(5) 2) fibonacci2(5) = fibonacci2(4) + fibonacci2(3)         3) fibonacci2(5) = (fibonacci2(3) + fibonacci2(2)) + fibonacci2(3) 4) fibonacci2(5) = ((fibonacci2(2) + fibonacci2(1)) + fibonacci2(2)) + fibonacci2(3) 5) fibonacci2(5) = (1 + fibonacci2(1)) + fibonacci2(2)) + fibonacci2(3) 6) fibonacci2(5) = (1 + 0) + fibonacci2(2)) + fibonacci2(3) 7) fibonacci2(5) = ((1 + 0) + 1) + fibonacci2(3) 8) fibonacci2(5) = ((1 + 0) + 1) + (fibonacci2(2) + fibonacci2(1)) 9) fibonacci2(5) = ((1 + 0) + 1) + (1 + fibonacci2(1)) 10) fibonacci2(5) = ((1 + 0) + 1) + (1 + 0) 11) fibonacci2(5) = 3

This is the first part to a series of recursion tutorials. I know this is a complex subject
but bare with me. The interesting stuff is yet to come


-zylum

[zylum]

Recursion Part 2:

Intermediate:

Ok so we know the basic concepts of recursion. We know that we MUST have a terminating
condition and we know how recursion behaves.

Lets look at a couple more examples where recursion can be used:


Binray Search:

Binary search is a search method to find the index of a certain element in a sorted array.
You may ask what possible applications a binary search can have? Well how would you find the
place of a certain player in a high score list? Sure you can loop through the entire list
and find the position but that is not as efficient as a binary search so if you are doing
this many times then it would be preferable to use a binary search to speed things up.

The general algorithm to a binary search is look at the middle number of the array. If it is
bigger than the number we are looking for than search the left half of that array. If it is
smaller then search the right half. If it is equal to the number you are looking for then
you have found it and can return the index where you found it.

First lets think of our terminating condition(s). We know to stop searching when we have
found the number... When else can we stop? How about when we did not find our number? When
the size of the array we are searching becomes less than or equal to zero then we can stop
searching and return -1 to indicate the number does not exist in the array.

Heres the code:

code:

fcn binarySearch (n, low, high : int, numbers : array 1 .. * of int) : int     if high < low then         result - 1     end if     var middle : int := (low + high) div 2     if numbers (middle) = n then         result middle     elsif n < numbers (middle) then         result binarySearch (n, low, middle - 1, numbers)     else         result binarySearch (n, middle + 1, high, numbers)     end if end binarySearch

The binary search function takes in four parameters. n is the number we are looking for, low
is the lower bound of the search area, high is the upper bound of the search area. numbers
is the sorted array of numbers we will search through.

The first thing we do is check whether there is still numbers to search through. If high <
low then we have no numbers to search through and can return -1. Next we look at the middle
number in our search area. If it is equal to the number we are looking for then we return
the index. That takes care of our terminating conditions.

Now we check which half of the search area we should search next and call the binarySearch
function to search it.

We quickly see why the binary search is so much more efficient than the iterative search
method. Each time we call the binarySearch() function we cut our search area in half until
we find the number. In the worse case scenerio a binary search would have to make 1+log2(N)
calls to itself where as the iterative search would have to make N iterations where N is the
size of the array to be searched.


Fractal Trees:

Problem: How would you go about drawing a tree which starts off as a single branch then
from the end of it sprout two more branches and from the ends of those sprout three branches
and so on N times? It seems like you would need an awful lot of code to get something
like that working without recursion.

So what would the terminating condition be in this case? We want to stop drawing branches
once we have reached a certain depth, N. Now how can recursion help us solve this problem?
Well once we finish drawing each branch, we could call the procedure again to draw smaller
trees from the ends of each branch. Heres the code to a very simple fractal tree program:

code:

setscreen ("graphics:400;600,nobuttonbar") proc fractalTree (startx, starty, currentDepth, endDepth : int)     var endx, endy : int     for i : 1 .. currentDepth         endx := startx + Rand.Int (-currentDepth - 1, currentDepth + 1) * 15         endy := starty + Rand.Int (1, endDepth - currentDepth + 4) * 20         Draw.ThickLine (startx, starty, endx, endy, endDepth - currentDepth + 1, 7)         delay (100)         if currentDepth < endDepth then             fractalTree (endx, endy, currentDepth + 1, endDepth)         else             drawfilloval (endx, endy, Rand.Int (1, 4), Rand.Int (1, 4), green)         end if     end for end fractalTree fractalTree (maxx div 2, 10, 1, 5)

The parameters to this function are startx and starty which are where the current branch
will sprout from. currentDepth and endDepth are self explanitory.

We start by declaring variables for our end points. Then we loop through how ever many
branches we want to create. Since we want one branch for the 1st depth and two branches for
the 2nd depth and so on, then we want currentDepth branches in general. In the loop we give
each new branch a somewhat random end point. Next we draw that branch. Then we check whether
we have reached our desired depth (this is the terminating condition). If not then we call
our procedure again making sure we update the startx, starty and currentDepth parameters.
If we reached the desired depth then we draw our leaf and the procedure is terminated after
the loop is finished. Once terminated it goes back to where it was called whether it be the
main program or inside a loop in a previous depth.

There's the basic outline for a fractal tree. Keep in mind this is a very simple fractal
tree program. For better examples check these out:

http://www.compsci.ca/v2/viewtopic.php?t=8659&highlight=fractal
http://www.compsci.ca/v2/viewtopic.php?t=4137&highlight=fractal
http://www.compsci.ca/v2/viewtopic.php?t=2038&highlight=fractal+tree


Combinations / Permutations:

Problem: List all the possible ways a string can be rearranged. This is another problem that
would be difficult to solve without recursion. The idea is simple once you have a firm grasp
on the previously discussed concepts. Given a string, loop through each of the characters in
the string and build your new strings from those letters. The first depth of recursion will
choose the first letter, the next depth the second and so on until the terminating condition
is met (no more letters to choose from).

code:

proc permutations (word, currentPerm : string)     if length (word) = 0 then         put currentPerm     else         for i : 1 .. length (word)             permutations (word (1 .. i - 1) + word (i + 1 .. *), currentPerm + word (i))         end for     end if end permutations permutations ("abcd", "")

Each time we choose a letter, we call the procedure for the next depth. The word will have
the chosen letter removed and added to the current permutation. At the next depth we find
all the permutations from the remaining letters and concatenate them to the current
permutation. I know this description is brief but should be easily understood if you have a
strong understanding of the basic concepts.



In the next section I will be exploring advanced topics such as the shortest path problems.
In the fourth and final section I will discuss optimizations you can make on certain types
of recursive problems because as you may have noticed, recursion gets really slow with
larger problems. Infact most recursive problems have an exponential run time.


That's all for now



-zylum

[MysticVegeta]

Inspiration of tut : Shortest Path in a maze thread.

[Delos]

So far it's looking pretty good, as expected of you zylum. The only thing I can point out is your choice of variable names in the fibonacci example. a, b, and c tell us nothing at all about their function. Sure it's a technicality, but remember that people will be trying to learn of this.

Good idea breaking it down into Beginner, Intermediate, and Advanced topics. Your progression is well defined. A suggestion: we haven't done this much in the past, but how about adding some 'practice problem' type things to the end of each section.

[zylum]

MysticVegeta: lol well that was the last straw, i was also helping cerventes with his solutions to his puzzle games

Delos: thanks for the input. fibonacci example 1 is fixed (better variable names). also practice problems are a great idea. its really hard to understand recursion and practice really does help.

right now im trying to think of some topics to cover in my next section. i already have the last section all planned out any suggestions for next section? right now all i have is shortest path algorithm..

[Delos]

You could always give us a little bit on recursive in-place sorts?

[Cervantes]

Excellent tutorial, zylum!
For the next one, why not go over the N-Queen's recursive solution?

[MysticVegeta]

oh i was thinking maybe an example of recursion for advanced level that includes a maze. There is an example of it in the book i am reading but i dont think i can just post the code on the net. If i can, do i have to include the book name and author?

[zylum]

Recursion Part 3:

Advanced:

N-Queens problem:

You have an N by N chessboard and wish to place N queens on this board.
The trick is non of them can attack each other. This problem is closely related to the
combinations / permutations section discussed earlier. The only difference is we want to
generate all possible ways the queens can be placed on the board. An easy way to do this
for each column, try placing a queen on each row of that column. To accomplish this, imagine
that each depth of our recursion represents one column of the board. As we go deaper into
the recursion, we move to the next column. At each level of recursion we loop trough all the
rows and place a queen there before we move on the the next depth. Before we place the queen
though, we check whether the position is a legal one to place the queen at. Once we place
a queen in the Nth depth (or Nth column) we know we have reached our solution (and
terminating condition).

code:

proc Solve (col : int)     for row : 1 .. N         if clearSpot (col, row) then             grid (col, row) := true             if col = N then                 drawGrid                 put "SOLUTION!!!"                 return             end if             Solve (col + 1)             grid (col, row) := false         end if     end for end Solve Solve(1)

Our only parameter tells us the current column we are at. the variable grid is simply a 9x9
2d array of boolean. It is initialized all to false, which means we start with an empty
board. The main loop in our program goes through each row and checks whether it is legal to
place a queen there, if so we place it, and check whether we have a solution (col = N). If
we have a solution we display the grid and end the program. Otherwise we call solve again
and increment the column. After our call to solve (after it has tried deeper combinations),
we remove the peice so that we could place it somewhere else. In your function which checks
if the positions is legal, you only need to check the horizontals and diagonals. You omit
checking the columns because you already know there is at most one peice per column.

Pathfinding / Graph traversal:

This is a very broad topic and has many modern day applications such as managing traffic,
finding effient ways to send data trough a network and applications in game making. Here I
will discuss the Depth First Search. This search technique has the characteristic of
searching as deep as possible before returning to previous depths. Its counter part is known
as the Breadth First Search which searches all possibilities at the current depth before
moving on to the next depth. We wont discuss this technique as it requires a data structure
known as the queue.

The basic algorithm is: First push all the neighbors of the starting point into the queue.
Then pop each neighbor and push its neighbors into the queue. Since a queue is FIFO (First
In First Out) then the earlier neighbors will be visited first before visiting the neighbors
of the neighbors and so on. This means this search technique will reach the extremities of
the graph last where as the Depth First Search goes to the extremities early on.

Problem: You are given a 2d array of integers. You are to travel this array starting on the
bottom left corner and moving up to the top right corner. You are to find the path which
will yeild the greatest sum. You are only permitted to move up or right.

Since you want to get the highest sum possible, you want to traverse as much of the grid as
possible so Depth First Search is a good solution to this problem. All we need to do is keep
track of a few things; our current position, our current sum and the best sum we have thus
far acheived. Since we are only allowed to move up and right, this problem is relatively
simple because we do not need to keep track of which spaces we have already travelled on
since there is no chance to go over the same spot twice.

code:

proc Solve (x, y, fx, fy, currentSum, bestSum)     if x = fx and y = fy then         if currentSum + grid (x, y) > bestSum then             bestSum := currentSum + grid (x, y)         end if         return     elsif outOfBounds (x, y, fx, fy)         return     end if     Solve (x + 1, y, fx, fy, currentSum + grid (x, y), bestSum)     Solve (x, y + 1, fx, fy, currentSum + grid (x, y), bestSum) end Solve Solve (1,1, columns, rows, 0, 0)

We start off by checking our terminating conditions and updating our sum variables. Then we
try going right, and we try going up. Fairly straight forward.

Problem: Now consider trying to find the shortest path in a maze. Using Depth First Search
we try many different paths which lead to the end and update variables depending on whether
you find a shorter path later on. Using Breadth First Search means we entirely search each
depth before moving on to the next. Therefore the first time we find a path to the end we
know it is the shortest possible path. Cleary BFS would be the correct algorithm for this
problem. Since turing does not support queues, I will show you the DFS solution which works
aswell but is slower.

As you may have noticed, this problem has many similarities to the previous one. There are
a few differences though. Since there is a chance you may cross your path, you have to keep
track of which spaces you have travelled on. Another difference is that you are allowed to
travel in four directions. Finally since you are looking for the shortest path, your
bestPath variable should start off with a very big number.

code:

proc solve (x, y, fx, fy, currentPath, bestPath : int)     if ~maze (x, y) or currentPath >= bestPath then         return     elsif x = fx and y = fy then         if bestPath > currentPath then             bestPath := currentPath         end if         return     end if     maze (x, y) := false     solve (x + 1, y, fx, fy, currentPath + 1, bestPath)     solve (x - 1, y, fx, fy, currentPath + 1, bestPath)     solve (x, y + 1, fx, fy, currentPath + 1, bestPath)     solve (x, y - 1, fx, fy, currentPath + 1, bestPath)     maze (x, y) := true     currentPath -= 1 end solve Solve (startx, starty, finishx, finishy, 0, 1000000000)

This code looks quite similar to the last code we just examined. The maze array is a 2d
array of boolean. false spaces mean there is a wall there or you have already travelled on
that particular space. true means that it is a legal space to travel to. It is a good idea
to have a one space border all the way around your maze all initialized to false so that
you dont have to worry about boundary checks; you simply wont be able to travel there.

So as in our previous example, we check our terminating conditions (we travelled on a legal
space or that we finished a path). Then we mark the spot we travelled to and move on to
each of the adjacent spaces. After checking neighbors, we mark the spot as untravelled so
that in future paths, we can travel on that space again.





That's all for this section. I hope you guys are enjoying this series on recursion! I will
be splitting the fourth and final installment into two sections which will discuss two ways
of make your recursion much more efficient. You will be surprised at how well the new
techniques will work so stay tuned



- zylum

[Cervantes]

Good stuff zylum.
In the last section, could you show the Bredth First Search version of the Maze Search?

For those people who are good visual learners, the following code may help to understand the second problem in Part 3, the one where we can only move up and right and are trying to find the path that gives us the highest score.
The core of this code is what zylum posted, though it also contains code to create a grid and code to manage the paths that we are travelling on. If you uncomment the delay in the Solve procedure, you can slow things down and get a better sense of the steps the recursion will take.

Turing:

const screenResX := 600 const screenResY := 600 View.Set ("graphics:" + intstr (screenResX) + ";" + intstr (screenResY) + ",offscreenonly") const gridX := 7            % Number of pieces the grid will be wide const gridY := 7            % Number of pieces the grid will be high const gridOffsetX1 := 100   % The grid will go from (gridOffsetX1, gridOffsetY1) to (screenResX - gridOffsetX2, screenResY - gridOffsetY2) const gridOffsetX2 := 100 const gridOffsetY1 := 100 const gridOffsetY2 := 100 const gridX2 := screenResX - gridOffsetX2 const gridY2 := screenResY - gridOffsetY2 const gridWidth := (screenResX - gridOffsetX1 - gridOffsetX2) / gridX       % Width of each grid piece, in pixels const gridHeight := (screenResY - gridOffsetY1 - gridOffsetY2) / gridY      % Height of each grid piece, in pixels const fontHeight := gridHeight div 1.75 const font := Font.New ("Arial:" + intstr (fontHeight)) var grid : array 1 .. gridX, 1 .. gridY of int for x : 1 .. gridX     for y : 1 .. gridY         grid (x, y) := Rand.Int (1, 10)     end for end for type Coord :     record         x, y : int     end record var currentPath : flexible array 1 .. 0 of Coord var bestPath : flexible array 1 .. 0 of Coord proc drawPath (path : array 1 .. * of Coord, clr : int)     for i : 1 .. upper (path) - 1         Draw.Line (round ((path (i).x - 0.5) * gridWidth + gridOffsetX1),         %x1             round ((path (i).y - 0.5) * gridHeight + gridOffsetY1),                %y1             round ((path (i + 1).x - 0.5) * gridWidth + gridOffsetX1),             %x2             round ((path (i + 1).y - 0.5) * gridHeight + gridOffsetY1),            %y2             clr)                                                                   %colour     end for end drawPath proc drawGrid     Draw.FillBox (gridOffsetX1, gridOffsetY1, gridX2, gridY2, 30)     %colour the "true" squares black     var value : string     for x : 1 .. upper (grid, 1)         for y : 1 .. upper (grid, 2)             value := intstr (grid (x, y))             Draw.Text (value, round ((x - 1) * gridWidth + gridWidth / 2 - Font.Width (value, font) / 2) + gridOffsetX1,                 round ((y - 1) * gridHeight + gridHeight / 2 - fontHeight / 2 + gridOffsetY1), font, black)         end for     end for     %draw the lines of the grid     for x : 0 .. upper (grid, 1)         Draw.Line (round (x * gridWidth + gridOffsetX1), gridOffsetY1, round (x * gridWidth + gridOffsetX1), gridY2, black)     end for     for y : 0 .. upper (grid, 2)         Draw.Line (gridOffsetX1, round (y * gridHeight + gridOffsetY1), gridX2, round (y * gridHeight + gridOffsetY1), black)     end for     % Draw paths     drawPath (currentPath, brightred)     drawPath (bestPath, brightgreen) end drawGrid fcn outOfBounds (x, y : int) : boolean     if x > gridX or y > gridY then         result true     end if     result false end outOfBounds var bestSum := 0 proc Solve (x, y, fx, fy, currentSum : int)     if x = fx and y = fy then         if currentSum + grid (x, y) > bestSum then             bestSum := currentSum + grid (x, y)             new bestPath, upper (currentPath) + 1             for i : 1 .. upper (currentPath)                 bestPath (i) := currentPath (i)         % Copies the record and everything.  Essentially copies currentPath to bestPath             end for             bestPath (upper (bestPath)).x := gridX      % Finishes the bestPath path so that it will be drawn to show that it reached the end             bestPath (upper (bestPath)).y := gridY         end if         return     elsif outOfBounds (x, y) then         return     end if     new currentPath, upper (currentPath) + 1     currentPath (upper (currentPath)).x := x     currentPath (upper (currentPath)).y := y     drawGrid     View.Update     %delay (150)     Solve (x + 1, y, fx, fy, currentSum + grid (x, y))     Solve (x, y + 1, fx, fy, currentSum + grid (x, y))     new currentPath, upper (currentPath) - 1 end Solve put "The green line represents the best path found so far." put "The red line represents the path currently being searched." Solve (1, 1, gridX, gridY, 0) put "Best Score is ", bestSum put "Elapsed time is ", Time.Elapsed / 1000, " seconds"

One last thing, in the last section of zylum's code, he uses bestPath as a parameter. He then, if certain conditions are met, assigns currentPath to bestPath. This can only be done if the keyword var is placed before bestPath in the procedure declaration, like this:

code:

proc solve (x, y, fx, fy, currentPath : int, var bestPath : int)

This also requires the initial calling of the solve procedure to pass in a variable for the last parameter, or else bestPath would fail assignment.

[zylum]

Cervantes wrote:

Good stuff zylum.
In the last section, could you show the Bredth First Search version of the Maze Search?

sure but if you dont mind ill have to do that one in java... you need a queue class. or if i feel like it i could implement my own queue class in turing.

Cervantes wrote:

One last thing, in the last section of zylum's code, he uses bestPath as a parameter. He then, if certain conditions are met, assigns currentPath to bestPath. This can only be done if the keyword var is placed before bestPath in the procedure declaration, like this:

code:

proc solve (x, y, fx, fy, currentPath : int, var bestPath : int)

This also requires the initial calling of the solve procedure to pass in a variable for the last parameter, or else bestPath would fail assignment.

Yeah, i wrote a lot of the code off the top of my head so you may need to make a few small changes like that but the algorithm overall is correct

[Cervantes]

Building a queue class shouldn't be difficult, if my idea of what a queue class is is correct. Having it in Turing would be good, since this is the Turing section, but it's better in Java then not at all!
Another possibility for the next section would be explaining how to use recursion to generate a maze.

[zylum]

heh, generating a perfect, or at least good maze is not as easy as it looks. If i get a good algorithm worked out then maybe. my current maze generator returns mazes with few forks so they are really easy

[zylum]

Recursion Part 4a:

Expert:

Breadth First Search:

A problem you may encounter with recursion is that if you aren't careful with which solution
you choose, your algorithm may end up running much longer that it should. A good example of
this was our solution to the shortest path in a maze probelm from Part 3. Since we were on
the topic of Depth First Search, we implemented that algorithm to solve the maze and it
seemed to run fine. But under certain conditions such as very large mazes or configurations
where there are many different paths (such as open spaces), the solution ends up taking a
very long time.

The proper solution would have been to use the Breadth First Search algorithm which is the
counterpart to Deapth First Search. Just to recap: DFS tries to go as deep as possible
before recursing back. BFS searches each depth entirely before moving on to the next depth.
Both algorithms have their advantages and disadvantages. If you need to search every single
path such as in the problem in Part 3 where you wanted to find the path with the highest
sum then you use DFS. If you want to find the shortest path, you use BFS because it wont
check paths that are longer then the optimal path.

BFS works with a data structure known as a queue. A queue is a data structure similar to an
array with a few differences. Since a queue is a class, it comes with a few methods. Queues
usually start empty. You can 'push' an element on to it or you can 'pop' one off. When you
push an element on to a queue, it is added to the end of the queue. When you pop an element,
you take the first element from the front of the queue. This means this data structure is
First In First Out (FIFO). You can imagine this as a queue in an amusement park. The first
customers in the line up will go on the ride first. A queues counter part is the Stack which
is FILO. You can imagine a stack as a stack of boxes. As you stack the boxes, you can only
access the top box. To access the bottom box, you must go take of all the boxes above it
first.

BFS takes in four parameters; a queue which lists all the spaces you must visit, the
coordinate of the destination and the current depth. When you initially call BFS, you pass
it a queue with a single element which holds the parameter of the starting position. For
each depth, pop each element of the queue, check if its is the destination, otherwise you
push all the neighbors of that element on to the queue. With the queue now full of the
neighboring positions, you move on to the next depth.

code:

proc BFS (queue : array 1 .. * of Coords, depth, fx, fy : int)     var neighbors : flexible array 1 .. 0 of Coords     for i : 1 .. upper (queue)         if queue (i).x = fx and queue (i).y = fy then             put "Found!!! Length = ", depth, " Time : ", Time.Elapsed / 1000             return         end if         for dx : -1 .. 1             for dy : -1 .. 1                 if abs (dx) ~= abs (dy) and maze (queue (i).x + dx, queue (i).y + dy) then                     new neighbors, upper (neighbors) + 1                     neighbors (upper (neighbors)).x := queue (i).x + dx                     neighbors (upper (neighbors)).y := queue (i).y + dy                     maze (queue (i).x + dx, queue (i).y + dy) := false                 end if             end for         end for     end for     BFS (neighbors, depth + 1, fx, fy) end BFS BFS(startQueue, 1, finishx, finishy)

In my implementation, I decided to use two flexible arrays instead of a queue. This way I
dont have to perform any push or pop operations. I just examine each element and add the
neighbors to the newQueue before passing it to the next depth.

Lets go through the code. First we create an empty 'queue' (flexible array to emulate a
queue). Then we 'pop' each element (in our case loop through each element in the array).
When we 'pop' the element, we check our terminating condition (if we reached the end). If
we didnt terminate, we check each neighbor, if we can visit we push it on to the queue
(add it to the neighbors array). After all neighbors are pushed, we pass the update queue
to the next depth (pass the neighbors array).

Note how we check the neighbors. The nested loops are used to give us different combinations
of vertical and horizontal movement. We check to see that we travel on only one axis or
moving at all by checking whether the absolut values of the directions are not equal. If
you were to be making a game and you wanted to allow for diagonal movement, then all you
would need to do is change that statement to check if both directions are not equal to zero.

If you are sceptical on the speed improvement of this algorithm, implement versions of both
BFS and DFS and run them against this small and simple maze. Also try running them in an
environment you may find in a game, ie large emtpy space with spares obsticals such as a
wall.

code:

20 20 #.#..#.#.#.#.##....B ..............#.###. .##.#####.#####.#... ##..#.....#.....#... ....#######.#######. ............#....#.. ###########.#.#..#.# ............#.#.##.# .############.#.#... .#............#.###. .##..##########.##.. ..##.#...........#.# #..#.#....#....#.#.. ...#.#.####.#..#.##. ...#.#.#.##.#..#.... .###.#.#.#..#.###### .#...#.#.#..#......# .#.###.#.##.#####.## .#.#.....#..#.#.#..# A..##.##.#..#.....##

With the above example, my BFS implimentation is about 10 times faster than my DFS algorithm.
Now that is a significant boost considering that there are few open areas (which generate
many paths). If you were to try a grid thats about 20x20 with a wall as an obstacle, you
will realize that DFS is just not an option where as BFS will execute in a few miliseconds.

So the lesson of this discussion is make sure you use the proper algorithm for the job.
Think about any possible algorithms you can use to find the solution for the problem and
think about their advantages/disadvantages. Try to minimize the amount of retacing you
algorithm does. Also, once you learn recursion, you may be eager to implement it for every
problem you have. Remember, recursion tends to run in exponential time so they are only
efficient for small sets of data. Only use recursion when you really need to.



In the next sections (two more hopefully ) we will dicuss optimizations to recursion and some alternatives.


also it would be nice for someone to make a program that gives us a nice visual of how both the BFS and DFS work.
it should show the map tiles, which tiles were already visited and the current tile being looked at.


- zylum

[Cervantes]

Ask, and ye shall receive.
I suppose the reason you didn't make a queue class was because you would have to manually set the class to work with the Coords data type. It's too bad Turing isn't more like Ruby in that regard.
Good job on this section!