[자바스크립트]함수 이야기 5탄 - 재귀 함수와 함수 스택 이해하기.

안녕하세요. 신기한 연구소입니다.

요즘 자바스크립트에 시간을 많이 보내고 있는데요.

보면 볼수록 정말 어메이징 합니다.

빨리 자바스크립트를 능숙하게 다룰 수 있는 날이 오길 기대하며

오늘도 함수 시리즈를 같이 공부해봅니다.

 

재귀 함수를 사용하는 방법

혹시 factorial(팩토리얼) 함수에 대해 들어보셨나요?

알고리즘이나 프로그래밍 예제에서 약방의 감초처럼 등장하는 함수인데요.

n! = n * (n-1) * (n-2) * ... * 1

4! = 4 * 3 * 2 * 1 = 24

이 공식을 함수화 하면 다음과 같습니다.

    function factorial(num) {
      if (num <= 1) return num;
      else return (factorial(num - 1) * num);
    }
    
    var rst = factorial(4);
    
    console.log(rst); //24

위 소스를 보면 특이한 점이 있습니다.

함수 factorial을 선언하고나서 return문에서 자기 자신을 다시 호출하도록 되어 있거든요.

뭔가 무한루프에 빠질듯한 이 상황을 바로 재귀(recursion)이라고 합니다.

자기 자신을 다시 호출한다는 의미입니다.

물론 무한으로 빠지지 않기 위해 조건이 들어가 있습니다.

자바스크립트에서는 함수 자신을 참조하기도 하고 호출할 수도 있다는 의미입니다.

 

함수를 호출하는 방법에 대해 이전 포스팅에서도 확인했었는데요.

한 가지 더 알아보겠습니다.

 

arguments.callee 사용하는 방법

마지막으로 하나 더 arguments.callee가 있습니다.

뭔가 어려워 보이고 낯설어 보이는데요.

현재 범위에서 실행 중인 함수를 의미합니다.

함수 이름이 있거나 변수에 할당되어 있으면 다시 호출하기 편하지만

익명의 함수(이름이 없는)라면 실행 흐름에 따르거나 리턴되어 실행되는 것이 아니고

임의로 다시 실행하고 싶다면 이름이 없기에 호출할 수 없겠지요.

그래서 arguments.callee(지금 실행하고 있는 너!!!)를 사용하면

마치 이름은 없지만 삿대질로 찍어서 익명 함수를 실행할 수 있는 그런 구조로 보시면 되겠네요.

 

다음 예를 보겠습니다.

var arr = [1,2,3];
 
console.log(arr.map(function (n) {
     return !(n > 1) ? 1 : arguments.callee(n - 1) * n;
}));

map을 실행할 때 익명 함수를 구현했습니다. function (n)

return에서 이 익명함수를 재귀 호출을 해야 하는데

이름이 없어서 불가능해 보이지만

arguments.callee(n - 1)로 호출이 가능합니다.

지금 실행중인 함수를 호출해줘~~ 라는 의미로 보면 되겠네요.

(어쨌든 함수 이름을 명시해서 가급적 arguments.callee를 지양하는 것이 좋다고 합니다.)

 

다시 말해 함수가 구현부 블록문 내에서 자신을 또 호출할 수 있고

이를 재귀함수라고 부릅니다.

무한 루프에 빠질 수도 있다고 했듯이

루프문으로 변환할 수 있고 그 반대로 루프문을 함수로 변환할 수도 있습니다.. (모든 경우는 아닙니다.)

재귀 함수는 함수 내에 자신을 또 호출하기에 

그 호출 시점 뒤의 로직을 거치지 않고 다시 처음으로 이동합니다.

그렇다고 해서 호출 시점 후반부의 로직을 전혀 실행하지 않고 버리지는 않고

재귀 조건이 완료되면 나머지 부분이 호출됩니다.

 

함수스택은 무엇인가요?

그런데 이 부분을 자세히 알고 가야 합니다.

스택을 사용해서 함수를 처리하기 때문입니다.

이것을 바로 함수스택이라고 하는데요.

다음 예를 통해서 함수 스택을 설명해보겠습니다.

function stackSample(n) {
    if (n < 0) {
        return;
    }
    
    console.log('before : ' + n);
    
    // 호출시점 
    stackSample(n - 1);
    // 호출시점 후반
    console.log('after : ' + n);
}
 
stackSample(4);

이 소스를 보면, 우리가 함수 스택을 모른다고 가정하고, 

호출 시점 후반에 있는 after 부분은 절대 실행되지 않을 것으로 판단됩니다.

하지만 자바스크립트에서는 이렇게 재귀 호출을 하면

함수 스택을 사용해서 함수가 재귀 호출될 때마다 

스택에 담아두고 return을 통해 종료가 되면

마지막으로 담았던 함수의 후반부부터 차례로 실행을 하게 됩니다.

그렇기에 5번의 함수 스택이 처리되어서

after는 4, 3, 2, 1, 0 순으로 결과를 출력하게 됩니다.

예상 결괏값은 다음과 같습니다.

before : 4
before : 3
before : 2
before : 1
before : 0
after : 0
after : 1
after : 2
after : 3
after : 4

이런 결과가 나오다니..

신기하네요.

 

지금까지 재귀 함수와 함수 스택에 관한 이야기를 해봤습니다.

함수 스택은 실전에서 잘 활용하세요.