![]() ![]() In addition, we need to make use of B which we call the auxiliary stack.Īn important thing to notice is that the source, destination and auxiliary stacks keep on changing. When solving the problem of moving disc n from A to C, we call A the source and C the destination. ![]() However, we want to talk about these stacks in terms of source, destination and auxiliary stacks. Now, we have three stacks labeled A, B and C. By the principle of recursion, we have already solved these subproblems. How do we solve these subproblems? We don't have to. Move all the discs smaller than disc n from B to C.Move all the discs smaller than disc n from A to B.Our problem of moving all the discs from A to C has now been divided into two subproblems: Finally, we move the remaining discs from B to C. First, we move all the discs above disc n from A to B. We can solve our problem in three simple steps. Now, the only way we can move disc n from A to C is by first moving all the discs above it from A to B. Without this invariant, the solution would be trivial. Our job is to move all the discs from stack A to stack C while maintaining the invariant that a bigger disc may never be placed on top of a smaller disc. Given n discs, the smallest disc is labeled 1 and the largest disc is labeled n. I won't give you the solution outright, but I'll explain the intuition behind the solution. Tower of Hanoi is an inherently recursive problem and it has an elegant recursive solution. The code for Hanoi is my attempt to turn my project from C++ into Scheme.Īny help is appreciated. My problem with that, is I'm so used to imperative and OOP with the use of variables that I'm not sure how I can do this when Hanoi only takes one parameter. I'm getting an infinite loop since every time it gets used it takes the same value, thus not ever reducing the value. SumSublists returns how many disks there are in the game. (hanoi '((cddr towersNum) (cadr towersNum) (car towersNum))) (hanoi '((car towersNum) (cadr towersNum) (cddr towersNum))) (hanoi '((car towersNum) (cddr towersNum) (cadr towersNum))) (+ (length (car lst)) (sumSublists (cdr lst))) Here's an example of what I've got on my latest attempt. My professor said they were able to do it with about 6 helper functions.Īs mentioned, I have to solve the problem taking taking the list as the only parameter. Every solution I come up with doesn't do it recursively, seeing as I can't manage to wrap my head around doing it recursively with the list as the only parameter. I've been ruminating on this for about a week now. It prints all the valid moves of the disks.I'd like to start off by saying this is homework so I'm not asking for a solution, just some tips. a disc can only be moved if it is the uppermost disc on a stack.Ī larger disc may not be stacked on top of a smaller disc. To complete the puzzle, put the discs in the same order in the final rod via the middle rod.Īt any given time, only one disc can be transferred.Įach move requires taking the uppermost disc from one of the stacks and placing it on top of another, i.e. In the first rod, the discs are positioned so that the largest disc is at the bottom and the smallest is at the top. It is a mathematical puzzle game in which three identical rods and n discs of varying sizes are used. The answer to the primary problem is represented in terms of lesser problems until the smallest problem meets the base case in a recursive function. Recursive Case: In the recursive case, the function calls itself till it reaches the base case. Recursion is most useful for activities that can be broken down into smaller subtasks.Ī recursive function is made up of two major components:īase Case: The base case is where all further calls to the same function end, implying that no additional recursive calls are made. When loops are built or interpreted, they are generally transformed into recursive functions. In general, recursive code is shorter and easier to write than iterative code. The technique of explaining an action in terms of itself is known as recursion. This type of function is known as a recursive function. When a function calls itself repeatedly until it meets a stated stopping condition, this is referred to as recursion. The Oxford English Dictionary defines recursion as the repeated use of a recursive technique or term. Get hold of all the important Java fundamentals with the Simple java program example guide and practice well. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |