[자료구조] 순환적, 반복적 피보나치 수열 구현 및 성능 비교, 순환문과 반복문 비교, 하노이탑

■ 구현

■ Main

■ 성능 비교

 

이로 인하여 피보나치 수열은 Iterative 기법이 더욱 효과적인 것을 알 수 있었다.

 

■ 순환 (Recursive) vs 반복 (Iterative)

순환 (Recursive)	반복 (Iterative)
[장점] 가독성 증대 및 코딩도 간단해짐 [단점] 함수 호출의 오버헤드 발생으로 수행속도가 느림 (스택 저장 공간에 함수 파라미터 스택을 저장할 기억 공간이 더필요하고 이와 관련된 작업을 함에 있어서 오버헤드가 발생함)   [특징] 1. 어떤 경우는 순환이 아니면 프로그램 구현이 어려운 경우가 있음 2. 시간 복잡도 (Time Complexity)는 순환 호출 1번에 1번의 곱셈을 수행하므로 n번 발생시 O(n)이다.	[장점] 수행속도가 빠름 [단점] 가독성을 악화시킬 수 있음 [특징] 1. 순환적 문제에는 프로그램이 아주 어려운 경우도 있음 2. 시간 복잡도는 for를 n번 반복할 시 O(n)이다.

 

■ 하노이탑 (The Tower of Hanoi)

 

하노이탑 문제는 순환 호출이 가장 잘 적용이 된 문제이다.

 

아래와 같이 왼쪽 막대에 있는 원판 n개를 가장 오른쪽 끝에 위치한 막대로 옮기는 것

(출처: 나무위키)