재귀함수 2부 (재귀, 꼬리재귀, 반복문 비교)

1부터 n까지의 합

반복문

const iterator = (n) => {
  let result = 0;
  for (let i = 1; i <= n; i++) {
    result = result + i;
  }
  return result;
};

간단하다. result라는 변수를 생성후 각 수마다 result 값에 계속 더해주면 된다.

 

 

재귀

const recursion = (n) => {
  if (n === 0) {
    return 0;
  }
  return n + recursion(n - 1);
};

먼저 조건문으로 base case를 만들어준후 recursive case로 현재 받은 값과 재귀를 통해 받을값을 계속해서 더해준다.

 

 

꼬리재귀

const tailRecursion = (n, a = 0) => {
  if (n === 0) {
    return a;
  }
  return tailRecursion(n - 1, n + a);
};

base case는 재귀와 같다. recursive case로 자신의 함수를 부른후 첫번째인자는 반복수와 input값이 되고 두번째인자가 반복되는 함수들의 결과값으로 연산된다.

 

문자열 뒤집기

반복문

const iterator = (string) => {
  let result = "";
  for (let i = 0; i < string.length; i++) {
    result = string[i] + result;
  }
  return result;
};

반복문의 경우 결과값에 문자열의 첫번째 문자부터 순차대로 '앞쪽으로' 삽입해주면된다.

 

 

재귀

const recursion = (string) => {
  if (!string) {
    return "";
  }
  return recursion(string.slice(1)) + string[0];
};

base case 설정후 .slice를 이용, 첫문자부터 하나씩 제거하며 함수호출, 그리고 받는 리턴값들에 첫문자를 더해준다.

 

 

꼬리재귀

const tailRecursion = (string, result = "") => {
  if (!string) {
    return result;
  }
  return tailRecursion(string.slice(1), string[0] + result);
};

.slice를 이용하여 첫문자부터 하나씩 제거하고 제거된 문자열은 그대로 result에 더해주며 계속해서 호출, 넘겨받는 string 인자가 비어있다면 여지껏 더해진 result만을 리턴한다.

 

피보나치 수열

반복문

const iterator = (n) => {
  let fib1 = 0;
  let fib2 = 1;
  let assistant = 0;
  for (let i = 1; i < n; i++) {
    assistant = fib2 + fib1;
    fib1 = fib2;
    fib2 = assistant;
  }
  return fib1;
};

함수를 호출하면 n번째의 수열값을 반환한다.

피보나치 수열의 첫번째값과 두번째값인 0과 1을 초기 변수로 주고 반복수로는 n값으로 반복문을 작성

변수 assistant를 이용하여  수열의 첫번째값과 두번째값을 합한값을 저장 후 수열의 두번째값을 첫번째값으로, 서로 합한 값을 두번째값으로 건내준다. 그렇게 n번의 수를 반복한후 마지막 합의 값을 리턴.

 

 

재귀

const recursiion = (n) => {
  if (n <= 1) {
    return 0;
  }
  if (n === 2) {
    return 1;
  }
  return recursiion(n - 1) + recursiion(n - 2);
};

피보나치수열의 첫번째값은 0, 두번째 세번째값은 1이된다. 그러므로 반복문을 이용하여 초기값들을 base case로 정의해주어야한다. 

위의 코드는 n이 1로 들어오는경우 즉 첫번째 수열값을 구하는경우 0을 리턴해준고 두번째 수열값을 구하는경우 피보나치수열의 두번째값인 1을 리턴해준다. 수열의 3번째값 즉 n값을 3으로 받아주면 자연스레 수열의 첫번째값 0과 두번째값 1을 더해 1을 리턴하게된다.

만약 4번째 수열값 즉 n값을 4로 받아주면 2번째값인 1은 바로 리턴이되고 3번째값은 위의 순서로통해 1이 리턴되므로 최종적으로 2를 반환한다.

5번째, 6번째 등 이후의 수열값들또한 마찬가지로 진행됨

 

 

꼬리재귀

const tailRecursion = (n, fib1 = 0, fib2 = 1) => {
  if (n <= 1) {
    return fib1;
  }
  if (n === 2) {
    return fib2;
  }
  let assistant = fib2 + fib1;
  fib1 = fib2;
  fib2 = assistant;
  return tailRecursion(n - 1, fib1, fib2);
};

여기에서도 n값은 계속해서 리턴값으로 n-1이 되므로 n-1값만큼 함수가 반복되어 호출된다. 

fib1과 fib2를 수열의 첫번째값과 두번째값인 0과 1로 설정해준다.

처음 함수가 호출되면 수열의 첫번째, 두번째값인 0과 1이 합해지고 fib2에 저장, 두번째수열값인 1을 fib1으로 전달후 n-1을 하여 반복수를 낮춘뒤 다시 함수를 호출해준다. 그럼 이전에 연산한 값들을 넘겨받아 그값들을 반복하여 실행, 이후 n값이 2가됫을때 함수호출을 멈추고 여지껏 연산한 값인 fib2를 반환한다.

 

마무리

반복문, 재귀, 꼬리재귀를 비교해서 작성해보니 몇가지 느낀점들이 있었다.

 

첫번째, 반복문을 작성할때는 기존에 해오던것처럼 첫번째 연산부터 접근을 한뒤 반복수와 반복 제약을 설정해주었던 것과 달리 재귀와 꼬리재귀의경우 마지막 연산부터 접근을 해야 이해하기가 쉬웟다. 예를 들면 base case로 마지막 연산의 결과를 도출한뒤 그 결과값을 바탕으로 마지막 이전의 연산을 recursive case로 설정해주는 방식으로 접근을 했더니 더 이해하기 쉬웠다.

 

두번째, 꼬리재귀의 경우 재귀와 반복문을 합친것처럼 느껴젓다. 

재귀와 마찬가지로 마지막연산부터 접근을 하고 반복문이 반복수와 반복제약을 걸고 결과값을 따로 저장하듯이 재귀함수도 그 값들을 인자로써 자신의 함수로 보낸다는 것이다.

 

마지막으로, 3가지를 비교해 봤을때 재귀의경우 가독성이 제일 좋긴 했지만 스택오버플로우가 걱정되었다. 예를들어 재귀는 피보나치수열의 3만번째 값을구할경우 3만개의 스택이 쌓이게 되지만 꼬리재귀는 함수를 3만번을 호출하더라도 스택이 하나씩만 쌓이게된다. 반복문의 경우 한번의 함수 호출후 3만번의 반복연산이 되므로 반복되는 연산의 수가 많을수록 for문이 제일 효율적일것 같았다.