TIL [재귀 함수]

재귀 함수 (Recursive Function)

재귀 함수는 함수가 자기 자신을 멈출 때 까지 호출하는 함수이다. 그리고 이러한 기술을 '재귀 (recursion)'이라고 한다. 만약 recures( )라는 함수가 있다고 가정해보자.

function recurse() {
        .
        .
        .
    recurse(); 
}

재귀 함수의 특징

1. 재귀 함수는 항상 반복을 멈추는 조건문이 있어야 한다. 그렇지 않으면 그 함수는 무기한으로 반복을 할 것이다.

function recurse() {
    if(condition) {
    // 반복을 멈추게 하는 조건문이 꼭 필요하다.
        
    } else {
        recurse();
    }
}

function countDown(num){
    for (let i = num; i >= 1; i--){ // 이게 반복을 멈추게 하는 조건문인 셈
        console.log(i);
    }
}

이처럼 for문이나 while문도 항상 어디까지 반복을 하는지 그 조건을 달아주기 때문에 무한 반복을 하지않고 목적 달성 시 알아서 멈추는 것이다. 이렇게 재귀 함수와 반복문은 닮은 점이 많다.

2. 재귀 함수는 보통 큰 문제들을 작은 문제들로 쪼개는데 쓰인다. Binary trees나 graphs, algorithms등 앞으로 배울 데이터의 구조에 많이 쓰인다.

재귀 함수의 예제

1. 재귀 함수를 이용하여 숫자를 3에서 부터 1까지 세는 예제

// 수도 코드
// 1. 우선 함수에 숫자3을 인자로 넣어준다.
// 2. 3을 보여준다.
// 3. 함수에 숫자 2를 인자로 넣어준다.
// 4. 2를 보여준다.
// 5. 함수에 숫자 1을 인자로 넣어준다.
// 6. 1을 보여준다.

function countDown(fromNumber) {
    console.log(fromNumber);
    countDown(fromNumber-1);
}
countDown(3);

하지만 지금 완성한 코드는 1에서 멈추는 것이 아니라 무한 반복을 할 것이다. 조건문을 달아주지 않았기 때문이다.

function countDown(fromNumber) {
    console.log(fromNumber);

    let nextNumber = fromNumber - 1;

    if (nextNumber > 0) { // 반복을 멈추는 조건문
        countDown(nextNumber);
    }
}

countDown(3);

이번에는 조건문을 달아주었다. 이제 숫자가 0이상 일때만 반복할 것이다.

2. 수를 입력받아 n-factorial(n!) 값을 리턴하는 예제

function factorial(num) {
  // 1. num을 받는다
  // 2. num을 num * (num-1) * (num-2) * ...(num - (num-1))
  if (num <= 1) return 1; // 브레이크 역할 num <= 1 이면 1을 리턴하고 멈춘다
  return num * factorial(num - 1); // 결과값
}

1번 예제와는 다르게 어떤 값을 축적해야 하는 경우 이렇게 return에 축적할 값 (num)과 반복할 재귀 함수 (factorial(num - 1))가 들어간다.

자료 출처:
https://www.javascripttutorial.net/javascript-recursive-function/