2.1 순환

순환(recursion)

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

 

ex)

int factorial(int n)

{

 if(n <= 1 ) return(1);

 else return (n * factorial(n-1) )

}

 

-> factorial(3) = 3 * factorial(2)

                    = 3 * 2 * factorial(1)

                    = 3 * 2 * 1

                    = 6

 

순환 호출의 내부적인 구현

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

 

순환 알고리즘의 구조

- 자기 자신을 순환적으로 호출하는 부분

- 순환 호출을 멈추는 부분으로 구성

 

순환 <-> 반복

반복: for or while 등의 반복구조로 되풀이 하는 방법이다.

순환: 본질적으로 순환적(recursive)인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다.

 

- 반복과 순환은 서로 바꾸어 쓸 수 있다.

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