순환

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

 

ex) 팩토리얼

- n!을 정의하는 데 (n-1)!이 사용

- (n-1)!을 정의하기 위해 다시 (n-2)!가 필요

int factorial(int n){
	if(n<=1) return(1);
    else return(n*factorial(n-1));
}

- C언어로 팩토리얼 계산 구현

---

순환 호출의 내부적인 구현

- 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일

- 복귀 주소가 시스템 스택에 저장되고, 호출되는 함수를 위한 매개변수와 지역 변수를 할당받음

→ 자기 자신의 시작 위치로 점프

 

순환 알고리즘의 구조

- 자기 자신을 호출하는 부분과 순환 호출을 멈추는 부분으로 구성

- 멈추는 부분이 없다면 스택을 모두 소모할 때까지 순환 호출을 반복하다 오류 발생

if(n<=1) return 1;	//순환을 멈추는 부분
else return n*factorial(n-1);	//순환 호출 부분

 

순환 vs 반복

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

반복(iteration)	순환(recursion)
- for(반복 제어 변수 사용)이나 while(조건을 충족할 때까지 반복) 등의 반복 구조로 되풀이 - 반복을 사용하면 복잡해지는 경우 존재	- 자기 자신을 다시 호출하여 작업을 수행 - 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합 - 함수 호출을 요하므로 많은 경우 반복에 비해 수행속도 저하 - 호출이 발생할 때마다 호출하는 함수의 상태를 기억해야 하므로 여분의 기억 공간 필요

- 반복과 순환은 기본적으로 문제 해결 능력이 동일

- 많은 경우 순환 알고리즘을 반복 알고리즘으로, 반복 알고리즘을 순환 알고리즘으로 구현 가능

- 순환 알고리즘은 수행 시간과 기억 공간 사용의 측면에서 비효율적인 경우가 많음

 

※ 반복으로 바꾸기 어려운 순환

ex)

① return n*factorial(n-1);

② return factorial(n-1)*n;

 

- 꼬리 순환(tail recursion): ①처럼 순환 호출이 순환 함수의 가장 마지막에 이루어지는 형태

- 머리 순환(head recursion): ②처럼 ~

- 머리 순환 또는 여러 군데에서 자기 자신을 호출하는 경우(multi recursion) 반복으로 변환이 어려움