재귀 알고리즘(Recursive Algorithms)

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

1. 주어진 배열의 길이가 0이라면 결과값 0반환.
2. 주어진 배열의 길이가 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번째 위치하는 피보나치의 수를 구한다.

---

---

함께 보기

Fibonacci
Palindromes
Towers of Hanoi