02.순환-(1)

순환의 소개

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

 

순환 호출의 내부적인 구현

-프로그램 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일.

 즉,복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역변수를 스택으로부터 할당 받음. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드(activation record)라 함.

-순환 호출이 계속 중첩될수록 시스템 스택에는 활성 레코드들이 쌓이게 됨.

 

순환 알고리즘의 구조

-순환 알고리즘은 자기 자신을 순환적으로 호출하는 부분과 순환 호출을 멈추는 부분으로 구성

 

순환 ⇔ 반복

-프로그래밍 언어에서 되풀이하는 방법에는 반복(iteration)과 순환(recursion)이 있음.

-반복: for나 while등의 반복 구조를 사용하여 반복시키는 문장을 작성하는것.

-순환: 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식.

 

-순환 호출이 끝에서 이루어지는 순환을 꼬리 순환(tail recursion)이라 함.

-순환은 일반적으로 함수 호출을 하게 되므로 반복에 비해 수행속도 면에서는 떨어짐.

 

-순환은 문제의 정의가 순환적으로 되어 있는 경우에 유리한 방법

 ->팩토리얼 함수 계산, 피보나치 수열, 이항 계수 계산, 각종 이진 트리 알고리즘, 이즘탐색, 하노이탑 문제 등

 

순환 알고리즘의 성능

-알고리즘과 순환알고리즘이 시간 복잡도는 같지만 순환 호출의 경우 여분의 기억 공간이 더 필요하고, 또한 함수를 호출하기 위해서는 함수의 파라미터들을 스택에 저장하는 것과 같은 사전 작업이 상당히 필요.

순환 호출 시에는 호출이 일어날 떄마다 호출하는 함수의 상태가 기억되어야 하므로 여분의 기억장소가 필요.