[JavaScript] Recursion (재귀)

코드 반복 작성만이 익숙해지는 길인가, 좀처럼 익숙해지지 않고 있는 애증의 재귀 함수. 

오늘은 Recursion 재귀에 대해 정리해 본다.

---

Recursion 이란?

함수는 자신도 호출할 수 있는데, 함수 안에서 자기 자신을 다시 호출하는 프로그래밍 패턴을 말하며 '재귀 함수'라고 한다.

• 재귀 함수를 사용할 때에는 반드시 재귀 함수를 끝내는 종료 조건(초기화)이 필요하다.
• 종료 조건을 설정하지 않으면 시스템이 무한 루프의 재귀함수를 돌아서 메모리 오류가 발생한다.
• 재귀는 같은 종류의 작업을 반복적으로 실행할 때 유용하다.

재귀함수를 쓰는 이유는?

재귀적 알고리즘은 비 재귀적인 알고리즘으로 변환할 수 있다. 재귀는 반복문과 유사하다. 둘 다 동일한 코드를 여러 번 실행하고 종료 조건이 필요하다. 일부 함수는 반복문으로도 구현이 가능하지만 그렇게 변환하기 어려운 경우도 있다. 예를 들어 tree구조에서 모든 노드의 값을 확인하는 경우는 재귀를 사용하는 게 훨씬 쉽고 코드도 직관적이다.

• 알고리즘을 기술한 그대로 코드로 표현할 수 있다. 즉 코드 가독성이 높다.
• 변수 사용을 줄일 수 있다.

재귀함수의 단점

함수가 호출될 때 함수의 입력값, 리턴 값, 돌아갈 위치 값 등이 스택에 저장된다. 이때 함수가 끝나지 않은 채 재귀적인 함수 호출이 계속 이루어지게 되면 스택에도 메모리가 계속 쌓이게 되고 overflow가 발생할 수 있다.

• 재귀적으로 함수를 호출할 때마다 스택을 소비하기 때문에 반복문에 비해 시간이 많이 걸린다.

---

먼저 비교적 간단한 계산식 알고리즘을 예시로 보자.

팩토리얼은 그 수보다 작거나 같은 모든 양의 정수의 곱을 말한다. 팩토리얼을 재귀 함수로 작성하면 아래와 같다.

function factorial(n) {
  if(n > 1) {
    return n * factorial(n - 1);
  }
  return n;
}

factorial(1);  //1
factorial(2);  //2
factorial(3);  //6
factorial(4);  //24
factorial(5);  //120

같은 알고리즘을 반복문으로도 작성할 수 있다.

function factorial(n) {
let total = 1;
  for(let i = n; n >= 1; n--) {
    total = total * n;
  }
  return total;
}

 

이번에는 두 수의 최대공약수를 구하는 알고리즘이다. 아래 코드를 이해하기 위해서는 유클리드 호제법 을 알아야 한다. 

* 유클리드 호제법 : 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 
ex.
- 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
- 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
- 42는 21로 나누어떨어진다. ≫ 최대공약수는 21

function gcd(m, n) {
  if (!n) {
    return m;
  }
  return gcd(n, m % n);
}

gcd(1071, 1029);  //21

 

다른 예제로 중첩된 배열의 뎁스를 제거하는 알고리즘도 재귀함수로 작성할 수 있다.

예를 들어 아래와 같이 중첩된 배열의 결괏값으로 뎁스를 제거한 배열을 얻고 싶다면 reduce()를 활용해볼 수 있다. 값을 리턴할 때 삼항 연산자를 이용해 해당 val의 값이 배열인지를 확인하고 배열이면 재귀 호출, 아니면 기존 배열에 합치도록 한다.

이런 예제는 주어진 배열의 뎁스가 랜덤 한 경우, 반복문으로 작성하기는 어렵다.

function flat(array) {
  return array.reduce(function(acc, val) {
    return acc.concat(Array.isArray(val) ? flat(val) : val);
  }, []);
}

flat([[1, 2], 3, [4, [5, 6, 7]]]);  //[ 1, 2, 3, 4, 5, 6, 7 ]

 

 

반복적인 작업을 하는 알고리즘으로 객체 안에 겹의 객체를 가지고 있는 오브젝트에서 특정한 값이 있는지를 찾는 코드도 예시로 종종 볼 수 있다. 아래 코드는 nestedObject에서 특정 값이 존재하는지의 여부를 true, false로 리턴하는 알고리즘이다.

var nestedObject = {
    data: {
        info: {
            stuff: {
                thing: {
                    moreStuff: {
                        magicNumber: 44,
                        something: 'foo2'
                    }
                }
            }
        }
    }
}

function contains(obj, value){
	for(let key in obj){
		if(typeof obj[key] === 'object'){ 
			return contains(obj[key], value);  //재귀 호출
		}

		if (obj[key] === value){
			return true;
		}
	}
	return false;
}

contains(nestedObject, 44);  // true
contains(nestedObject, 'foo');  // false

 

위와 비슷한 예제로 트리 구조를 재귀 함수로 탐색하는 코드도 생각해볼 수 있다.

let check =  function(tree) {
  let result = [];
  if(tree.children) {
    for (let i = 0; i < tree.children.length; i++) {
      result.push(tree.children[i].value);
      check(tree.children[i])
    }
  }
  return result;
}