[자료구조] chap2. 순환

2.1 순환의 소개

-순환: 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제 해결하는 프로그래밍기법

 

ex. 피보나치 수열

 

 

 

 

 

 

 

 

-순환 알고리즘: 자기 자신을 순환적으로 호출하는 부분+ 순환 호출을 멈추는 부분

-순환 호출이 끝에서 이루어지는 꼬리순환은 반복알고리즘으로 쉽게 바꿔 쓸 수 있다.

[순환 vs 반복]

ㄴ순환: 알고리즘 명확 간결,  반복에 비해 수행속도 느림, 여분의 기억공간 더 필요. 함수 호출 위해서 함수 매개변수들을 스택에 저장하는 사전작업 필요

ㄴ반복: 지나치게 복잡해질수도 있음

 

-순환의 분할정복: 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결

-성능: O(n)

 

2.2 거듭제곱값 계산

-팩토리얼에서는 반복이 순환보다 빠름

-거듭제곱에서는 순환이 반복보다 빠름

 

 

 

 

 

 

 

 

2.3 피보나치 수열의 계산

 

 

 

 

 

 

 

 

-시간복잡도: O(2^n)

 

 

2.4 하노이의 탑 문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-반복적인 형태로 바꾸기 어려운 순환: 꼬리순환. 

 

-꼬리순환

-머리순환 ex. 하노이의 탑