References
이번 글은 아래 자료들을 참고하여 작성하였습니다.
Recursive Algorithms on Khan Academy
Think Like a Programmer
위 인형은 러시아의 전통 인형 마트료시카이다. 큰 인형을 열면 그보다 작은 인형이 하나 나오고 다시 그 인형을 열면 또 작은 인형이 나오고를 반복하며 점점 크기가 작아진다. 재귀 함수도 이와 마찬가지로 주어진 조건을 충족할 때까지 함수 자신의 크기를 줄여가다 조건을 충족하면 결과값을 반환하는 함수이다.
배열 내 값 모두 더하기
// solution 1.
const numArr1 = [1, 2, 3, 4, 5];
function iterativeArraySum(array, size) {
let sum = 0;
for (let i = 0; i < size; ++i) {
sum += array[i];
}
return sum;
}
console.log(iterativeArraySum(numArr1, numArr1.length)); // 15위 코드는 주어진 배열의 길이만큼 for문으로 주어진 배열을 탐색하여 배열 내 모든 값의 합을 반환하는 함수이다. 이 함수를 살펴보면 배열 index 0부터 끝까지 탐색하며 값을 하나하나 더해나가는 것을 알 수 있다. 일정 조건 하에 반복 작업을 수행하는 함수라면, 반복문 대신 재귀 함수로 바꿔 쓸 수 있다.
위 함수를 완전한 재귀 함수로 바꿔 쓰기 전에 위 반복문은 그대로 놔둔 채 다른 기능을 수행하는 함수를 추가하여 보다 재귀 함수와 가까워지게 작성해보자.
// solution 2.
function iterativeArraySum(array, size) {
let sum = 0;
for (let i = 0; i < size; ++i) {
sum += array[i];
}
return sum;
}
function arraySumDelegate(array, size) {
if (size === 0) return 0;
// the last number in the array is stored in this local variable
const lastNum = array[size - 1];
// the sum of all the other values in the array is computed and this result is stored in this local variable
const allButLastSum = iterativeArraySum(array, size - 1);
return lastNum + allButLastSum;
}
console.log(arraySumDelegate(numArr1, numArr1.length)); // 15- 주어진 배열의 길이가
0이라면 결과값0반환. - 주어진 배열의 길이가
0보다 크다면 반복문을 호출하여size의 값이0이 될 때까지 배열값 더하기 작업 수행
위의 함수를 재귀 함수로 바꾸기 위해서는 iterativeArraySum으로 호출하는 반복문을 지금 실행 중인 함수로 치환하면 된다. 작성하면 아래와 같이 된다.
// solution 3.
const numArr1 = [1, 2, 3, 4, 5];
function arraySumRecursive(array, size) {
if (size === 0) return 0;
const lastNum = array[size - 1];
const allButLastSum = arraySumRecursive(array, size - 1);
return lastNum + allButLastSum;
}
console.log(arraySumDelegate(numArr1, numArr1.length)); // 15위의 함수를 실행하게 되면 size의 값이 0이 될때까지 해당 작업을 반복하며 배열 내 값을 모두 더한다. solution 2.에서는 allButLastSum에 해당하는 값으로 다른 반복문을 불러왔다면, 여기서는 자기 자신을 호출함으로써 재귀적 작업을 수행한다.
Recursive Algorithms 활용 예들
The Factorial Function
const factorial = function (n) {
// base case:
if (n === 0) {
return 1;
}
return n * factorial(n - 1);
};
console.log(factorial(5)); // 120위의 함수는 1부터 n까지 자연수의 곱을 계산하는 함수이다. n-1을 설정하여 함수 factorial이 재귀적으로 쓰인 것을 볼 수 있다.
determine palindrome
const firstCharacter = function (str) {
return str.slice(0, 1);
};
// Returns the last character of a string str
const lastCharacter = function (str) {
return str.slice(-1);
};
// Returns the string that results from removing the first
// and last characters from str
const middleCharacters = function (str) {
return str.slice(1, -1);
};
const isPalindrome = function (str) {
// base case #1
if (str.length <= 1) return true;
// base case #2
if (firstCharacter(str) === lastCharacter(str))
return isPalindrome(middleCharacters(str));
// recursive case
return false;
};
const checkPalindrome = function (str) {
console.log("Is this word a palindrome? " + str);
console.log(isPalindrome(str));
};
checkPalindrome(""); // true
checkPalindrome("a"); // true
checkPalindrome("motor"); // false
checkPalindrome("rotor"); // true위의 코드는 주어진 문자열이 palindrome인지 판별하는 함수이다. 입력값이 없거나 하나인 경우 palindrome이기 때문에 true를 반환한다. 입력값의 길이가 2 이상인 경우 첫째값과 마지막 값을 잘라내어 일치 여부를 확인하고 나머지 중간값을 반환, 다시 반환된 중간값의 첫째값과 마지막값의 일치 여부를 확인하는 작업을 반복한다. 작업을 마친 후 palindrome이라면 true, 아니라면 false를 반환한다.
Fibonacci Series
function fib(n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
console.log(fib(9)); // 34위 함수는 피보나치 수열을 재귀 함수로 작성한 것이다. 함수를 실행하면 앞의 수와 앞앞의 수를 더하는 작업을 반복하여 입력값 n번째 위치하는 피보나치의 수를 구한다.
함께 보기
