[알고리즘] Recursion
by Jewoo.Song
Recursion
- 재귀함수
- 자기 자신을 호출하는 함수
- 무한 루프에 빠지지 않도록 조건을 잘 세워야한다.
- Base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
- Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 한다.
기본적인 수학함수에서의 Recursion 예
Factorial: n!
- Recursion 관점에서의 접근
- 0! = 1 : Base case
- n! = n * (n-1)! if n>0 : Recursion case
function factorial(n) {
if (n == 0) return 1;
else return n * factorial(n - 1);
}
power (x^n)
- Recursion 관점에서의 접근
- x^0 = 1 : Base case
- x^n = x*x^n-1 if n>0 : Recursion case
function power(x, n) {
if (n == 0) return 1;
else return x * power(x, n - 1);
}
Fibonacci Number
- Recursion 관점에서의 접근
- f0 = 0 : Base case
- f1 = 1 : Base case
- fn = fn-1 + fn-2 if n>1 : Recursion case
function fibonacci(n) {
if (n < 2) return n;
else return fibonacci(n - 1) + fibonacci(n - 2);
}
최대공약수 gcd
- m>n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m, n)=n이고,
- 그렇지 않으면 gcd(m, n)= gcd(n, m%n)이다.
- Recursion 관점에서의 접근
- if n == 0 return n : Base case
- gcd(m, n) = gcd(n, m%n) : Recursion case
function gcd(m, n) {
if (m < n) {
var temp = m;
m = n;
n = temp;
}
if (n == 0) return m;
else return gcd(n, m % n);
}
다른 예(일반적으로 반복문으로 행하는 동작들)
- 일반적으로
반복문으로 하는 모든 동작은 Recursion
으로 나타낼 수 있다. - 즉, 모든 Recursion은 반복문으로 변경이 가능하다.
- Recursion은 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.
- 하지만 함수 호출에 따른 오버헤드가 있다.(매개변수 전달, 액티베이션 프레임 생성 등)
이진수로 변환하여 출력
- Recursion 관점에서의 접근
- if n < 2 return n : Base case
- f(n / 2) : Recursion case
- return n%2 : Recursion case
function printInBinary(n) {
if (n < 2) {
console.log(Math.floor(n));
} else {
printInBinary(n / 2);
console.log(Math.floor(n % 2));
}
}
data[0]에서 data[n-1]까지의 합
- Recursion 관점에서의 접근
- if n < 0 return 0 : Base case
- return f(n-1) + data[n-1] : Recursion case
function sum(n, data) {
if (n <= 0) {
return 0;
} else {
return sum(n - 1, data) + data[n - 1];
}
}
Designing Recursion(순환적 알고리즘 설계)
- 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다.
- 모든 case는 결국 base case로 수렴해야 한다.
- 암시적 매개변수를 명시적 매개변수로 바꿔야 한다.
- 맨 처음 호출될 때의 상황 뿐아니라 Recursive하게 호출될 때의 상황을 고려해야한다.
- 즉, 함수를 일반화시켜야 한다.
- 명시적 매겨변수 사용
순차 탐색
- 반복문을 사용한 순차탐색을 Recursion 함수로 변경한다.
- 시작 위치를 명시적으로 입력해준다.
function LinearSearch(data, n, target) {
for (var i = 0; i < n; i++) {
if (data[i] == target) return i;
}
return -1;
}
이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적으로 지정한다.
function LinearSearch(data, target, begin, end) {
if (begin > end) {
return -1;
} else if (target == data[begin]) {
return begin;
} else {
return LinearSearch(data, target, begin + 1, end);
}
}
최대값 찾기
- 이 함수의 미션은 data[begin]에서 date[end] 사이에서 최대값을 찾아 반환한다.
- begin<=end라고 가정한다.
function findMax(data, begin, end) {
if (begin == end) {
return data[begin];
} else {
return Math.max(data[begin], findMax(data, begin + 1, end));
}
}
Binary Search
- items[begin]에서 items[end] 사이에서 target을 검색한다.
function binarySearch(arr, target, begin, end) {
if (!begin) begin = 0;
if (!end) end = arr.length;
if (begin > end) {
return -1;
} else {
var mid = (begin + end) / 2;
if (target == arr[mid]) {
return mid;
} else if (target < arr[mid]) {
return binarySearch(arr, target, begin, mid - 1);
} else {
return binarySearch(arr, target, mid + 1, end);
}
}
}
참고
Subscribe via RSS