알고리즘 - 재귀

📍 재귀 함수란?

 

함수가 자기자신을 스스로 호출하는 구조로 만들어진 함수이다.

 

함수가 본인 스스로를 호출하는 것을 재귀적으로 호출한다고 한다.

 

function countdown(n) {
  if (n > 0) {
    console.log(n);
    countdown(n - 1);
  }
}

countdown(4)

//출력
4
3
2
1

위 코드에서 countdown 함수는 재귀 함수이다. 함수 내부에서 자기 자신을 호출하고 있는 것을 볼 수 있다.

 

함수 파라미터로 숫자4를 입력값으로 주면 4, 3, 2, 1을 출력하는 걸 볼 수 있는데 함수 내부에 while문이나 for문 등 반복문이 없지만 재귀 개념을 적용했기 때문에 반복적으로 숫자를 출력할 수 있는걸 볼 수있다.

 

countdown(4) 호출하면 어떤 일이 일어나는지 단계별로 보자.

 

countdown 함수 파라미터에 숫자 4가 전달된다.

 

숫자 4는 0보다 크기 때문에 콘솔에 숫자 4가 출력된다. 그 다음 countdown(n - 1) 이니까 countdown(3) 호출된다.

 

그럼 파라미터에 숫자 3이 전달됩니다. 숫자 3도 0보다 크기 때문에 콘솔에 숫자 3이 출력되고 countdown(2) 호출된다.

 

같은 방식으로 2도 0보다 크기 때문에 콘솔에 숫자 2가 출력되고 countdown(1) 호출된다.

 

1도 0보다 크기 때문에 콘솔에 숫자 1이 출력되고  countdown(0) 호출된다. 

 

파라미터로 0이 입력값으로 들어갔을 때는 0은 0보다 크지 않기 때문에 if문 코드가 실행되지 않고 바로 종료된다.

 

이후 countdown(0)은 countdown(1)에서 호출 되었기 때문에  countdown(1)로 돌아가지만 마지막 줄까지 실행되었기 때문에 종료된다. 

 

그 다음 countdown(2) > countdown(3) > countdown(4)까지 차례대로 종료된다. 결과적으로 4, 3, 2, 1이 순서대로 하나씩 출력되고 countdown(4)에 대한 호출이 끝난다.

 

 

📍 재귀 함수의 원리

 

먼저 팩토리얼이란 ?

자기 자신을 포함하여 1부터 자기 자신까지 모두 곱하는 것을 말한다. 기호는 숫자 뒤에 !를 붙인다.

예를 들어, 5!는 5 * 4 * 3 * 2 * 1 = 120 이다. 

 

아래 코드는 재귀적으로 구현된 팩토리얼 함수이다.

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

 

재귀 함수의 구현 핵심은 하위 문제를 파악해야한다.

 

예를 들어, 5!를 계산한다고 해보자.

 

5! = 1 * 2 * 3 * 4 * 5   // 5! = 4! * 5로 계산할 수 있다. 4!의 값을 구할 수 있다면 4!를 이용해서 5!를 구할 수 있다. 이렇듯 4!은 5!의 하위문제라고 할 수 있다.

 

4! = 1 * 2 * 3 * 4   // 4! = 3! * 4로 계산할 수 있다. 여기서 3!는 4!의 하위 문제이다.

 

3! = 1 * 2 * 3    // 3! =  2! * 3

 

2! = 1 * 2   // 2! = 1! * 2

 

1! = 1   // 1! 까지 가면 더이상 하위 문제로 나눌 수 없다. 1!는 값이 1이라는 걸 아니까 1!의 1의 값을 대입하면서 위로 올라가면 5! = 120이라는 것을 알 수 있다.

 

여기서 1!처럼 바로 답을 알 수 있는 것을 베이스 케이스라고 하여, 2!, 3!, 4!, 5! 같이 하위 문제로 더 쪼갤 수 있는 것은 재귀 케이스라고 한다.

 

즉 여기 팩토리얼 함수에서 if(n === 1) 때는 베이스 케이스, n > 1는 재귀 케이스라고 볼 수 있다.

 

 

재귀 함수의 핵심원리

• 하위 문제

• 재귀 케이스

• 베이스 케이스