[알고리즘] 재귀 (JS)

📌 참고 사이트

[Algorithm] 재귀 알고리즘이란 recursion algorithm (tistory.com)

[Algorithm] 재귀 알고리즘이란 recursion algorithm

 

[Algorithm] 재귀 알고리즘 배열 javascript 기본 문제 정리 (tistory.com)

[Algorithm] 재귀 알고리즘 배열 javascript 기본 문제 정리

 

 

 

📋 재귀 (Recursion)

📍 재귀 알고리즘의 특징

➡️ 분할 정복법의 한 유형으로 문제를 더 작은 구조의 문제로 잘게 쪼개면서 연산을 분산시키는 방식이다.

 

➡️ 문제를 더 작은 문제로 분해할 수 있는 경우나, 반복문의 중첩이 많아 결과를 예측하기 힘든 경우에 유용하게 사용될 수 있다.

 

➡️ 재귀를 이용한 모든 코드는 for, while 같은 반복문으로 치환 가능하고, 반복문이 코드의 가독성을 해칠 경우 재귀 알고리즘은 가독성과 유지 보수성을 향상시킨다.

 

 

📍 재귀 알고리즘을 사용하는 방법

1️⃣ 문제를 단순화 시킨다.

입력값과 출력값을 정의하는 것부터 시작한다.

 

2️⃣ 더 작은 문제로 분해하기

입력값을 기준으로 더 이상 쪼갤 수 없는 단계까지 문제를 분해한다.

예를 들어 배열을 입력받아 총 합을 구하는 문제가 있다고 해보자.

[1, 2, 3, 4, 5] 이렇게 배열이 주어졌다면 5개의 배열 인자를 4개, 3개, 2개, 1개로 쪼개고 1개의 인자를 가진 배열은 더 이상 쪼갤 수 없으므로 출력 로직을 구성하면 된다.

 

3️⃣ 가장 단순한 문제를 해결

문제를 다 쪼개면 탈출 조건을 정의하여 가장 작은 문제를 해결하면 된다. 

위의 예시의 경우 1개의 배열 인자를 가진 배열을 가지게 되는 단계에서 탈출 조건을 구성하면 된다.

 

4️⃣ 문제 해결 완료

분해했던 문제를 탈출 조건을 통해 하나씩 조합하면서 로직을 완성하면 된다.

 

 

 

📋 재귀 알고리즘 사용해 보기

✏️ 정수의 합 구하기

정수를 하나 받아서 1부터 그 정수까지의 합을 구하는 코드를 짜면 다음과 같다.

 

function sum(n, result) {
  if (n > num) return result;
  else return sum(n + 1, result + n);
}

console.log(sum(1, 0));

 

입력받은 정수는 num이라는 변수에 할당한 상태라고 생각하고 진행해 보자.

1부터 1씩 증가하며 숫자를 더해갈 것이므로 입력이 어떻게 되든 항상 sum(1, 0)의 함수를 호출한다.

첫번째 인자로는 첫 번째로 더할 요소로 1을 적었고, 두 번째 인자로는 더한 결과를 누적하기 위해 0으로 설정하였다. (result에 해당)

n이 num이 될때까지는 결과에 더해지는 연산을 해야 하므로 함수 안에서 반환되는 함수는 sum(n+1, result+n)이고, n이 num보다 커지면 result를 반환하고 함수가 종료되도록 하였다.

 

* 물론 이것보다 더 짧게 작성할 수도 있지만 아직 재귀에 익숙하지 않아 그냥 내가 이해하기 편한 방식으로 작성함.

 

 

✏️ 팩토리얼 문제

음의 정수가 아닌 정수를 하나 입력받아 팩토리얼 계산 결과를 반환하는 코드를 짜면 다음과 같다.

(* 0!은 1을 반환함에 유의하자.)

 

function factorial(n) {
  if (n === 0 || n === 1) return 1;
  else return n * factorial(n - 1);
}

console.log(factorial(num));

 

3! = 3 * 2 * 1이다. 이는 곧 3 * factorial(2)로 나타낼 수 있고, factorial(2)는 2 * factorial(1)로 나타낼 수 있다.

factorial(1)은 종료 지점으로, 1을 반환해야 한다.

인자로 0이 들어간 경우 바로 1을 반환하고 끝내야 하므로 if문의 조건문으로 n === 0 또는 n === 1일 경우 1을 반환하도록 하였다.

그렇지 않을 경우 해당 숫자와 factorial 함수에 해당 숫자 - 1을 넣어 계산한 결과를 곱하는 것으로 쪼갰다.

 

 

✏️ 피보나치 문제

음이 아닌 정수를 하나 입력받아 피보나치 수열의 n번째 요소를 반환하는 코드를 작성해 보면 다음과 같이 된다.

 

const record = { 0: 0, 1: 1 };

function fibo(n) {
  if (Object.keys(record).includes(n.toString())) {
    return record[n];
  } else {
    record[n] = fibo(n - 1) + fibo(n - 2);
    return record[n];
  }
}

console.log(fibo(num));     // 5
console.log(record);     // { '0': 0, '1': 1, '2': 1, '3': 2, '4': 3, '5': 5 }

 

보편적인 피보나치 수열 코드보다 살짝 긴 것을 볼 수 있는데, 이는 record에 결과를 저장함으로써 이미 진행했던 재귀 단계를 또 밟지 않게 하여 성능을 향상시키도록 코드를 작성해 본 것이다.

record에 현재 인자로 들어간 숫자에 대한 피보나치 수열 계산 결과가 저장되어 있지 않다면 추가를 해 주고 현재 계산 결과를 반환한다.

만약 record에 존재한다면 record에 있는 값을 그대로 반환하여 사용하면 된다.

 

❗ JS에서 객체의 키 값으로 Number가 될 수 없으므로 key를 찾을 때 String으로 변환하는 것을 잊지 말아야 한다. 이것을 놓치면 record에서 값을 계속 찾지 못해 재귀가 끝없이 반복되어 결국 에러가 난다.

 

💡 이미 진행했던 재귀 단계를 또 밟는다는 것은 다음과 같은 의미이다.

예를 들어 fibo(5)을 실행한다고 해보자.

보편적인 피보나치 수열 방식을 따른다면

fibo(5) = fibo(4) + fibo(3) = (fibo(3) + fibo(2)) + (fibo(2) + fibo(1)) = ((fibo(2) + fibo(1)) + (fibo(1) + fibo(0))) + ((fibo(1) + fibo(0)) + 1) .......   이 과정을 모두 거쳐야 하는 것이다. fibo(3)과 fibo(2)를 여러 번 구하게 된다.

이것은 입력 숫자가 커졌을 때 비효율적이므로 record라는 객체에 피보나치 수열 계산 값을 저장한 것이다.

record 객체에 기록된 내용을 사용하면 fibo(3) 같은 것을 구할 때에도 fibo(2) + fibo(1) = (fibo(1) + fibo(0)) + 1 ...의 과정을 거치지 않고 이미 저장된 값을 이용해 record['2'] + record['1'] 이렇게 쉽게 구할 수 있으므로 시간이 많이 단축된다.