[FE_Bootcamp] 42일차

서버에서 벗어나 간만에 다시 자바스크립트로 돌아왔다

오오 즐거워 오오

1. 재귀함수

재귀함수란, 자기 자신을 계속 호출하는 함수를 말한다.

~~마치 입으로 밥을 먹고 똥을 싸는 해삼과도 같은 함수이다.~~

function func(num){
  console.log(num)
  return func(num-1)
}

다음과 같은 함수가 바로 재귀함수이다.

input으로 num을 받고, num 대신 num-1을 넣은 자기 자신을 return한다.

예를들어, num=5를 입력으로 준다면, return 값은 func(4)가 된다.

func(4)의 return은 다시 func(3)이 되고, func(2)가 되고,..,,.,.의 과정을 거쳐 func(-∞)까지 갈 것이다.

이 함수를 실행하면, 재귀의 종료 조건이 없기 때문에 재귀가 계속해서 일어나는 것을 볼 수 있다.

따라서, 재귀 함수를 실행하기 위해서는 재귀의 종료 조건을 잘 설정해 주는 것이 중요하다.

만약, num이 양수일때만 재귀를 실행한다고 하자.

그렇다면, 재귀의 종료 조건은 'num이 1보다 작을 때'가 된다.

function func(num){
  if(num <= 1){
    return '리턴값은 ' + num
  }
  console.log(num)
  return func(num-1)
}

함수는 리턴값을 반환하면 함수 자체가 즉시 종료되기 때문에, 조건을 설정해준 뒤 원하는 리턴값을 넣어주면 된다.

위 코드같은 경우, num이 1보다 작거나 같아지면 num을 리턴한다.

func(1)의 리턴값은 1인데, func(1) 자체가 func(2)의 리턴값이다. 따라서 func(2)의 리턴값도 1.

func(2)는 또 func(3)의 리턴이므로 func(3)의 리턴도 1.

같은 과정을 반복하면, 결국 func(5)의 리턴 역시 1이 된다.

이렇게만 하면 알기 어려우니, 대표적인 예제를 들어보겠다.

우리가 흔히 아는 '팩토리얼'을 생각해보자.

부터 N까지의 자연수를 모두 곱하는 것을 의미한다.

팩토리얼을 자세히 살펴보면, N!은 '(N-1)! x N'임을 알 수 있다.

5! = 5 x (4!)
4! = 4 x (3!)
3! = 3 x (2!)
2! = 2 x (1!)
1! = 1 x (0!)

즉, 팩토리얼을 함수로 만든다면, 'N x (N-1)!'를 리턴하면 된다는 것이다.

리턴값에 팩토리얼이 있으므로, 이는 재귀를 사용해 풀 수 있다.

function factorial(num){
  //종료조건
  //return 재귀
}

종료 조건을 먼저 생각해보자.

팩토리얼은 무조건 어떤 수에 적용하건, 마지막엔 1을 곱하고 끝나게 된다.

그렇다면, 재귀의 마지막에 호출되는 함수는 1을 리턴하게 만들어준다.

팩토리얼은 1에서 끝나므로, num이 1인 경우 1을 리턴해야 한다.

function factorial(num){
  if(num === 1){
    return 1
  }
  //return 재귀
}

종료 조건을 만족했으니 재귀의 리턴값을 정해야 한다.

팩토리얼은 N * (N-1)!이므로, 이를 코드로 나타내면 다음과 같다

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