자바스크립트 피보나치 수열 연습 1(재귀)

몇 주 전에 자바스크립트를 배우면서 퀘스트 과제로 제시되었던 피보나치 수열 & 피보나치 array가 문득 생각났다.
그 당시에 꽤 어렵게 느꼈었는데 어떻게든 '테스트 코드'를 먼저 작성하고 풀어내리라 다짐했고 실제로 시간은 오래 걸렸지만 테스트를 계속 짜면서 문제를 풀었던 경험이 있는지라 다시한번 그 문제를 통해 테스트코드 작성 & 자바스크립트 손에 익히기를 실천하고자 했다.

지금 살펴보니 피보나치 수열은 모던 자바스크립트 문서의 재귀함수 편에도 예시로 실려있는 거 아니겠는가..ㅎㅎ 넘나 늦게 발견했군.
과제와는 요구사항이 살-짝 다르긴 하지만, 어쨌든 피보나치 넘버 원리 자체가 변동된 것은 아니기에 오늘 풀어본 방법에 대해 간략히 정리해본다.

결론적으론 지난번에 풀었던 방법과는 다르게 풀었더라.
피보나치 넘버를 만드는 방법은 같았는데, array를 만드는 방법이 달랐다.
그 당시에 map을 활용했었는데, 트레이너의 도움을 받았던지라 역시 지금 다시 풀어보려고 하니 생각이 나질 않아서 활용을 못했다. 본인이 직접 풀어보고 배우고 정리해놓은 것이 더 기억에 오래 남는게 사실이다.

다만, 이번에는 스프레드 문법을 활용해 배열을 재조립(ㅎㅎ)해서 풀어내게 되었다.

스프레드 문법이나 재귀함수나 map이나. 내용이 사실 많기도 하고 머리로 아는거랑 직접 문제를 푸는데 적용하는거랑은 너무 다른 문제라;; 오늘은 피보나치 수열에 한정하여 간단하게 재귀함수만 짚고 넘어가려 한다.

피보나치 넘버 요구사항

피보나치 넘버의 사전적인 정의는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 의미한다.

과제로 받은 피보나치 넘버의 요구사항을 축약하면 아래와 같다.

---

피보나치 넘버를 생성하는 함수 fibonacciNumber() 만들기
fibonacciNumber(1) = 0
fibonacciNumber(2) = 1
fibonacciNumber(3) = 1
fibonacciNumber(4) = 2 ...

---

fibonacciNumber() 구현을 위한 테스트 만들기

만들어 본 테스트는 아래와 같다. 처음에 테스트 이름은 아주 단순하게 'fibonacciNumber' 라고 네이밍했는데, 좀 더 의미있는 네이밍에 대한 피드백을 받아 아래와 같이 수정되었다.

처음부터 아래에 있는 모든 테스트를 다 때려넣고 만들기 시작한 건 아니었다. 위 요구사항 내 예시에 나와있듯이 1을 입력했을 때에는 0이 출력되어야 하고 차례로 2, 3, 4가 입력될 때 1, 1, 2가 출력되어야 했다. 순차적으로 테스트를 하나씩 추가하면서 리팩터링 했고, 마지막에는 유효하지 않은 숫자들(with invalid number)을 입력했을 때에도 원하는 결과가 출력되는지 확인하기 위하여 테스트를 작성하게 되었다.

import { fibonacciNumber } from './fibonacci';

// fibonacciNumber 함수 구현을 위한 test
test('with invalid number', () => {
  expect(fibonacciNumber(0)).toBe(0);
  expect(fibonacciNumber(-3)).toBe(0);
});

test('with valid number', () => {
  expect(fibonacciNumber(1)).toBe(0);
  expect(fibonacciNumber(2)).toBe(1);
  expect(fibonacciNumber(5)).toBe(3);
  expect(fibonacciNumber(10)).toBe(34);
  expect(fibonacciNumber(25)).toBe(46368);
});

피보나치 넘버 만들기

한번에 만들고자 하는 생각을 버렸다.
이 생각을 버리는게 너무나도 중요하고, 아직도 잘 안되는 부분이다.

처음엔 일정부분의 노가다가 필요한 것 같다.
숫자 1, 2, 3을 넣었을 때를 모두 if문으로 만들어 보았다.

