Computer Science Canada

[Tutorial] Recursion
Author:  zylum [ Sat Jul 30, 2005 8:06 pm ]
Post subject:  [Tutorial] Recursion
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 Wink


-zylum
Author:  zylum [ Sat Jul 30, 2005 10:23 pm ]
Post subject: 
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
Author:  MysticVegeta [ Sun Jul 31, 2005 8:31 am ]
Post subject: 
Inspiration of tut : Shortest Path in a maze thread.
Author:  Delos [ Sun Jul 31, 2005 11:17 am ]
Post subject: 
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.
Author:  zylum [ Sun Jul 31, 2005 3:29 pm ]
Post subject: 
MysticVegeta: lol well that was the last straw, i was also helping cerventes with his solutions to his puzzle games Wink

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 Smile any suggestions for next section? right now all i have is shortest path algorithm..
Author:  Delos [ Sun Jul 31, 2005 5:00 pm ]
Post subject: 
You could always give us a little bit on recursive in-place sorts?
Author:  Cervantes [ Mon Aug 01, 2005 7:30 am ]
Post subject: 
Excellent tutorial, zylum!
For the next one, why not go over the N-Queen's recursive solution?
Author:  MysticVegeta [ Mon Aug 01, 2005 9:06 am ]
Post subject: 
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?
Author:  zylum [ Mon Aug 01, 2005 10:47 pm ]
Post subject: 
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 Wink



- zylum
Author:  Cervantes [ Tue Aug 02, 2005 11:25 am ]
Post subject: 
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.
Author:  zylum [ Tue Aug 02, 2005 1:01 pm ]
Post subject: 
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 Wink
Author:  Cervantes [ Tue Aug 02, 2005 3:27 pm ]
Post subject: 
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! Very Happy
Another possibility for the next section would be explaining how to use recursion to generate a maze.
Author:  zylum [ Tue Aug 02, 2005 8:27 pm ]
Post subject: 
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 Confused
Author:  zylum [ Wed Aug 03, 2005 2:20 am ]
Post subject: 
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 Smile) 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
Author:  Cervantes [ Thu Aug 04, 2005 6:55 am ]
Post subject: 
Ask, and ye shall receive. Smile
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! Very Happy
Author:  zylum [ Thu Aug 04, 2005 4:08 pm ]
Post subject: 
nice job cervantes! great visual. as you can plainly see, DFS is no good for this type of problem.

im working on the next section at the moment. should be up by tonight
Author:  zylum [ Sat Aug 06, 2005 1:59 am ]
Post subject: 
Recursion Part 4b:

Expert:

Introduction to Memoization:

"Memoization is a technique used to speed up computer programs by storing the results of
functions for later reuse, rather than recomputing them. Memoization is a characteristic of
dynamic programming. Memoization literally means "to put in memory" and is derived from the
Latin word memorandum, meaning what must be remembered. The word memoization is often
confused with memorization, which, although a good description of the process, is not
limited to this specific meaning.

Functions can only be memoized if they are referentially transparent -- that is, if they
will always return the same result given the same arguments. Operations which are not
referentially transparent, but whose results are not likely to change rapidly, can still be
cached with methods more complicated than memoization. In general, memoized results are not
expired or invalidated later, while caches generally are." - Wikipedia

So what the hell does all that mean? Well for our purposes, it means that we can speed up
most of our recursion by a whole lot just by storing some values so we don't need to
recompute them. I say 'most' because all recursive algorithms do not have to compute the
same value multiple times.

Remember our recursive solution the fibonacci numbers? Try findinding the 30th number. It
takes quite a while doesn't it? Why does it take so much longer than the iterative solution?

Fibonacci Numbers and Memoization:

Lets take a look at what values are calculated to find the 8th fibonacci number using a
plain recursive solution:

code:
N =                       8
                     /         \
=                7        +       6
              /     \            / \
=            6   +   5          5 + 4
            / \     / \        /\   /\
=          5 + 4   4 + 3      4+3   3+2
          /\   /\  /\  /\    /\ /\  /\
=        4+3   3+2 3+2 2+1  3+2 2+1 2+1
        /\ /\  /\  /\      /\
=      3+2 2+1 2+1 2+1    2+1 
      /\                 
=    2+1


As you can see, to calculate the 8th fibonacci number, we calculate the 3rd number 8 times!
We only really need to calculate it once and remember it. Remember, as we calculate higher
numbers, the amount of repetition increases exponentially.

