We can do this by calling an a PicoLisp function that decreases N, and store the return value in the variable (be move ( (dec again, we 'move' the last remaining plate from one pole from to by printing a line. (be move ( will implement exactly the same steps: First we need to call the move predicate with N-1 plates.

Here we do care for the pole variables, so let's call them and analogous to the functional implementation. We don't care for the pole variables, so lets just replace them by the anonymous variable (be move ( 0 T) We can just stop the recursion here using the cut-operator T. The first thing we need again is the base case for N=0, where we can just stop the recursion. But for (hanoi 5), we already have 31 movements of plates (2^5 -1)!įrom our Pilog course we know that logical languages are very well suited to solve recursive tasks.

The case (hanoi 1) is trivial: The recursive loops are never entered, and the plate is just moved like this.

Move disk 1 from the left to the center pole Let's write everything to a file called hanoi-functional.l and run it in debug mode, so that we can interact with it in the REPL: $ pil hanoi-functional.l + Now that we defined the algorithm, let's define also the starting point for our function, assuming that we have three poles: (de hanoi (N) These steps are repeated for all sub-towers of each tower until the task is finished. (println 'Move 'disk N 'from 'the A 'to 'the B 'pole) Now we do the same thing again, only switching B and C: (de move (N A B C) Now we have exactly plate on A and (N-1) plates on B. In the last step, we move the whole remaining tower to C via A. Because we are not really moving anything physically (not even data), let's just add a line for our mental node: (println 'Move 'disk 'from 'the A 'to 'the B 'pole) Now we only need to move one plate from A to B. We express it in PicoLisp by 'moving' N-1 plates from A to B via C. Then we model the overall procedure as recursion of small, repetitive tasks:įirst we move the tower on pole A to pole B, except for the lowest, largest plate. In our case, the base case is that the number of plates need to be larger than 0, otherwise we cannot move anything: (de move (N A B C) First of all, a recursive function always needs an exit condition: the base case. The main idea of recursion is that a large problem can be split up into repetition of smaller problems that are easier to solve. Let's define a function move which has four parameters: We will discuss a recursive functional and logical algorithm. No disk may be placed on top of a disk that is smaller than it.įor example, this is how a solution for four disks may look like:.Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.These are the 'immutable rules of Brahma': According to the legend, when the last move of the puzzle is completed, the world will end. Acting out the command of an ancient prophecy, Brahmin priests have been moving these disks in accordance with the immutable rules of Brahma since that time. Once there was an Indian temple in Kashi Vishwanath containing a large room with three time-worn posts in it, surrounded by 64 golden disks. This is the story (or one of many versions): The 'Towers of Hanoi' riddle was introduced to the West by the French mathematician Edouard Lucas in 1883. We will show two ways to solve this, one using functional programming purely in PicoLisp, and one using logical programming with help of Pilog. Today we will talk about a very famous recursive algorithm: The Towers of Hanoi riddle.

Hanoi towers golang