재귀 구현에서 Recursion과 Iteration의 차이점

우리가 정말 많이 사용하는 재귀함수

처음에는 개념과 구현이 조금 헷갈리지만, 시간이 지나면 이만큼 편한게 없다

하지만 재귀함수를 구현할 때에는 몇 가지 주의할 점들이 있고, 이를 지키지 않으면 수많은 오류가 발생할 수 있다

출처: https://shoark7.github.io/assets/img/algorithm/fibonacci-logo.png

재귀: 특정 개념 or 함수를 정의할 때 자기 자신을 이용하는 방법

ex) 내 연봉은 1년에 천만원씩 증가하고, 입사 첫 연봉은 1억원이었다. 

이 경우 현재 나의 연봉은 (작년 연봉 + 천만원)이며, 입사 몇년차인지에 따라 연봉 금액이 달라진다. 현재 연봉을 정의하는 데에 작년 연봉을 이용하는 이러한 예시가 재귀라고 할 수 있다.

재귀를 처음 학습할 때 참고하는 대표적인 예시 두 가지가 있다

그것은 바로 Factorial과 Fibonacci

1️⃣ Factorial: 어떤 자연수 n에 대해 n! = n * (n-1) * (n-2) * ... * 2 * 1 (if n is 0, 0! is 1)

팩토리얼은 정규 교육과정을 수료한 사람이라면 전부 아는 수학적 개념이다

위와 같은 정의를 통해, 5! = 5*4*3*2*1 = 120임을 알 수 있다. 우리는 이 때, 5와 나머지 부분을 따로 묶음으로써 5! = 5* 4!임을 알 수 있다.

결국 n! = n * (n-1)!이 되는 것이다

2️⃣ Fibonacci: 0을 포함한 자연수 n에 대해, 피보나치 숫자 Fn = Fn-1 + Fn-2 (F0 = 0, F1 = 1)

F0과 F1이 상수로 정해져 있기 때문에, 피보나치 숫자는 다음과 같다.

0, 1, 1(0+1), 2(1+1), 3(1+2), 5(2+3), 8, 13, 21, 34, 55, 89, ...

피보나치는 정의 자체가 재귀적 정의를 따르기 때문에 이해하기에는 어렵지 않다.

 

우리는 이제 위의 두 가지 재귀를 Recursion과 Iteration을 이용해서 구현해 볼 것이다.

 

Recursion: 재귀의 정의에 부합하게 함수 f(x)를 정의한다(매개변수는 하나 이상일 수 있다). 이 때, 함수의 형태는 반드시 Base case + Induction step의 형태를 띄어야 한다.

Base case: 재귀함수의 최소 혹은 최대 bound에 해당하는 변수의 값을 직접 명시해주는 부분

Induction step: f(x)를 f(x') (이 때, x'는 base case에 더 가까워지도록 증가/감소 해야한다)을 이용하여 재귀적으로 정의(단순한 문제로 변환하는 과정)

recursion 코드를 이용하면 2번 값에서 반환된 값에 대한 추가 연산 후 함수 값을 리턴하게 된다.

int factorial(int n) {
	if (n == 1 || n == 0)return 1;	//base case
	return n * factorial(n - 1);	//induction step
}

int factorial2(int n) {
	return n * factorial2(n - 1);	//X 무한 roop에 빠진다
}

int factorial3(int n) {
	if (n == 1 || n == 0)return 1;	
	return n * factorial3(n);	//X 재귀 호출을 해도 매개변수가 줄지 않는다
}

재귀 함수를 구현할 때 자주 저지르는 실수에 대해서도 적어보았다

base case를 빼먹거나, induction step에서 인자가 base case쪽으로 증감하지 않으면 틀린 구현 방식이다 ❗

 

int fibonacci(int n) {
	if (n <= 1)return n;	//base case
	return fibonacci(n - 1) + fibonacci(n - 2);	//induction step
}

recursion으로 구현한 팩토리얼과 피보나치 함수는 위와 같다.

반드시 base case에 대한 상수 값 처리와 induction step에서의 재귀 호출 및 반환이 무조건 포함되어야 한다는 사실

하지만 기본 상식중에 하나는, 피보나치 함수를 위와 같이 짰을 경우 타임 오버헤드가 일어난다는 충격적인 사실도 있다왜냐? 피보나치 함수를 재귀호출 하는 과정에서 똑같은 매개변수에 대한 값을 중복 호출하기 때문. 그렇기 때문에 memoization이라는 기법을 사용해서 중간 계산 값을 저장해줄 수도 있다(dp).

이러한 재귀 구현 방식을 Top-down 방식이라고 한다. top down 방식은 구현하기 쉽고, 정의 방식을 그대로 옮겨서 사용자가 보기에 매우 직관적이라는 장점이 있다 😱

Iteration: for문 혹은 while문을 이용해서 같은 구조의 연산을, 반복해서 답을 구하는 방법. 이 때 구현시 이용할 정의는 recursion의 정의 혹은 사전적 정의도 가능.

이러한 재귀 구현 방식을 Top-down 방식이라고 한다. top down 방식은 구현하기 쉽고, 정의 방식을 그대로 옮겨서 사용자가 보기에 매우 직관적이라는 장점이 있다 😱

int fact = 1;
for (int i = 1; i <= n; i++) {
	fact = fact * i;
}	//factorial 구현

	int fibo[3] = { 0,1 };
	if (n > 1) {
		for (int i = 2; i <= n; i++) {
			fibo[2] = fibo[0] + fibo[1];
			fibo[0] = fibo[1];
			fibo[1] = fibo[2];
		}
	}
	else {	//n이 0또는 1일 때
		printf("%d", fibo[n]);
	}
	printf("%d", fibo[2]);

iteration을 이용한 구현 방식이다. recursion과 비교했을 때에는 코드를 보고 이해하는데 좀 시간이 걸린다는 단점이 있다.

제대로 구현했을경우 recursion과 iteration은 이론적으로 동일한 시간복잡도를 가진다(위의 recursion-fibonacci 예제 예외).

하지만 실제로 구현했을 때는 iteration의 성능이 훨씬 우수하다.

왜냐면 함수의 호출/리턴에 소요되는 시간이 반복문보다 느리기 때문(새로운 함수를 호출할 때 마다 스택의 저장공간을 차지하므로 공간도 더 차지한다).

그렇기 때문에 소요 시간이 중요할 경우에는 iteration으로, 코드의 가독성 및 난이도가 중요할 때는 recursion(+memoization)으로 구현하는 습관을 기르자

😊