So how does memoization work? Well it's simple really. First you make an array which will
store the value of calculations you may make. If you need to calculate a number, check the
array whether you have calculated it. If so, then you return that value, otherwise you
calculate that value and add it to the array.

code:
var fibNumbers : flexible array 1 .. N of int
fibNumbers (1) := 0
fibNumbers (2) := 1
for i : 3..N
fibNumbers (i) := -1

fcn fibonacci3 (n : int) : int
    if fibNumbers (n) ~= -1 then
        result fibNumbers (n)
    end if
    fibNumbers (n) := fibonacci3 (n - 1) + fibonacci3 (n - 2)
    result fibNumbers (n)
end fibonacci3

put fibonacci3(N)


The code looks very similar to our recursive solution. The only exceptions being:
1) We have an array to store calculated numbers. Since we know the first two numbers, we
initialize them. The rest are initialized to -1 to let us know that they are unknown.
2) Our terminating condition checks whether the nth number is known, rather than if
n = 1 or 2.

With that said, lets look at the calculations needed by our recursive solution with
memoization:

code:
N =           8
             / \
            7 + 6
           / \
          6 + 5
         / \
        5 + 4
       / \
      4 + 3
     / \
    3 + 2
   / \
  2 + 1


Well that drastically reduced the amount of calculations! Due to the recursive nature of the
solution, if we don't know the value of the nth number we compute it by summing the (n-1)th
and (n-2)th numbers recursively. This means that the (n-1)th number will always be computed
before the (n-2)th number will be and so on. This results with us quickly reaching the
bottom of the chain where we finally compute the 3rd number (the smallest one unknown to us).
Once we know the value of the 3rd number, when we recurse back one depth, we know all the
values to calculate the 4th number, then all the values to calculate the 5th and so on 'till
the 8th.

Using my implementations of the current fibonacci algorithms we have discussed, memoiztaion
is the fastest closely followed by iteration and then recursion. Try finding the 30th number
with your own implementations. You will realize that recusion is just too slow.

Largest Sum (Up / Right Problem) with Memoization:

Lets take a look back at one of the problems from Part 3: You have an NxN 2d array which is
filled with random positive integers. Find the path which will generate the greatest sum.
You are only allowed to travel up and right.

A very elegant solution (more so than the one presented in part 3 Confused) would be:

code:
fcn Solve1 (x, y : int) : int
    if grid (x, y) < 0 then
        result 0
    end if
    result grid (x, y) + max (Solve1 (x + 1, y), Solve1 (x, y + 1))
end Solve1


Where grid is padded with a border containing -1, the rest of the elements being random
positive integers.

Now lets look at a solution which implements memoization:

code:
fcn Solve2 (x, y : int) : int
    if memo (x, y) >= 0 then
        result memo (x, y)
    end if
    memo (x, y) := grid (x, y) + max (Solve2 (x + 1, y), Solve2 (x, y + 1))
    result memo (x, y)
end Solve2


memo is a 2d array which stores the best path from (x, y) to (N, N). Since we know that the
best path from (N, N) to (N, N) is grid(N, N), then we initialize memo(N, N) to grid (N, N).
Also, we pad the memo array with a border containing zeros. This will assure us that we will
not travel off the grid since we know that there will always be a better path than one going
into the border (all integers are positive thus a path excluding the border will result in
a higher sum).

The solution recurses through all possible paths. If one is know, we return the sum of that
path. Otherwise, we return the current position value plus the greater of the two adjacent
paths. This is a very similar process to the fibonacci problem because an unknown path
requires to fork in two directions to find the value. The only difference is this is a two
dimensional problem and requires a little bit more thought Wink.

As you can see, memoization greatly increases the speed of recursion. With N = 10, recursion
takes 1.7 seconds where as memoization takes 2 milliseconds. If you were to try N = 12,
recursion takes 25 seconds and memoization still takes 2 milliseconds. Now if you test
memoization alone (because recursion will run for an eternity) with N = 1000, it takes
about 11 seconds. THATS LESS THAN HALF THE TIME WITH N 988 TIMES LARGER!!!

The full source to both these implementations plus the source to a different implementation
(which will be discussed in the final part) is attached.

Conclusion:

