재귀 알고리즘
Sep 3, 2018 · 8 min read
- 재귀 함수는 자기 자신을 실행시키는 함수다.
- 재귀적인 문제 해결이란 ? 복잡한 문제를 쪼개고 쪼개서 즉시 풀 수 있는 문제로 작아지게 만든다. 동일한 문제의 더 작은 경우를 해결함으로써 그 문제를 해결하는 것.
- 재귀 함수의 장점 : 정의를 그대로 담을 수 있다. 재귀적으로 표현된 식은 식이 진행되는 걸 상상하기에 용이하고 정의와 가장 흡사하게 코딩을 할 수 있다.
- 재귀 함수의 단점 : 더 많이 연산해야 한다. 이는 underscore의 memoize와 같은 함수를 써서 해결 가능하다. (memoize는 한 번 계산된 값은 cache에 저장해놓고, 똑같은 계산을 해야할 때 연산 없이 저장된 값을 찾아 반환해준다. 참고: underscore.org )
재귀 함수의 기본적인 형태
- 예외 처리 조건 적어주고, 변하지 않는 고정된 값을 base case 조건으로, 이후에 recursive 조건을 적어준다.
var function_name = function(input) {
if (termination_condition) { // 무한 루프에 빠지지 않기 위해 필요하다.
return value;
} elseif (base_case) {
return value; }
// recursive case
return (expression_with_recursion_call)
};
재귀함수를 활용하는 케이스
- factorial, fibonacci numbers, tree travesal 구조에서 해결해야하는 모든 경우 (Finding node, stringifyJSON, getElementsByClassName, document object model)
- 팩토리얼
- 팩토리얼 : 팩토리얼이 적용되는 수보다 작거나 같은 모든 양의 정수의 곱 ex) 5! = 5 * 4 * 3 * 2 * 1
var factorial = function(n) {
// base case:
if (n === 0) {
return 1;
}
return factorial(n-1) * n;
};println("The value of 0! is " + factorial(0) + ".");
println("The value of 5! is " + factorial(5) + ".");Program.assertEqual(factorial(0), 1);
Program.assertEqual(factorial(5), 120);
2. 문자열이 회문인지 확인
- 회문 : 앞으로 읽어도 뒤로 읽어도 똑같은 문자 ex) level
// Returns the first character of the string str
var firstCharacter = function(str) {
return str.slice(0, 1);
};// Returns the last character of a string str
var lastCharacter = function(str) {
return str.slice(-1);
};// Returns the string that results from removing the first
// and last characters from str
var middleCharacters = function(str) {
return str.slice(1, -1);
};var isPalindrome = function(str) {
if (str.length === 0 || str.length === 1) {
return true;
} else if (firstCharacter(str) !== lastCharacter(str)) {
return false;
} else {
return isPalindrome(middleCharacters(str));
}
};var checkPalindrome = function(str) {
println("Is this word a palindrome? " + str);
println(isPalindrome(str));
};checkPalindrome("a");
Program.assertEqual(isPalindrome("a"), true);
checkPalindrome("motor");
Program.assertEqual(isPalindrome("motor"), false);
checkPalindrome("rotor");
Program.assertEqual(isPalindrome("rotor"), true);
3. x의 n승 확인
var isEven = function(n) {
return n % 2 === 0;
};var isOdd = function(n) {
return !isEven(n);
};var power = function(x, n) {
println("Computing " + x + " raised to power " + n + ".");
// base case
if (x === 1 || n === 0) {
return 1;
} else if ( n > 0 && isOdd(n) ) {
return x * power(x, n-1);
} else if ( n > 0 && isEven(n) ) {
var y = power(x, n/2);
return y * y;
} else if ( n < 0 ) {
return 1/power(x, -(n));
}
};var displayPower = function(x, n) {
println(x + " to the " + n + " is " + power(x, n));
};
4. stringifyJSON(=JSON.stringify) 구현
- JSON.stringify(parameter) 적용했을 때, 파라미터 타입에 따라 아래와 같이 다른 값을 반환한다.
- type이 number나 boolean : string으로 바꿔 반환. ex) JSON.stringify(true) // ‘true’
- type이 string : string 문자 그대로 박제한 걸 string으로 반환. ex) JSON.stringify(“Hello”) // “”Hello”” (참고로 JSON은 큰따옴표만 사용한다.)
- type이 array/object : array/object 형태 그대로 박제한 걸 string으로 반환 ex) JSON.stringify([‘a’, ‘b’]) // “[‘a’, ‘b’]”
- 단, array의 element나 object의 value가 undefined/함수/symbol이면 이를 string인 null로 바꾼 후 박제해 반환.
var stringifyJSON = function(obj) {var result;
var arr;
if (typeof(obj) === 'number' || typeof(obj) === 'boolean' || obj === null) {
return String(obj);
} else if (typeof(obj) === 'string') {
arr = [];
for (var i = 0; i < obj.length; i++) {
arr.push(obj[i])
}
result = arr.join('');
return "\"" + result + "\"";
} else if (Array.isArray(obj)) {
arr = [];
for (var i = 0; i < obj.length; i++) {
if (obj[i] === undefined || typeof(obj[i]) === 'function' || typeof(obj[i]) === 'symbol') {
arr.push(String(null));
} else {
arr.push(stringifyJSON(obj[i]));
}
}
result = arr.join(',');
return '[' + result + ']';} else if (typeof(obj) === 'object') {
arr = [];
for (var prop in obj) {
if (obj[prop] === undefined
|| typeof(obj[prop]) === 'function'
|| typeof(obj[prop]) === 'symbol') {
} else {
arr.push(stringifyJSON(prop));
arr.push(':');
arr.push(stringifyJSON(obj[prop]));
arr.push(',');
}
}
arr.pop();
result = arr.join('');
return '{' + result + '}';}};
5. 재귀를 활용해 document.getElementsByClassName 구현
var getElementsByClassName = function(className){var bodyElements = document.body;var newArr = [];var chkAndAdd = function(inputElement) {if (inputElement.classList && inputElement.classList.contains(className)) {newArr.push(inputElement);}if (inputElement.childNodes.length >= 1) {for (var i = 0; i < inputElement.childNodes.length; i++) {chkAndAdd(inputElement.childNodes[i]);}}};if (bodyElements.childNodes.length < 1) {return;}chkAndAdd(bodyElements);return newArr;};