구구

피보나치 수열은 수학적으로 a₁＝1, a₂＝1, aₙ＝aₙ₋₁+aₙ₋₂(n≧3) 정의되는 수열이다 즉, 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 1, 1, 2, 3, 5, 8, 13 ... 인 수열인 것이다. 반복문으로도 충분히 구현이 가능하다. 입력된 숫자만큼 반복문을 반복하고 첫째 항과 둘째 항을 더한 값을 반복적으로 합산하여 출력한다. 이를 재귀함수로 구현하고자 한다. 입력한 특정 숫자 이하까지 피보나치수열이 출력되도록 구현한다.

하노이의 탑은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다. 즉 왼쪽의 원판들을 전부 오른쪽 기둥으로 순서 그대로 옮기는 것이다. 원판의 숫자가 얼마나 커져도 상관없이 하나의 알고리즘으로 해결이 가능하다. 간단한 파이썬으로 구현할 수 있다. 그전에 재귀함수의 원리에 대해서 알아보자. 재귀함수는 함수를 정의함에 있어 본인 스스로를 재참조하여 정의하는 함수이다. 예를 들어 숫자를 세는 함수로 순서를 따라가면 5 -> 4 -> 3 -> 2 -> 1 -..