안녕하세요 c++을 공부하고있는 대학생입니다. 이번에는 자료구조 내용을 복습해볼겸, 재귀에 관하여 정리 해 보았습니다.
재귀함수는 하나의 함수에서 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법. 이라고 설명이 되어있습니다.
그렇다면 어떤경우에 사용하고 어떻게 풀어나가야하지 정리 해 보겠습니다.
어떤경우에 사용해야할까?
1. 연산의 횟수가 많아진 경우
2. 반복문 보다 더 효율적으로 사용 할 수 있을때 (팩토리얼 , 하노이 탑, 피보나치 등)
그렇다면 방법은??
1. 탈출구를 만든다. (가장 중요)
2. 그림을 그려보면서 의사코드로 작성 후, 수학적인 배경지식이 필요하다면 반드시 활용한다.
3. 반드시 예외를 고려하고 가장 최적화된 방법으로 구현하자.
재귀를 직접 구현 해 보면서, 빅오 표기법으로 본다면 반복문으로 하면, O(n)으로 시간복잡도가 표현되겠지만, 재귀를 잘 쓴다면 O(n) 보다 더 빠르게 할 수 있다는것을 배웠습니다. 대표적으로는 병합정렬 , KMP알고리즘, 위상정렬, 이진탐색 등 이 있습니다.
우선 간단하게 x^n 을 구하는 것 먼저 구현 해 보았습니다. (c 코드)
#include <stdio.h>
int function(int x,int n) {
if(n==0) return 1;
else if(n%2==0) {
return function(x*x,n/2);
}
else {
return x*function(x*x,n-1/2);
}
}
int main() {
printf("%d",function(2,10));
}초기 아이디어를 말씀드리자면, 2^10 = 1024 가 나온다는것을 알고있기에 이것을 구현하고자 잡았습니다.(x = 2 , n = 10)
2^10의 경우 다음과 같이 나타 낼 수 있습니다.
2^10 = 2x2^9 or 2^10 = 2x2x2^8
이런식으로 곱연산에 의해 나누어서 생각 할 수 있습니다. 그래서 2^10을 가장 간단하게 표현하면,
2^10 = (2^2)^5
가 됩니다. 왜 이렇게 표현하는게 가장 간단한 표현인가 하면 하나의 식으로 표현하고자 할 때
2^10 을 계속 2의 n제곱으로 나열하면 2x2x2x2x2x2x2x2x2x2 이런식으로 되는데, 이것을 지수법칙을 이용해서 나타낼 수 있는 가장 간단한식이 (4)^5 가됩니다.
다른 방법이 있나 해서 계속 찾아봤는데 이게 가장 간단하게 연산을 할 수 있는 식이어서 그 점을 참고하여 구현하였습니다.
그리고 주의해야 할 점이, n이 홀수일때입니다. 왜냐하면 n/2 에서 n이 홀수면 몫이 정수로 될 수 없기때문입니다.
그러므로 짝수로 만들어주는것을 중점으로 합니다 예를들어, 2^9가 있다고 가정하면,
2^9 = 2x2^8 이 됩니다. 그러므로 2^8에서 위의 식을 사용하여 (4)^4가 됩니다.
그러면 최종식은 2x(4)^4 가 됩니다.
이런식으로 n이 짝수일때와 홀수일때를 나누어서 계산한 다음, n이 0이되는순간 1값을 리턴하여 값을 출력하는 형식으로 코드를 짰습니다.
그렇다면 팩토리얼은 어떻게 해야할 지 구현 해 보겠습니다.
#include <stdio.h>
int function(int n){
if(n==1) return 1;
else {
return n*function(n-1);
}
}
int main() {
printf("%d",function(4));
}
팩토리얼 자체가 5! 으로 예를들자면 , 5! = 5x4x3x2x1 이므로, 자기자신과 그앞에있는 수를 곱하면서 연산을 진행합니다.
그러므로 n이 1이되었을때 1값을 반환 해 주고, 1이 아니라면 return을 통해 자기자신과 자기자신 -1 의 수를 곱하는 연산을 수행하도록 표현합니다.
마지막으로 피보나치수열을 구현 해 보겠습니다.
#include <stdio.h>
int function(int n){
if(n==1) return 1;
else if(n==0) return 0;
else {
return function(n-1)+function(n-2);
}
}
int main() {
printf("%d",function(10));
}피보나치 수열을 본다면 0 1 1 2 3 5 8 13 21 34 55 이런식으로 n번째항이 n-1 번째와 n-2번째 항을 더한 값이 됩니다.
n이 0일때는 0을 리턴해주고, 1일때는 1을 리턴해주며, 그 외의 값들은 function(n-1) + function(n-2) 값을 리턴하여 피보나치의 수식과 일치시켜 구현하였습니다.
간단하게 재귀의 기본 3가지를 구현 해 보았습니다. 제가 공부하면서 느낀것은, 재귀가 꼭 빠른것은 아니지만 효율적인 알고리즘을 구현하기위해서는 반드시 알아야되는 부분입니다. 재귀가 반복문보다 느린경우는 한가지밖에 없습니다. 그것은 같은 항을 중복해서 연산하기 때문입니다. 그렇기떄문에 반복문이 재귀보다 더 빠르다 라는 생각을 가진 사람이 많습니다. 하지만 기존에 반복문으로 O(n) 이 나오는 알고리즘이 , 재귀 하나로 O(n/2) or O(logn) 처럼 나올 수 있습니다. 이런경우는 위의 코드처럼 불필요한 연산의횟수를 줄이는 코딩을 하거나, 조금 더 어려운 내용으로 들자면 dp (다이나믹 프로그래밍), 메모이제이션 기법이 있습니다. 특히 메모이제이션 기법은, 기존 재귀에서 중복되는 항의 연산을 피할 수 있게 해주는 정말 효율적이고 어려운 기법입니다. 나중에 기회가 된다면 velog에 나중에 올리겠지만, 실제로 저도 연습코딩을 많이 해 보면서 재귀문제 large 버전의 경우 메모이제이션으로 시도 해 본 기억이 있습니다.(물론 저도 어려웠지만..) 이렇게 사용되는 순간이 오기때문에 dp , 메모이제이션 부분도 공부해보면 좋을 것 같습니다.
