재귀 함수 (Recursive Function)

재귀함수(Recursive Function)는 자기 자신을 호출하는 함수를 의미한다.

정수 1부터 n까지를 출력하는 countFunc 만들기

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

parameter로 7을 넘겨서 함수를 실행해보면,

7, 6, 5, 4, 3, 2, 1이 출력된다.

코드 안에서는 반복문이 하나도 없는데 어떻게 실행될까?
코드의 실행순서를 하나하나씩 살펴보면

//countFunc(7)
function countFunc(7) {
  if(7>0) {
    console.log(7);
    countFunc(7-1); //6
  }
}

//countFunc(6)
function countFunc(6) {
  if(6>0) {
    console.log(6);
    countFunc(6-1); //5
  }
}

//countFunc(5)
function countFunc(5) {
  if(5>0) {
    console.log(5);
    countFunc(5-1); //4
  }
}

//countFunc(4)
function countFunc(4) {
  if(4>0) {
    console.log(4);
    countFunc(4-1); //3
  }
}

//countFunc(3)
function countFunc(3) {
  if(3>0) {
    console.log(3);
    countFunc(3-1); //2
  }
}

//countFunc(2)
function countFunc(2) {
  if(2>0) {
    console.log(2);
    countFunc(2-1); //1
  }
}

//countFunc(1)
function countFunc(1) {
  if(1>0) {
    console.log(1);
    countFunc(1-1); //0
  }
}


//countFunc(0)
function countFunc(0) {
  if(0>0) { //false
    console.log(0);
    countFunc(0-1);
  }
}

countFunc(0)이 끝남 --> countFunc(1)이 끝남 --> countFunc(2)이 끝남 --> countFunc3)이 끝남 --> countFunc(4)이 끝남 --> countFunc(5)이 끝남 --> countFunc(6)이 끝남 --> countFunc(7)이 끝남 --> 프로그램이 끝난다.

factorial을 통해 재귀함수 이해하기

팩토리얼은 n! = 1 x 2 x 3 x ... x (n-1) x n
까지의 곱을 나타낸다.

1부터 자연수 n까지의 곱을 말한다.

0!은 1이고, 1!로 1이다.

0! = 1
1! = 1
2! = 1 x 2
n! = 1 x 2 x 3 x ... x (n-1) x n

재귀적으로 문제를 해결, 푸는 법은 같은 동작을 하는 형태에서 더 작은 문제를 해결해서 부분적인 문제를 알아내야 되고, 그걸 해결하고 다시 더 큰 문제를 해결해야 된다.

5!을 놓고 봤을 때 5! = 5 x 4 x 3 x 2 x 1인데 여기서 보면
4 x 3 x 2 x 1 --> 이 부분은 4!이고,
3 x 2 x 1 --> 이부분은 3!
2 x 1 --> 2!
1 --> 1! 인것을 확인할 수 있다.

그렇다면, n! (n 팩토리얼)은
n = 0 인 경우와 n > 0 인 경우로 나눌 수 있지 않을까?


재귀함수는 재귀를 끝낼 수 있는 조건이 필요하다.
그래서 재귀를 끝내는 값에 0아니면 1일 때를 기준으로 줘서 재귀함수를 끝낼 수 있게 조건을 줘야 된다.

n = 0인 경우 n! = 1 (base case)
n > 0인 경우 n! = (n - 1)! x n (recursive case)

base case : 문제가 작아서 충분히 잡을 수 있는 경우, 따로 해결해야 될 부분 문제가 없는 경우 사용한다.

recursive case만 있으면 재귀적으로 계속 함수를 호출하고 끝나질 않으니 base case가 반드시 필요하다.

아래의 함수는 팩토리얼을 계산하는 함수이다.

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

factorualFunc(5)를 넣어서 함수를 실행시켜 보았을 때
1 x 2 x 3 x 4 x 5가 계산되어서 120이 나오는 것을 확인할 수 있다.