Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
[Tutorial] Recursion
Author Message
zylum

Posted: Thu Aug 04, 2005 4:08 pm   Post subject: (No 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

zylum

Posted: Sat Aug 06, 2005 1:59 am   Post subject: (No 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 ) 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 .

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 .

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 .

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

UR Solver.t
Description:
Filename:  UR Solver.t
Filesize:  1.93 KB

MihaiG

Posted: Sun Aug 14, 2005 6:21 pm   Post subject: (No 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
zylum

Posted: Sun Aug 14, 2005 9:18 pm   Post subject: (No 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.
MysticVegeta

Posted: Mon Nov 07, 2005 2:56 pm   Post subject: (No 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!
Aziz

Posted: Thu Dec 01, 2005 8:16 pm   Post subject: (No 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
zylum

Posted: Thu Dec 01, 2005 11:32 pm   Post subject: (No subject)

check turing source code.. i think i have a BFS class posted there that returns the path as an array...
A.J

Posted: 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