재귀 알고리즘에 대하여

재귀 함수란 자신을 다시 호출하여 동작하는 원리이다.

간단한 예시로 자연수의 합을 구하는 것으로 재귀 알고리즘을 적용해보자

자연수의 합 구하기

sum = (n) => {
  if (n <= 1) {
    return n
}
  else {return n + sum(n-1)}
}

여기서 n이 1보다 작거나 같다는 조건은 재귀 호출의 종결 조건과도 같다.
재귀 알고리즘은 반드시 종결조건이 필요하다 종결조건이 없거나 잘못 주어진 경우 루프가 무한으로 돌아 함수값이 반환되지 않는다.
종결 조건 밑에는 그 외의 조건으로 함수의 로직을 구현한다.
합을 구하는 경우에는 자신과 자신-1의 합을 계속 구하는 식으로 진행한다.
10을 인자로 넣으면 10+sum(9)이고 sum(9)는 1부터 9까지 더하는 함수이다.
sum(9)도 9+sum(8)이고 이러한 방법이 반복된다.

파보나치 수열의 합 구하기

let pibo = (x) => {
  if (x<2) { return x }
  else { return pibo(x-1) + pibo(x-2)}
}

피보나치 수열도 재귀 알고리즘을 통해 만들 수 있다.
피보나치 수열의 중요한 점은 재귀를 2번 사용하였다는 것이다.
Pibo(x-1)과 pibo(x-2)를 사용하여 피보나치 함수를 만들었고 종결 조건으로 x<2인 조건을 걸어주었다.

팩토리얼 문제 풀기

const factorial = n => {
  if (n==0 || n==1)
  {return 1}
  else {return n*factorial(n-1)}
}

종결 조건을 n이 0이거나 1인경우로 설정한다. 원래는 n=1이면 팩토리얼이 종결되지만 0!인 경우도 생각해주어야하기 때문에 n=1 or n=0으로 설정하였다.
else에는 factorial의 logic을 구현해준다.