Although memoization seems to be a godly programming technique, you have to be carefull when
and how you implement it. For example, it would be very hard to implement a memoization
solution to the shortest path problem. Remember that in that problem it is possible to
step on a square from four possible locations (from above, below, left and right). This
means that the best path migh go in the direction you just came from. Also, even if the best
path does not go in the path you just came from, it may overlap your path somewhere further
back. This means that for each position, you must keep track of the best path in each
direction so when you land on that position, you just add the best path of the four,
excluding the direction you came from. This only solves the problem of the best path going
towards where you just came from.. Well anyways, things get a bit complicated. Maybe not,
I am not entirely sure. Maybe all these problems are insignificant because if the path
has overlaps, it will not be the shortest path and will be discarded... That said, if
anyone decides to implement a memoization algorithm to the shortest path problem, let me
know.. For now i will stick with BFS Wink.

Something I'd like to mention is that although the solution to the Up/Right problem
presented above is more elegant, the solution presented in the third article has its own
advantages. ie it is much easier to update an array containing the best path using some
global variables. Most of my implementations thus far have followed this format because my
personal implementations had a 'bestPath' array and it made things easier. When I wrote the
article I just copied and pasted. These methods are fine for that sort of thing but
generally speaking recursive solutions should be confined to using only local variables. I
recall reading an interesting article which mentions that most if not all recursive problems
can be solved using no global variables. I would like to apolagize to the newbies to
if i have tainted you minds permanently Razz.


Anywho, the final part to this series will be coming shortly (probably tomorrow night) which
will discuss a programing technique called dynamic programing. It is closely related to
recursion and has enormous speed advantages. If you would like a sneek peek, take a look at
the attached file which has a DP solution to the UR puzzle.




- zylum
Author:  MihaiG [ Sun Aug 14, 2005 6:21 pm ]
Post subject: 
very well done..from waht i learnd i made.. a sqaring fcn

code:

fcn power (x : real, y : real) : real
    if y = 0 then
        result 1
    else
        result x * power (x, y - 1)
    end if
end power
put power (base, exponent)

any good zylum
Author:  zylum [ Sun Aug 14, 2005 9:18 pm ]
Post subject: 
yes good job!

heh, i forgot to finish this tutorial... maybe sometime soon. i still have to do part 4c and then i plan on adding practice problems to each section.
Author:  MysticVegeta [ Mon Nov 07, 2005 2:56 pm ]
Post subject: 
Wow what can I say, you the man zylum!!! Your tuts helped me a lot in the previous contests dealing with recursions/trees/permutations/grid, Thanks a lot man!!!! If you werent a mod, 50 Bits would be yours!!!! Loved your tuts, reading them over and over again because I kinda get lost, hmm treees are confusion, heh cant wait for part C!! Good job!
Author:  Aziz [ Thu Dec 01, 2005 8:16 pm ]
Post subject: 
Okay so I've gone farther with this than anything else. Now, how can I use this to get my Pacman ghosts to move toward Pacman? So I can find the shortest path to Pacman, now how do I get the ghost to follow this path? I'm thinking something along the lines of storing the directions in a string. This is what I've gotten so far (btw im using rows and columns instead of x and y)

code:
%Bredth First Search
proc BFS (queue : array 1 .. * of coord, fr, fc : int)
    var neighbours : flexible array 1 .. 0 of coord
    for i : 1 .. upper (queue)
        if queue (i).r = fr and queue (i).c = fc then
            %Done
            return
        end if
        for dr : -1 .. 1 by 2
            for dc : -1 .. 1 by 2
                if abs (dr) ~= abs (dc) then
                    var neighbourR := queue (i).r + dr
                    var neighbourC := queue (i).c + dc
                    if grid (neighbourR, neighbourC) >= EMPTY then %or grid (neighbourR, neighbourC) = "B" then
                        new neighbours, upper (neighbours) + 1
                        neighbours (upper (neighbours)).r := neighbourR
                        neighbours (upper (neighbours)).c := neighbourC
                        grid (neighbourR, neighbourC) := -1
                    end if
                end if
            end for
        end for
    end for

    BFS (neighbours, fr, fc)
end BFS


I'm just not sure where/how to add the correct values to the string. Thanks Very Happy
Author:  zylum [ Thu Dec 01, 2005 11:32 pm ]
Post subject: 
check turing source code.. i think i have a BFS class posted there that returns the path as an array...
Author:  A.J [ Thu Mar 13, 2008 1:46 pm ]
Post subject:  Re: [Tutorial] Recursion
i know this thread is couple of years old, but i was wondering if zylum could post one on A*.....
I don't mind helping you.......

A.J

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy