[알고리즘][JS] 재귀 함수

재귀함수란?

자기자신을 호출하는 함수를 의미합니다.
일반적인 함수처럼 입력값을 받고, 그 입력값에 대한 연산을 하면서 결과값을 반환할 수 있습니다.
재귀함수는 함수내에서 자신을 호출하면서 작업을 반복적으로 수행하며,
return keyword 즉,연산을 반복적으로 수행중 원하는 반환값이 나온다면 종료되도록 하는 함수입니다.

자바스크립트에서는 HTML의 DOM트리의 특성인 중첩된 div를 재귀함수를 통해 보다 쉽게 접근 할 수 있습니다.

// 재귀함수를 사용하여 특정 클래스명을 가진 모든 DOM 요소를 찾는 함수
function findElementsByClassname(className, node) {
    node = node || document.body; // 시작 노드가 주어지지 않으면 body를 시작 노드로 사용

    var elements = [];
    if (node.classList.contains(className)) {
        elements.push(node);
    }

    for (var i = 0; i < node.children.length; i++) {
        // 자식 노드에 대해 재귀 호출
        elements = elements.concat(findElementsByClassname(className, node.children[i]));
    }

    return elements;
}

// 예제: 클래스명이 "example-class"인 모든 요소를 찾아 콘솔에 출력
var elements = findElementsByClassname("example-class");
console.log(elements);

이런식의 함수 작성을 통해 원하는 노드를 찾는 재귀함수도 작성이 가능합니다.

스택?

재귀함수와 스택은 매우 밀접한 관계에 있습니다.

스택은 재귀함수가 호출 될 때 마다, 함수의 상태를 호출 스택에 저장합니다.
이 호출 스택은 함수 호출이 중첩될 때 어떤 함수가 호출되는지,
각 호출에서 변수값은 어떤게 사용되는지 추적하는데 사용됩니다.

재귀함수는 자기 자신을 호출하며 문제를 수행합니다.
이 호출들은 스택에 쌓이게 되며, 호출의 깊이가 깊을수록 스택에 많은 프레임이 쌓이며,
이것은 스택오버플로우가 발생할 수 있는 위험이 있습니다.

아래는 스택에 대한 간단한 예시입니다.

function takeShower(){
    return "샤워하기~"
}

function eatBreakfast(){
    let meal = cookFood()
    return `오늘의 아침은 ${meal}`
}

function cookFood(){
     let items = ["오트밀","계란","프로틴 음료"]
    return items[Math.floor(Math.random()*items.length)];
}

function wakeUp(){
     takeShower()
      eatBreakfast()
      console.log("일하러 가자~~")
}

wakeUp()

wakeUp 함수를 실행시 3개의 구문이 실행되며
wakeUp 함수가 스택이라고 볼 수 있습니다. (2개의 함수 및 하나의 console.log를 실행하기 때문.)

재귀함수 예시

재귀함수를 사용한 예시입니다.

function countDown(num){
    if(num <= 0){
      console.log("done");
      return;
    }
      console.log(num);
      num--;
      countDown(num);
}

이함수는 num의 적힌 숫자를 기준으로 내림차순으로 num <= 0 의 조건을 만족하는 1까지 출력합니다
ex) 5,4,3,2,1

함수의 마지막에 countDown함수 본인을 다시 출력합니다.
그렇다면 스택에는 countDown(5) ... countDown(1)까지 쌓일것입니다.

이 함수를 읽으며 이해하는 과정이 필요 할 것 같습니다.

문제

숫자를 받아 해당 숫자의 계승(팩토리얼)을 반환하는 팩토리얼 함수를 작성하시오.
팩토리얼은 정수와 그 아래의 모든 정수의 곱입니다.
예를 들어, 4 팩토리얼 (4!)은 4 * 3 * 2 * 1 = 2입니다. 팩토리얼 0(0!)은 항상 1입니다.

이 문제를 풀고나서 구글에 js 재귀함수 팩토리얼 검색해서 풀이를 한번 보시는 것을 추천드립니다.