재귀 알고리즘

jooyeon yi
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)
  1. 팩토리얼
  • 팩토리얼 : 팩토리얼이 적용되는 수보다 작거나 같은 모든 양의 정수의 곱 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;};
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade