Understanding Recursion in Power Query: Tower Of Hanoi

This post introduces a fun puzzle that perfectly illustrates the concept of recursion. If you’ve ever looked into a mirror holding another mirror behind you, you’ve witnessed a visual form of recursion: a reflection within a reflection, going on seemingly forever.

In the programming world, recursion is a technique where a function calls itself to solve smaller instances of the same problem. In this article, we’ll be looking at the concept of recursion using the @ sign.

Tower of Hanoi: A Puzzle That Screams Recursion

The Tower of Hanoi is a classic puzzle game that perfectly illustrates the power of recursion. Invented in 1883, the puzzle consists of three pillars and a number of disks with different diameters. Your mission is to move all the disks from one pillar to another, following these rules:

1. You can only move one disk at a time.
2. Only the top disk from any pillar can be moved.
3. No disk may be placed on top of a smaller disk.

Sounds simple, but it can get quite tricky as the number of disks increases. Here’s a visual representation of how a pillar with 3 disks can move from the first pillar to the last pillar.

The first step is to move the smallest disk to the third pillar. Then a medium-sized disk needs to move from the first pillar to the second pillar, etc.

So, how does recursion come to the rescue? Recursion helps you break down the big problem—moving all disks from one pillar to another—into smaller, manageable sub-steps.

The M-Code to Solve the Tower of Hanoi

Here’s how you can solve the Tower of Hanoi puzzle using a function in the M language:

let
  TowerOfHanoi = 
    ( n as number, fromPillar as text, helpPillar as text, targetPillar as text ) 
=>
let
  MoveDisk   = ( fromPillar, targetPillar ) =>
    Text.From ( fromPillar ) & " -> " & Text.From ( targetPillar ), 
  SolveHanoi = 
    if n = 1 then
      { MoveDisk ( fromPillar, targetPillar ) }
    else
      List.Combine (
        {
          @TowerOfHanoi ( n - 1, fromPillar, targetPillar, helpPillar ), 
          { MoveDisk ( fromPillar, targetPillar ) }, 
          @TowerOfHanoi ( n - 1, helpPillar, fromPillar, targetPillar )
        }
      )
in
  SolveHanoi
in
  TowerOfHanoi ( 3, "a", "b", "c" )

The function expects 4 parameters as input:

• n: number of disks
• fromPillar: the description of the first pillar.
• helpPillar: the description of the second pillar.
• targetPillar: the description of the third pillar.

Now, let’s understand how this function works.

• Start the Function: We start by calling TowerOfHanoi(3, "A", "B", "C"). We want to move three disks from pillar “A” to pillar”C”, using pillar”B” as a helper pillar.
• First Recursive Call: The function notices that the number of disks is more than 1, so it must break down the problem. It calls itself to move 2 disks from “A” to “B”, treating “C” as a helper (TowerOfHanoi(2, "A", "C", "B")).
• Breaking It Down: Before it can move two disks from “A” to “B”, it needs to clear the path by moving one disk from “A” to “C”. Another self-call (TowerOfHanoi(1, "A", "B", "C")).
• The Base Case: With only one disk, the function executes a direct move from “A” to “C”, resulting in “A -> C”. This is the most straightforward case.
• Unfolding the Recursion: Now that one disk is out of the way, the function moves back up the recursion chain, shifting the remaining disks accordingly.
• Final Moves: Ultimately, all recursive calls are resolved, and you get a list of moves.

What we’re after is an output that shows something like:

Tower of Hanoi Sequence
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

How does this really work?

The MoveDisk variable contains a function that transforms the fromPillar and targetPillar into text and creates a direction.

MoveDisk = 
  (fromPillar, targetPillar) => Text.From(fromPillar) & " -> " & Text.From(targetPillar),

This simply transforms our input values into text and combines them with an arrow in between. For example: “1 -> 3”.

Then comes the magic function:

SolveHanoi = 
            if n = 1 then 
                {MoveDisk(fromPillar, targetPillar)}
            else 
                List.Combine(
                    {
                        @TowerOfHanoi(n - 1, fromPillar, targetPillar, helpPillar),
                        {MoveDisk(fromPillar, targetPillar)},
                        @TowerOfHanoi(n - 1, helpPillar, fromPillar, targetPillar)
                    }
                )

If there’s only one disk (n = 1), the function performs a single move. Otherwise, it strategically divides the problem into smaller parts, reusing itself to solve these smaller problems.

List.Combine(
  {
    @TowerOfHanoi(n - 1, fromPillar, targetPillar, helpPillar),
    { MoveDisk(fromPillar, targetPillar ) },
    @TowerOfHanoi(n - 1, helpPillar, fromPillar, targetPillar)
  }
)

As step 1, it then does the following:

• @TowerOfHanoi(3-1, "A", "C", "B") is called to move two disks from A to B, using C as a helper.
• Inside this, @TowerOfHanoi(2-1, "A", "B", "C") is called.
• Since n = 1 now, it leads to the move of the first disk from A to C.

List.Combine(
  {
    @TowerOfHanoi( 3 - 1, "a", "c", "b" ),
    { MoveDisk( "a", "b" ) },                 // this statement returns the output of the first step
    @TowerOfHanoi(2 - 1, "a", "b", "c" )     
  }
)

As step 2:

• @TowerOfHanoi( 2, “A”, “C”, “B” ) continues.
• MoveDisk("A", "B") is called directly.
• Again, the if n = 1 clause is activated.

We’ve now looked at steps 1 and 2. Each of these steps triggers the condition of the if n = 1 clause, which triggers a single move. Every other part of the code is about setting up these moves in the correct order.

The recursive function continues this cycle until it has elegantly solved the puzzle. By understanding the logic of this classic game, you can grasp the fundamentals of recursion—a technique that is not just confined to games but widely used in programming to solve complex problems.

This was a tough challenge. In case you want to achieve recursion using other functions, you can check out the article on List.Generate or with a similar approach, you can check out how to use @ operator for recursion.