테스트를 작성했을 때 구현된 코드가 없다면 당연히 테스트가 통과하지 않을 것이므로(red), 어떻게든 빠르게 테스트를 통과시키고(green), 그 다음 리펙터링을 하는 것. TDD의 기본적인 프로세스이기 때문이다.

export function fibonacciNumber(x) {
  // fibonacciNumber(1) 테스트 통과
  if (x <= 1) {
    return 0;
  }

  // fibonacciNumber(2) 테스트 통과
  if (x === 2) {
    return 1;
  }

  // fibonacciNumber(3) 테스트 통과
  if (x === 3) {
    return 1;
  }

  // fibonacciNumber(4) 테스트 통과
  return 2;
}

위와 같이 코드를 작성했을 때 피보나치넘버 함수에 1, 2, 3, 4를 각각 넣었을 때까지의 테스트는 모두 통과한다.

그럼 이쯤에서 피보나치의 원리를 다시 생각해본다.
=> 그 뒤의 모든 항은 바로 앞 두 항의 합
즉 fibonacciNumber(1 이하의 수) = 0,
fibonacciNumber(2) = 1로 특정하고
fibonacciNumber(3)부터는 아래 공식이 성립하는 것이다.

fibonacciNumber(x) = fibonacciNumber(x - 2 ) + fibonacciNumber(x - 1)

'피보나치'라는 단어만 들었을 때에는 괜시리 어려워보였는데
우선 if문으로 몇가지 케이스를 만들어본 다음 공통적으로 나타나는 패턴을 발견하니 아래와 같이 코드를 정리할 수 있었다.

1 이하의 수를 입력받았을 때에는 0을 반환하도록 임의로 설정했다.

export function fibonacciNumber(x) {
  if (x <= 1) {
    return 0;
  }

  if (x === 2) {
    return 1;
  }

  return fibonacciNumber(x - 1) + fibonacciNumber(x - 2);
}

재귀(recursion)

재귀(再歸, Recursion)의 사전적 정의는 '자신을 정의할 때 자기 자신을 재참조하는 방법'이다.

모던자바스크립트 문서에서도 재귀(recursion)를 함수 내부에서 자기 자신을 호출하는 것을 나타내는 프로그래밍 용어라고 이야기 하고 있다.
위 코드에서도 볼 수 있듯이 fibonacciNumber라는 함수 안에서 자기 자신이 불리는 것을 '재귀'라고 할 수 있다.

재귀함수가 갖추어야 할 두가지 조건이 있다면 아래와 같다.

• 탈출 조건
• 재귀 호출(자기 자신을 재참조하는 것)

위 코드에 주석을 조금 달아보면 이렇게 될 것이다.

export function fibonacciNumber(x) {
  // 탈출 조건
  if (x <= 1) {
    return 0;
  }

  if (x === 2) {
    return 1;
  }
  //

  // 재귀 호출
  return fibonacciNumber(x - 1) + fibonacciNumber(x - 2);
}

재귀함수에 탈출 조건이 없다면 저 안에서 무한히 돌아가는 참사가... 컴퓨터가 "나 좀 제발 죽여줘..."할지도 모르는..ㅎㅎ

여러 곳에서 예시로 제시되는 피보나치 수열, 팩토리얼 결과값 구하기 등이 재귀를 연습하기에 좋은 아주 간단한 문제들이라고 하니 담번엔 factorial값 구하기를 만들어봐야겠다. (이건 모던자바스크립트 문서에도 예시로 주어진다.)

reduce역시 재귀와 직결된다고 하는데 map, reduce, filter, forEach... 뭔가 숙제같이 남겨진 녀석들이라 얼른 익숙해지고, 학습해서 별도로 정리해야지. ㅠㅠ

아직 재귀를 활용하는게 쉽지 않다. 우선 저 패턴을 찾아내는 것 자체가 익숙하지 않고.
결국엔 여러가지 문제를 풀어보면서 익숙해지고 또 '재귀'라는 논리가 멀지 않게 느껴지는게 우선일 것 같다.

다음번 글은 이번에 만든 피보나치 넘버 함수를 가지고 array를 만든 방법에 대해 정리해봐야지. (스프레드 문법, map 활용 2가지 측면)

참고문서

• https://ko.javascript.info/recursion#ref-713