[FP] 재귀함수

재귀적으로 사고하기

재귀란 ?

: 재귀(Recursion)란 주어진 문제를 자기 반복적인 문제들로 잘게 분해한 다음에 이들을 다시 조합해서 원래 문제의 정답을 찾는 기법이다. 재귀의 주된 구성 요소는

• 기저 케이스(=종료 조건)
• 재귀 케이스
  이다.

재귀적으로 생각하기

: 너무 복잡하게 접근하기보다는 딱 떠오르는 것에 비유를 해보면 reduce 의 로직이 재귀적 사고 방식을 적용한 것이라고 할 수 있다. 자기 반복적인 로직을 순차적으로 적용해 가면서 결괏값을 도출하는 reduce를 통해 재귀적 사고를 이해해보자.

덧셈을 재귀적으로 사고해보자.

: 덧셈을 예시로 이를 이해해보자.

const sumData = [1, 2, 3, 4, 5, 6, 7, 8, 9];

const sum = (arr) => {
	if(arr.length === 0) return 0;
    
    `return arr[0] + sum(arr.slice(1));
}

console.log(sum(sumData)); // 45

위와 같이 재귀적으로 함수를 짜서 덧셈을 할 수 있다. 이걸 reduce로 똑같이 만들어보면,

const sumData = [1, 2, 3, 4, 5, 6, 7, 8, 9];

const reduceSum = (accum, now) => {
  return now + accum;
};

const sumResult = sumData.reduce(reduceSum);
console.log(sumResult); // 45

위와 같이 된다. 이 때, now + accum 이부분과 return arr[0] + sum(arr.slice(1)); 이부분이 자기 반복적인 로직이라고 할 수 있고, 재귀함수와 reduce 모두 자기 반복적인 로직을 통해 결괏값을 도출하고 있다.

꼭 재귀를 써야하나?

: 물론 재귀 함수를 쓰거나 앞선 reduce를 쓰는게 필수는 아니다. 하지만 함수형 프로그래밍을 한다는 관점에서는 재귀적으로 사고하는게 권장된다 정도로 생각해보자. 실제로 함수형 프로그래밍 전용(?) 언어에서는 루프문이 없다고 한다. 즉, 재귀를 강제적으로 써야한다고 한다. 하지만 JS에서는 강제가 아니기에 꼭 쓸 필요는 없으니 이런 개념에 대해 알고 가는 정도로 하자.

재귀를 쓰면 이득이 있나?

: 하지만, 함수형 프로그래밍이니까 재귀를 써야지! 라고 넘어가기엔 좀 찝찝한게 많다. 만약 이게 일반 루프문 보다 효율이 떨어진다면 정말 굳이 써야할 이유가 없기 때문이다. 실제로 재귀함수를 JS를 통해서 구현해서 쓰면 이점은 특별히 없지만 오히려 위험 요소가 있다고 한다. 그건 Stack Overflow이다. JS 내부 로직을 배웠다면, 함수를 하나 실행할 때마다 콜스택에 실행 컨텍스트가 쌓인다는 것을 알고 있을 것이다. 이 때 재귀함수를 쓰게 되면 스택에 계속해서 컨텍스트가 쌓이게 되는데, 이게 JS 의 Limit을 넘게 되면 Stack overflow가 발생한다(=error). 재귀함수는 이런 스택 오버 플로우의 위험도 갖고 있기 때문에 재귀함수를 쓰려면 대비를 따로 해줘야한다.

: TCO(Tail Call Optimization) 가 ES6 스펙에 명시돼 있으나 Safari의 Strict 모드에서만 지원하기 때문에 사실상 못쓴다고 할 수 있다. 꼬리 호출 최적화란 앞서 말한 스택오버 플로우를 피하기 위해 재귀함수를 단계별로 호출할 때마다 스택을 쌓는게 아니라 이전 스택을 재사용하는 형태로 하기 때문에 스택이 넘칠일이 없게 만드는 최적화이다. 하지만, 앞서 말한 것처럼 꼬리 호출 형태로 개발을 하더라도 예를 들어, 구글 크롬에서는 이를 지원하지 않기 때문에(디버깅, 함수 추적 등의 어려움이 가장 큰 이유 같다) 의미가 없는 상태이다.

그러면 재귀 함수는 사실상 안쓰는게 낫나?

: 사실 나는 재귀함수를 코딩테스트 때 DFS, BFS 이런 로직을 짤 때나 써보고(혹은 완전 탐색) 실제 프로젝트를 할 때는 앞서 말한 위험성 때문에 써본적이 없다. 하지만, 함수형 프로그래밍을 좀 더 제대로 체험(?) 해보고 싶고, 이를 위해 재귀함수를 꼭 쓰고 싶다면, 실상은 루프문을 쓰되 재귀함수처럼 코딩하는 방법이 있다. 이렇게 하면 뭔 짬뽕인가..? 이유가 있나?? 할 수 있지만, 재귀적 사고를 하면서도 재귀함수 사용에 따른 위험성을 방지할 수 있다는 장점이 있다.

function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result();
    }
    return result;
  };
}

function factorial(n, acc = 1) {
  if (n <= 1) return acc;
  return () => factorial(n - 1, n * acc);
}

const trampolinedFactorial = trampoline(factorial);

console.log(trampolinedFactorial(5));  // 120
console.log(trampolinedFactorial(10000));  // Doesn't cause stack overflow

위와 같이 결론적으로는 루프문을 통해 반복을 하되, 함수를 짤 때 사고 자체는 재귀적 사고로 로직을 짜게 하는거다. 이런식으로 우회적인 재귀적 코딩을 할 수 있다.

재귀를 이용한 DFS 로직 예시

: Object.freeze를 재귀 로직을 사용해 특정 객체에 중첩된 모든 객체에 적용하는걸 했었는데, 그것처럼 Tree 자료구조를 console에 찍을 때 DFS 로직과 재귀적 사고를 이용해 Node 내 데이터를 출력하는 예시를 개발해봤다. 데이터에서 사용한 객체는 이전 블로깅에서 사용했던 Person, Student 객체이다.

class Node {
  constructor(val) {
    this._val = val;
    this._parent = null;
    this._children = [];
  }

  isRoot() {
    return this._parent === null;
  }

  get children() {
    return this._children;
  }

  hasChildren() {
    return this._children.length > 0;
  }

  get value() {
    return this._val;
  }

  set value(val) {
    this._val = val;
  }

  append(child) {
    child._parent = this;
    this._children.push(child);
    return this;
  }

  toString() {
    return `Node (val: ${this._val}, children: ${this._children.length})`;
  }
}

class Tree {
  constructor(root) {
    this._root = root;
  }

  static map(node, fn, tree = null) {
    node.value = fn(node.value);
    if (tree === null) {
      tree = new Tree(node);
    }

    if (node.hasChildren()) {
      _.map(node.children, function (child) {
        Tree.map(child, fn, tree);
      });
    }

    return tree;
  }

  static read(node, fn, tree = null) {
    console.log(fn(node.value));
    if (tree === null) {
      tree = new Tree(node);
    }

    if (node.hasChildren()) {
      _.forEach(node.children, function (child) {
        Tree.read(child, fn, tree);
      });
    }
  }
  get root() {
    return this._root;
  }
}

const s1Node = new Node(s1);
const s2Node = new Node(s2);
const s3Node = new Node(s3);
const s4Node = new Node(s4);
const s5Node = new Node(s5);
const s6Node = new Node(s6);
const s7Node = new Node(s7);
const s8Node = new Node(s8);
const s9Node = new Node(s9);

s1Node.append(s3Node).append(s5Node).append(s9Node);
s9Node.append(s2Node).append(s4Node);
s3Node.append(s6Node).append(s7Node);
s5Node.append(s8Node);

Tree.read(s1Node, (p) => p.lastname);

// DFS
// Haskell (S1)
// John (S3)
// Andy (S6)
// Jihoon (S7)
// Yongki (S5)
// Jinn (S8)
// June (S9)
// Barkley (S2)
// Alonzo (S4)

마무리

: 나는 일단 다음 프로젝트를 할 때 앞서 말한 trampoline 을 사용해서 재귀적 사고로 루프 로직을 짜는걸 해볼 생각이다. 옛날에 하노이의 탑 같은 문제를 풀 때나 해본 재귀함수를 오랜만에 공부해봐서 좋았다.