[additional] 꼬리재귀

leejaeseung commented 1 year ago

연관 챕터

7장 - 함수형 최적화

조사 내용

이후에 꼬리재귀라는 내용이 나옵니다.

꼬리재귀란?

재귀로 작성한 코드를 컴파일 시점에 반복문으로 변환하여 반복문으로 작성한 코드와 동일한 효율을 낼 수 있다. <- 컴파일러가 지원해 줘야 함. (JS 는 ES6 부터 지원)

3장에 map, reduce, filter 가 나오는데 꼬리재귀로 어떻게 구현해 볼 수 있을지 고민해보는 것도 좋을 듯.

leejaeseung commented 1 year ago

꼬리재귀 최적화는 검색해보면 너무 많이 나오기 때문에 간단히 요약만 해본다.

아래 코드는 꼬리재귀가 아니다.

function recursion(n) {
  if (n === 0) {
    return 0;
  }

  return n + recursion(n - 1);
}

return n + recursion(n - 1); 구문 때문에 꼬리재귀가 아니게 된다. n 을 함수 스택에 저장해두어야 이후에 함수가 반환될 때 처리할 수 있기 때문.

따라서, 꼬리재귀로 구현된 함수는 return 문에서 항상 함수 자신만을 호출한다. (혹은 함수의 종결 값)

function recursion(n, total=0) {
  if (n === 0) {
    return total;  // 마지막까지 합산된 결과 값을 반환
  }

  return recursion(n - 1, total + n);  // 현재 함수의 계산 값 : total + n
}

꼬리재귀의 패턴은 사실 단순하다. 현재 함수의 계산 결과를 다음 함수 호출에 넘겨주고, 마지막엔 그걸 반환해주면 된다.

반복문에서 하나의 변수에 값을 계속 더해가는 걸 파라미터로 대신한다고 보면 된다.

leejaeseung commented 1 year ago

map 함수를 조잡하게나마 꼬리재귀로 구현해 보았다.

function MyList(...arg: number[]) {
  function get(index: number): number {
    return arg[index]
  }

  function _map<T>(cb: (param: number) => T, index: number = 0, acc: T[] = []): T[] {
    if (index >= arg.length) return acc
    return _map(cb, index + 1, acc.concat(cb(arg[index]))) // 여기가 중요!
  }

  function map<T>(cb: (param: number) => T) {
    return _map(cb)
  }

  return {
    get,
    map,
  }
}

const numberList = MyList(1, 2, 3)

const doubledList = numberList.map((param) => {
  return param * 2
})

const stringList = numberList.map((param) => {
  return "I'm String : " + param
})

console.log(doubledList) // [ 2, 4, 6 ]
console.log(stringList) // [ "I'm String : 1", "I'm String : 2", "I'm String : 3" ]

horizontal-library / functional-programming-in-javascript