----------------------------------- zylum Sat Jul 30, 2005 8:06 pm [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: %iterative solution to fibonacci problem fcn fibonacci1 (n : int) : int if n 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: 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 Tue Aug 02, 2005 1:01 pm ----------------------------------- 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. 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: 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 Tue Aug 02, 2005 3:27 pm ----------------------------------- 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! :D Another possibility for the next section would be explaining how to use recursion to generate a maze. ----------------------------------- zylum Tue Aug 02, 2005 8:27 pm ----------------------------------- 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 Wed Aug 03, 2005 2:20 am ----------------------------------- 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. 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. 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 Thu Aug 04, 2005 6:55 am ----------------------------------- 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! :D ----------------------------------- zylum Thu Aug 04, 2005 4:08 pm ----------------------------------- 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 Sat Aug 06, 2005 1:59 am ----------------------------------- 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: 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. 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: 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: 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: 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 :P. 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 ----------------------------------- MihaiG Sun Aug 14, 2005 6:21 pm ----------------------------------- very well done..from waht i learnd i made.. a sqaring fcn 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 Sun Aug 14, 2005 9:18 pm ----------------------------------- 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 Mon Nov 07, 2005 2:56 pm ----------------------------------- 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 Thu Dec 01, 2005 8:16 pm ----------------------------------- 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) %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 :D ----------------------------------- zylum Thu Dec 01, 2005 11:32 pm ----------------------------------- check turing source code.. i think i have a BFS class posted there that returns the path as an array... ----------------------------------- A.J Thu Mar 13, 2008 1:46 pm 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