1. 재귀(순환)

Reference:
C언어로 쉽게 풀어쓴 자료구조 / 생능출판사 / 천인국

1. 순환의 소개

- 순환(recusrion)

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

 

 

순환의 예

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

 

 

순환적인 팩토리얼 계산 프로그램

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

 

factorial(3)이 작동하는 방식

 

 

factorial(3)의 순서

---

- 순환 호출의 내부적인 구현

만약 위와 같이 프로그램을 작성하였을 경우, 컴퓨터 안에서는 어떤 일이 일어날까?

 

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

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

 

*호출된 함수가 자기 자신이라면 자기 자신의 시작 위치로 점프하게 되는 것이다

 

 

main()에서 factorial()이 호출됬을 때의 시스템 스택이 변화

==> 순환호출이 계속 중첩될수록 시스템 스택에는 활성 레코드들이 쌓인다 => 수행 속도 up

---

- 순환 알고리즘의 구조

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

=> 만약 순환을 멈추는 부분이 없다면 시스템 스택을 다 사용할 때까지 순환적으로 호출되다가 결국 오류를 내면서 멈출 것이다

---

- 순환 <-> 반복

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

반복

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

==> 간명하고 효율적이지만 반복을 사용할 때 지나치게 복잡해지는 문제들도 있는데 그럴 때 순환을 사용한다

 

순환

: 자기 자신을 다시 호출하여 작업을 수행하는 방식

 

장점 : 반복에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있음 (알고리즘으로 나타낼 때는 순환) 

단점 : 반복에 비해 수행속도가 오래 걸림 (실제 코딩은 반복)

 

*반복과 순환은 문제 해결 능력이 같으며 서로 바꾸어 쓸 수 있다*

 

 

앞의 프로그램을 반복 기법으로 구현

int factorial(int n)
{
	int i, result = 1;
	for (i = 1; i < n; i++)
	{
		result = result * i;
	}
	return (result);
}

---

- 순환의 원리

순환은 문제를 일부 해결한 다음, 나머지 문제에 대하여 순환호출을 한다

 

분할정복(divicde and conquer)

: 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법

 

==> 순환은 분할정복방법을 사용하고 이는 문제의 크기를 점점 작아지게 해서 아주 쉽게 만든다

 

 

순환은 알고리즘의 정의가 순환적으로 되어 있는 경우에 유리하다

ex)

• 팩토리얼 함수 계산
• 피보나치 수열
• 이항계수 계산
• 이진 트리 알고리즘
• 이진 탐색
• 히노이 탑 문제들

---

- 순환 알고리즘의 성능

반복 알고리즘

시간 복잡도 : O(n)

==> for을 이용하여 n번 반복하므로

 

순환 알고리즘

시간 복잡도 : O(n)

==> 곱셈이 몇 번이나 반복되는지 세어본다

==> 한번 순환 호출될 때마다 1번의 곱셈이 수행되고 순환 호출이 n번 일어나므로 n번의 곱셈 : O(n)

 

시간복잡도는 같지만 순환 호출의 경우 기억공간이 더 필요, 스택에 저장하는 등 작업이 많이 필요

=> 수행시간 up => 유도리있게 사용하기