2021_03_25

TIL - 재귀함수

1. 재귀함수

오늘은 재귀함수에 대하여 학습하였다. 그렇다면 우선, 함수에서 '재귀'라는 것은 무엇일까? 재귀란 어떤 함수가 스스로를 반복적으로 호출하는 것을 말한다.
'반복적인 호출' 하면 무엇이 떠오르는가? 그렇다. 재귀함수는 반복문이랑 비슷한 기능을 한다. 그렇다면 반복문이 있는데 굳이 왜 재귀함수를 사용하는걸까?

이유는 코드의 간결함 때문일것이다. 또한 이 블로그를 작성하기 위해 검색을 해보니 변수 사용도 줄여준다고 한다. 그러나 장점만 있는것은 아니다.
재귀함수에는 치명적인 단점이 있다. 메모리를 많이 차지하며 성능이 반복문에 비해 느리다. 함수를 호출 시 함수의 매개변수, 지역변수, 리턴 값, 그리고 함수 종료 후 돌아가는 위치가 스택 메모리에 저장되기 때문이다.

위와 같은 문제를 해결하기 위해 꼬리재귀(tail recursion)을 이용할 수 있다. 재귀함수의 실행 결과가 연산에 사용되지 않고 바로 반환되게 함으로써 이전 함수의 상태를 유지할 필요가 없도록 재귀 함수를 작성하는 것이다.

위를 통해 재귀함수의 정의를 배웠다면 예시를 통해 재귀함수를 활용하는 법을 배워보자.

다음은 일반적인 재귀 함수의 템플릿이다.

function recursive(input1, input2 ...) {
//재귀의 기초(base case)
if(문제를 더 이상 쪼갤 수 없는 경우) { 
  return 단순한 문제의 해답;
}
//recursive case
//그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제;
 //예)1. somevalue + recursive(input1Changed, input2Changed...)
 //예)2. somevalue + recursive(input1Changed, input2Changed...)

이를 바탕으로 factorial 함수를 구현해보자

factorial(n)은 자연수 1부터 n까지의 곱을 계산하는 함수이다.
factorial(1) = 1 => factorial(1)
factorial(2) = 1 2 = 2 => factorial(1) x 2
factorial(3) = 1 2 3 = 6 => factorial(2) x 3
factorial(4) = 1 2 3 4 = 24 => factorial(3) x 4

우선 factorial 함수를 반복문을 이용해서 구현해보았다.

function factorial(n) {
  let result = 1;
  for (let i = n; i >= 1; i--) {
    result = result * i;
   }
  return result;
}

이번엔 재귀함수를 이용해서 구현해보자.

1. 문제를 더 이상 쪼갤 수 없는 경우: num이 0일 때
2. 단순한 문제의 해답: 1을 리턴한다.
3. 더 작은 문제로 새롭게 정의된 문제 num * factorial(num-1)

function factorial(num) {
//base case
  if(num === 0){ //문제를 더 이상 쪼갤 수 없는 경우
    return 1; //단순한 문제의 해답
  }
  //recursive case
  return num * factorial(num-1); //더 작은 문제로 새롭게 정의된 문제
}

factorial 함수를 각각 반복문과 재귀함수를 이용해서 구현해보았다.

위에서 재귀함수의 장점은 변수 사용을 줄여주고 코드의 간결함을 도와준다고 하였다. 반복문과 재귀함수로 구현한 코드 각각을 비교해보면 코드의 길이도 줄어들고, 변수 선언도 덜한 것을 볼 수 있다.

오늘은 재귀함수의 정의를 배우고 간단한 알고리즘을 구현하며 재귀에 대해 익숙해지는 시간을 가졌다. 강의를 해주시는 엔지니어분이 실무에 가면 굉~장히 많이 쓰일 개념이라고 하셨다. 앞으로 다양한 알고리즘에 재귀함수를 적용해보며 더 능숙해져야겠다.
내일은 더 나아가 재귀함수를 더 활용해 보는 시간을 갖는다.
오늘은 여기까지 ^_^