[프로그래머스/Python] 하노이의 탑

https://school.programmers.co.kr/learn/courses/30/lessons/12946

아주 오래전에 프로그램을 처음 배울 때 recursion을 배우는 예제였다. 처음 보는 문제라면 아래와 같은 알고리즘을 생각하는게 쉽지는 않다.
작은 예제 n = 1, n=2 부터 작동하는 프로그램을 만들어보고 n이 커졌을 대 작동해야할 프로그램의 아이디어를 찾아가면 좋다.

def solution(n):
    answer = []
    def recursion(n,fr,to,spare):
        if n == 1:
            answer.append([fr,to])
            return
        else:
            recursion(n-1,fr,spare,to)
            recursion(1,fr,to,spare)
            recursion(n-1,spare,to,fr)
    recursion(n,1,3,2)
    return answer