Recrusion(순환)
: 함수 호출 시 자기 자신을 호출하는 함수(무한루프에 빠지지 않도록 주의)
- Base Case : 적어도 하나의 Recrusion에 빠지지 않는 경우가 존재해야 한다.
- Recrusive Case : Recrusion을 반복하다 보면 결국 Base Case로 수렴해야 한다.
ex) n!, X^n, 피보나치 수(Fibonacci numbers), 최대공약수(Euclid Method)
//n! (1부터 n까지 모든 정수 곱하기)
int factorial(int n)
{
if (n == 1) //base case
return 1;
else return n*factorial(n-1); //recrusive case
}만약 n이 6이라면
6*factorial(6-1) -> 6*5*factorial(5-1) -> 6*5*4*factorial(4-1) -> ... -> 6*5*4*3*2*1 = 720. (시간복잡도 : O(n))
//X^n 거듭제곱(X를 n번 곱하기)
int pow(int x, int n)
{
if (n == 0) //base case
return 1;
else return x*pow(x, n-1); //recrusive case
}만약 x=5 , n=4라면
5*pow(5, 3) -> 5*5*pow(5, 2) -> 5*5*5*pow(5, 1) -> 5*5*5*5*pow(5, 0) -> 5*5*5*5*1 = 625. (시간복잡도 : O(n))
//n번째 피보나치 수 구하기(0 1 1 2 3 5 8 13 21..)
int fib(int n)
{
if (n == 0) return 0; //base case
if (n == 1) return 1; //base case
return fib(n - 1) + fib(n - 2); //recrusive case
}식만 보면 간단하지만 위의 방식대로 구할 경우 똑같은 값을 중복으로 구해 시간이 낭비된다.(반복문이 더 효율적)
int = 5;
fib(5)+fib(4) -> fib(4)+fib(3) + fib(3)+fib(2) -> fib(3)+fib(2)+fib(2)+fib(1) + fib(2)+fib(1)+fib(1)+fib(0) -> ...
위의 예시를 보면 fib(4)는 2번 fib(3)은 3번 fib(2)는 4번 구해진다. (이때 시간 복잡도 : O(2^n))
이를 해결하기 위해서는 한번 구한 피보나치 수열을 다시 활용하면 되지만,
이번 강의의 핵심은 아니니 다음 정리에서 적도록 하겠다.
//유클리드 호제법(최대공약수 구하기)
int gcd(int m, int n)
{
if (m < n) { //m이 항상 커야하므로 n이 더 클경우 swap
tmp = m;
m = n;
n = tmp;
if (m % n == 0) //최대공약수를 찾았을때
return n;
else
return gcd(n, m % n);
}유클리드 호제법은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다.
2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b),
a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다.
만약 m = 128, n = 56이라면
128%56 = 16 -> 56%16 = 8 -> 16%8 = 0으로 128과 56의 최대공약수는 8이된다.
Recrusion VS Iteration
- 모든 순환문은 반복문으로 변경 가능
- 모든 반복문은 순환문으로 대체 가능
순환함수는 반복함수를 단순하고 알기쉽게 표현하나 함수 호출에 따른 오버헤드가 존재한다.
순차탐색(1)
int search(int data[], int begin, int end, int target)
{
if(begin > end) //찾는 target이 없거나 탐색이 불가능 할 경우
return -1;
else if (target == data[end]) //맨 처음 비교하는 수가 target이면
return end;
else
return search(data, begin, end-1, target);
}
순차탐색(2)
int search(int data[], int begin, int end, int target)
{
if (begin > end) { //찾는 target이 없거나 탐색일 불가능 할 경우
return -1;
int middle = (begin + end) / 2;
if (data[middle] == target) //middle이 target이라면 middle return
return middle;
int index = search(data, begin, middle - 1, target); //middle값을 기준으로 왼쪽부터 탐색
if (index != -1)
return index;
else
return search(data, middle + 1, end, target); //왼쪽에 값이 없다면 오른쪽 탐색
}
}