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)

CodePudding user response：

I guess the recursive algorithm has 2