재귀 기초

재귀라는 용어는 익숙하지만 직접 구현하려고 하면 매우 골치가 아팠다.

정답 코드를 보며 스택 프레임을 직접 그려보아도 다시 코드를 구현하려면 머릿속이 백지가 되었다.

재귀가 어려운 이유를 두 가지로 좁히면 다음과 같다.

 

1. 어디를 재귀호출해야되는지 모르겠다.

2. 종료조건이 어떻게 되어야하는지 모르겠다.

 

다른말로 바꾸면 위의 두가지를 명확하게 정의해야 재귀적 접근이 가능하다는 것이다.

선언적 프로그래밍

재귀 알고리즘은 선언형 프로그램의 방식을 따라야한다.

선언형 프로그래밍이란 목표를 명시하고 알고리즘을 명시하지 않는 것이다.

여기서 목표는 종료조건과 문제의 정의이다.

이 목표만 명시하면 나머지 연산은 컴퓨터가 알아서 해준다.

 

쉬운 것부터 접근해보자.

십진수가 주어지면 이진수로 출력하는 코드를 재귀 알고리즘을 사용해 구현하는 문제가 있다.

예를 들어 11이 주어지면 1011이 출력되어야한다.

십진수를 이진수로 바꾸는 과정은 다음과 같다.

 

이렇게 나머지를 화살표 방향으로 출력하면 1011이 나온다.

11을 2로 나누고, 다시 해당 몫을 2로 나누는 과정이 반복된다.

여기서 문제의 정의를 내릴 수 있다. 인풋값이 n일 때, n / 2를 재귀적으로 호출하면 된다.

그리고 화살표 방향처럼 거꾸로 나머지를 출력하기 위해 재귀호출 아래에 나머지를 answer에 더해주는 코드를 작성한다.

function solution(num) {
  let answer = '';
  function DFS(n) {
    if (condition) {
    } else {
      DFS(Math.floor(n / 2)); // 6번째줄
      answer += (n % 2) + ' ';
    }
  }
  DFS(num);
  return answer;
}

const input = 11;
console.log(solution(input)); // 1011

 

스택 프레임은 다음과 같을 것이다.

 

표기방법 ➡ DFS(n) - 줄의 이름

그런데 종료조건이 없으면 콜스택이 초과된다. 따라서 종료조건을 명확하게 정의해야한다.

종료조건은 n이 0이 되면 함수를 종료하도록 하면 된다. 따라서 최종코드는 다음과 같다.

function solution(num) {
  let answer = '';
  function DFS(n) {
    if (n === 0) return;
    else {
      DFS(Math.floor(n / 2));
      answer += (n % 2) + ' ';
    }
  }
  DFS(num);
  return answer;
}

const input = 11;
console.log(solution(input)); // 1011

 

---

1️⃣팩토리얼 (백준 27433)

재귀함수를 이용해서 팩토리얼을 계산해보자.

n! 은 다음과 같이 표현할 수 있다.

n! = n * (n - 1) * (n - 2) * ... * 1

문제를 정의하기 위해서는 패턴을 찾아야한다. 팩토리얼에서는 다음과 같은 패턴을 가질 수 있다.

n! = n * (n - 1)!

(n - 1)! = (n - 1) * (n - 2)!

(n - 2)! = (n - 2) * (n - 3)!

 

따라서 재귀함수가 DFS라고 한다면 다음과 같이 정의할 수 있다.

n * DFS(n-1)

 

이제는 종료조건을 찾아야한다.

n이 0이 된다면 1을 리턴해야한다. 

예를 들어 3! 을 구한다면 문제의 정의에 따라 다음과 같이 표현할 수 있다.

3! = 3 * 2!

2! = 2 * 1!

1! = 1 * 0!

여기서 n이 0일 때 1을 리턴해야 1!은 1이 되고, 그러면 2!은 2가 되고 3!은 6이된다. 거꾸로 다시 올라간다고 보면 된다.

function solution(n) {
  function DFS(v) {
    if (v === 0) return 1;
    else {
      return v * DFS(v - 1);
    }
  }
  return DFS(n);
}

console.log(solution(10));

 

---

 

2️⃣피보나치 수 (백준 10870)

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

10

예제 출력 1

55

---

문제의 정의가 문제 속에 주어졌다.

Fn = Fn-1 + Fn-2

종료조건을 찾아주면 되는데 n이 0일때는 0을 반환하고 n이 1일때는 1을 반환하면 된다.

function solution(n) {
  function DFS(v) {
    if (v <= 1) return v;
    else {
      return DFS(v - 1) + DFS(v - 2);
    }
  }
  return DFS(n);
}

console.log(solution(10));

 

👀참고자료

https://ko.javascript.info/recursion

재귀와 스택