CS 부수기 - 알고리즘 (재귀) 편
0. Recursion Algorithm
어느 한 컴공과 학생이 교수를 찾아갔다.
학생 : 교수님, 재귀 함수가 뭔가요?
교수 : 봐봐, 옛날에 학생이 하나 있었어. 그 학생이 교수를 찾아가 이렇게 물었지.
학생 : 교수님, 재귀 함수가 뭔가요?
교수 : 봐봐, 옛날에 학생이 하나 있었어. 그 학생이 교수를 찾아가 이렇게 물었지.
학생 : 교수님, 재귀 함수가 …
재귀 함수(Recursion Function)의 정의 위키피디아에 따르면 다음과 같다.
컴퓨터 과학에 있어서 재귀는, 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻함.
즉, 함수에 자기 자신을 넣어 다시 호출하여 작업을 수행하는 방법을 재귀 함수라고 한다.
위의 예시는 재귀 함수를 이해하기 위한 가장 기초적인 관문 중 하나이다.
개발을 하는 사람이라면 한번쯤은 들어본 농담이며, 실제로 재귀 함수를 이해하는 데 가장 큰 힌트를 주기에 저렇게 써봤다.
이러한 재귀 함수는 알고리즘에서도 많이 쓰이며, 대표적으로 팩토리얼(Factorial), 피보나치(Fibonacci), 하노이의 탑(Tower of Hanoi)에 많이 쓰인다.
그럼 한번 알아보자.
1. 예제 코드
재귀함수의 예제 코드를 c와 python으로 작성하면 다음과 같다.
// Recursion Function Example
#include <stdio.h>
// 재귀 함수
void recursion(int num) {
// 0이 되면 함수 종료를 반환
if (num == 0) {
return;
}
// 현재 num을 print
printf("%d | Recursion \n", num);
// num은 1씩 작아짐
num -= 1;
// 1 작아진 num을 다시 파라미터로 자기 자신을 호출
recursion(num);
}
int main() {
// 최초 5를 파라미터로 입력
recursion(5);
}
결과는 다음과 같다.
재귀 함수 코드 결과
코드에 주석으로 설명하였지만, 간단히 정리하자면 다음과 같다.
최초 5라는 파라미터를 재귀 함수에 넘겨주고, 재귀함수는 main함수로부터 받은 파라미터를 print하며 파라미터를 1씩 줄이는 역할을 한다.
또한 파라미터가 0이 될 경우 함수 종료를 반환해준다.
때문에 결과는, 최초 5를 시작으로 1씩 줄어들며 0이 될때까지 함수를 반복하고, 0이 되면 함수를 종료하며 코드가 종료된다.
다음 코드를 파이썬으로 작성하면 다음과 같다.
# Recursion Function Example
def recursion(num):
if num == 0:
return
print(num, "| Recursion")
num -= 1
recursion(num)
recursion(5)
이 코드 또한 결과는 다음과 같다.
재귀 함수 python 코드 결과
이 정도면 충분한 이해가 가능할 듯하다.
그렇다면, 이러한 재귀 함수의 장점과 단점은 무엇일까.
정리하면 다음과 같다.
- 장점
- 함수화로 간결해지는 코드
- 단점
- 메모리의 사용이 커짐 (StackOverflow)
- 속도가 느림 (잦은 함수의 호출과 반환으로 인한 Context Switching)
재귀함수는 for문에 비해 훨씬 더 간결한 코드 정리가 가능해진다.
하지만 재귀 함수의 특성상, LIFO(Last-In First-Out)의 자료 구조인 Stack과 같은 형상을 띄어, 메모리의 사용량이 커짐과 동시에 잦은 함수의 호출, 반환으로 속도가 느리다는 단점이 있다.
때문에, 대체적으로 범위가 큰 형태의 반복문을 사용할때는 재귀 함수보다 for 혹은 while이 더 효과적이다.
그렇다면, 재귀 함수를 이용한 대표적인 알고리즘들인 팩토리얼, 피보나치, 하노이탑을 살펴보자.
2. Factorial Algorithm
재귀 함수의 가장 대표적인 알고리즘은 뭐니뭐니해도 팩토리얼(Factorial)이지 않을까 싶다.
팩토리얼(Factorial)이란 수학에서, 자기 자신부터 1씩 줄여가면 1까지 모든 수의 곱을 의미한다.
수식으로 표현하면 다음과 같다.
이러한 팩토리얼은 반복문으로 구현 가능하지만, 재귀함수로도 구현이 가능하다.
먼저 C언어를 이용해 구현한 코드를 살펴보자.
// Factorial Algorithm
#include <stdio.h>
// for문을 이용한 팩토리얼 구현
int factorial_repeat(int num) {
int result = 1;
// 목표하는 num부터 1까지 1씩 빼주며 곱하기
for(int i = num; i > 0; --i) {
result = result * i;
}
return result;
}
// 재귀함수를 이용한 구현
int factorial_recursion(int num) {
// num이 1이 되면 1 반환
if(num == 1) {
return 1;
}
// num에서 1씩 빼면서 자기 자신의 함수에 넣어주고
// 그 수를 기존 num과 곱함
return num * factorial_recursion(num - 1);
}
int main() {
printf("Factorial using for-repeat = %d \n", factorial_repeat(5));
printf("Factorial using recursion = %d \n", factorial_recursion(5));
}
위 코드의 결과는 다음과 같이 나온다.
코드에 기본적인 주석들로 설명했지만, 정리하면 다음과 같다.
for반복문을 이용한다면, num으로부터 1씩 줄이며 곱해주면 된다.
이를 재귀 함수로 풀어낸다면, num부터 1씩 줄어든 값을 재귀 함수로 재호출해주며, 이때 재호출해준 함수는 기존의 num과 곱해준다.
최종적으로 num이 1이 되는 순간, 그 값은 1자체를 반환하여 다시 거슬로 올라가는 형태를 띄게 된다.
다음 코드를 파이썬으로 작성하면 다음과 같다.
# Factorial Algorithm
# using for - repeat
def factorial_repeat(num):
result = 1
for i in reversed(range(1, num + 1)):
result = result * i
return result
# using recursion function
def factorial_recursion(num):
if num == 1:
return 1
return num * factorial_recursion(num - 1)
print(factorial_repeat(5))
print(factorial_recursion(5))
결과는 다음과 같다.
다음은 피보나치 수열이다.
3. Fibonacci Algorithm
다음 알아볼 알고리즘은 피보나치(Fibonacci) 수열이다.
피보나치 수열이란, n항을 기준으로 (n-1)항과 (n-2)항의 합으로 이루어지는 형태를 띈 수열을 의미한다.
다음과 같다.
따라서 $ n = (n - 1) + (n - 2) $ 라는 공식이 성립되는 수열이다.
이러한 피보나치 수열 또한 재귀 함수로 표현이 가능하다.
먼저 C언어로 작성한 피보나치 수열 코드이다.
// Fibonacci Algorithm
#include <stdio.h>
// 반복문을 이용한 함수
int fibonacci_for(int num) {
int fib1 = 0;
int fib2 = 1;
int fib3 = 0;
// fib3 = fib1 + fib2
// fib1 = fib2, fib3 = fib2로 바뀜
for (int i = 2; i < num; i++) {
fib3 = fib1 + fib2;
fib1 = fib2;
fib2 = fib3;
}
return fib3;
}
// 재귀 함수를 이용
int fibonacci_recursion(int num) {
// 파라미터 num이 1일 경우 0을 반환
if (num == 1) {
return 0;
// 파라미터 num이 2일 경우 1을 반환
} else if (num == 2) {
return 1;
}
// num 기준 전 항과 전전 항을 호출
return fibonacci_recursion(num - 1) + fibonacci_recursion(num - 2);
}
int main() {
printf("Fibonacci Using for = %d \n", fibonacci_for(10));
printf("Fibonacci Using Recursion = %d \n", fibonacci_recursion(10));
}
결과는 다음과 같다.
간략하게 설명하면 다음과 같다.
for 반복문을 이용하면, 최초의 fib1, fib2 변수에 각각 1항, 2항의 값(0과 1)을 입력하고, fib3 변수는 fib1, fib2를 더하도록 한다.
그리고 fib3 변수 값이 정해지면 각 fib1과 fib2를 fib2와 fib3로 스왑해준 후 다음 반복을 실행한다.
이를 재귀 함수를 이용하게 되면, num 파라미터가 각 1, 2씩 줄인 후, 이를 재귀 함수로 return하고, 최종적으로 num값이 1과 2에 도달하면 각각 이를 0과 1로 return해주면 된다.
다음 피보나치 수열을 파이썬으로 작성하면 다음과 같다.
# Fibonacci Algorithm
def fibonacci_for(num):
fib1, fib2, fib3 = 0, 1, 0
for i in range(2, num):
fib3 = fib1 + fib2
fib1 = fib2
fib2 = fib3
return fib3
def fibonacci_recursion(num):
if num == 1:
return 0
elif num == 2:
return 1
return fibonacci_recursion(num - 1) + fibonacci_recursion(num - 2)
print("Fibonacci Using for =", fibonacci_for(10))
print("Fibonacci Using Recursion =", fibonacci_recursion(10))
결과는 다음과 같다.
이와 같이 정리된다.