Recursion Intro

October 9th 2018

Recursion은 Function이 자신을 함수 내부에서 호출하게 함으로써 문제를 해결하는 방법입니다. Recursion을 사용하면 소량의 처리만 완료하고 나머지 작업을 재귀 호출한 함수에 위임할 수 있으며, 코드도 좀 더 직관적으로 작성할 수 있습니다.

일반적으로 Recurtion에는 Base condition이 존재하고, 이 base 덕분에 함수가 무한으로 호출되는 것을 막습니다. Wrapper 함수 안에서 recursion을 구현하고, 새로운 recursive function을 호출할 때 argument accumulator를 전달하는 방법도 많이 사용합니다.

아래의 기본적인 recursive 코드를 작성해 재귀 함수에 익숙해지도록 합시다! 먼저 간단한 For loop를 Recursion으로 변경하는 것부터 확인해 보겠습니다.

// Write a function that loops through the numbers n down to 0. If you haven't done so try using a while loop to do this.
function countDown(n) {
  while (n > 0) {
    console.log(n);
    n--;
  }
}
// ↓↓
function recursiveCountDown(n) {
  if (n > 0) {
    console.log(n);
    return recursiveCountDown(--n);
  }
}

아래의 코드는 밑과 지수를 인자로 전달 받으면 거듭제곱의 값을 반환하는 함수를 작성하는 코드입니다. 먼저 while loop로 작성한 후 recursive로 변경해 보았습니다.

function exponent(base, expo) {
  let value = base;

  while (expo > 1) {
    value *= base;
    expo--;
  }

  return value;
};

// ↓↓

function recursiveExponent(base, expo) {
  if(expo === 1) {
    return base;
  } else {
    return base * recursiveExponent(base, --expo);
  }
};

다음은 곱셉입니다. 배열과 숫자를 인자로 받으면, 각 배열의 요소에 전달 받은 수를 곱한 값을 가진 새로운 배열을 반환하는 문제입니다.

function recursiveMultiplier(arr, num) {
  if(arr.length === 1) {
    return [arr[0] * num];
  } else {
    return [arr[0] * num].concat(recursiveMultiplier(arr.slice(1), num));
  }
};

저는 위와 같이 인자로 받은 배열의 길이를 재귀가 멈추는 조건으로 설정했습니다. recursion을 구현할 때는 함수가 무한으로 호출되는 것을 방지하기 위해 재귀가 멈추는 조건을 설정하는 것이 중요합니다.

저는 더 나은 방법은 없는지 궁금해서, 일단 제가 풀고 난 후 다른 풀이 방법을 참조하는 것을 좋아합니다. 아래의 코드는 제가 생각하지 못한 방법으로 풀이를 해서 가져와 봤습니다.

function recursiveMultiplier(arr, num) {
  if (arr.length === 0) {
    return;
  }

  const el = arr.pop();

  recursiveMultiplier(arr, num);

  arr.push(el * num);

  return arr;
}

위의 코드는 인자로 받은 arr 자체를 계속 수정해서 구현이 가능했습니다. Object, Array는 참조 값을 가지고 있으므로 recursive function이 호출될 때마다 새로 생기는 call stack에서 arr를 수정해도, 이전에 호출된 call stack의 arr의 값에도 영향을 미칩니다.

아래는 배열을 인자로 받으면 reverse 하는 함수를 재귀적으로 구현하는 문제입니다.

function recursiveReverse(arr) {
  if (arr.length === 1) {
    return arr;
  } else {
    return [arr.pop()].concat(recursiveReverse(arr));
  }
}

위 recursiveMultiplier와 유사하게 진행한 코드입니다. 생각의 틀을 조금씩 넓혀봅시다! :)

function recursiveReverse(arr) {
  if (arr.length === 0) {
    return;
  }

  const lastEl = arr.pop();

  recursiveReverse(arr);

  arr.unshift(lastEl);

  return arr;
}

마지막으로 하나 더..

function recursiveReverse(arr) {
  const reversedArr = [];

  const addItems = inOrderArr => {
    if (inOrderArr.length > 0) {
      reversedArr.push(inOrderArr.pop());
      addItems(arr);
    }
  };

  addItems(arr);
  return reversedArr;
}

Handmade with .