Space complexity of recursive Towers of Hanoi with memoization?

Question

What is the space-complexity of recursive Towers of Hanoi with memoization?

I guess the recursive algorithm has 2^(n-1) recursive calls, so the space-complexity is 2^(n-1)?

Edit after reading some comments below: I think there is no repetitive recursive calls here so memoization is not helpful at all. If I use memoization, all the recursive calls will be stored and hence raise the space-complexity to the maximum: 2^(n-1). Is it better not to use memoization for this recursive algorithm?

Can you confirm my justification?

Towers of Hanoi problem: list moves to move n disks from "source" peg to "target" peg using "mid" peg.

Recursive algorithm:

def hanoi_tower_solution(n, source, mid, target):
    if n == 1:
        disk_move(source, target)
    else:
        hanoi_tower_solution(n-1, source, target, mid)
        disk_move(source, target)
        hanoi_tower_solution(n-1, mid, source, target)

Answer 1

I guess the recursive algorithm has 2^𝑛−1 recursive calls, so the space-complexity is 2^𝑛−1?

No. Although there are that many calls, there are calls returning before the next recursive call is made, and so the (stack) memory used by the previous call is first freed and then reused again.

What counts is the deepest depth of recursion. Since 𝑛−1 is passed as argument, and with 𝑛 equal to 1 the deepest point of recursion is reached, the depth is 𝑛. Therefor the space complexity is O(𝑛).

If I use memoization, all the recursive calls will be stored and hence raise the space-complexity to the maximum: 2^𝑛−1.

True.

Is it better not to use memoization for this recursive algorithm?

That depends on what exactly is memoized. If the simple state of the towers is used as key, then it is useless, as no state occurs twice in a solution.

We could imagine a kind of memoization where the order of the towers is not represented in the key, and only the number of sequential, smallest discs on one stack is used as key -- with the idea that this substack must get moved to another location. The moves for moving the 3 smallest discs from tower B to C could then make use of a memoized solution for moving them from tower A to B. You would then take care of how the moves are encoded, so they translate correctly to the actual situation of the towers. This would then require about O(𝑛) entries for memoization, but each entry would list the moves to be made, which is again exponential in terms of the number of discs to move...

There really is not much gain with memoization, as:

1. Anyhow all the 2^𝑛−1 moves must be made, so there is no time gain.
2. There is a straightforward solution that does not require recursion: the number of discs, the current state and move number uniquely define which move must be played. That logic is explained on Wikipedia. And then it runs with constant auxiliary space complexity (so not counting the memory used for representing the current state).