재귀함수란? 간단하게 알아보자.

재귀란?

컴퓨터 과학에 있어서 재귀(Recursion)는 자신을 정의할 때 자기 자신을 재 참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다.

재귀함수

재귀 함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다. 다른 말로는 재귀 호출, 되부름이라고 부르기도 하며, 반복문을 사용하는 코드는 항상 재귀 함수를 통해 구현하는 것이 가능하며 그 반대도 가능하다.

재귀 함수를 작성할 때는 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 꼭 포함되어야 한다는 부분을 인지하고 작성하면 무한 루프를 방지할 수 있습니다.

재귀 함수를 직접 사용해보자

가장 쉽게 예시를 들자면 팩토리얼을 들 수 있다.

팩토리얼(Factorial) 구하기

function factorial(n) {
  if (n === 1) {
    return 1
  }
  return n * factorial(n - 1)
}
factorial(3) // 6

즉 팩토리얼함수에 3의 값을 넣었을 때 처음 스택 3이 쌓이고 두 번째 2 마지막 조건문을 끝으로 1이 쌓입니다. 결과적으로 321 = 6이 됩니다. n이 1일 경우 함수가 정지하도록 설정하였습니다.

꼬리 재귀

재귀 함수는 메모리를 많이 차지하지 때문에 성능이 반복문에 비해 느리다.

함수를 호출 시 함수의 매개변수, 지역변수, 리턴 값 그리고 함수 종료 후 돌아가는 위치가 스택 메모리에 저장된다.

재귀 함수를 사용하면 함수를 반복적으로 호출하므로 스택 메모리가 커지고, 호출하는 횟수가 많아지므로 스택오버플로가 발생할 수 있다.

꼬리 재귀는 기존의 재귀 함수의 문제를 해결할 수 있는 방법이다. 결론은

1. 프로그래머가 재귀 함수를 꼬리 재귀 방식으로 만들어야 한다.
2. 컴파일러가 꼬리 재귀 최적화를 지원해야 한다.

즉 컴파일러가 꼬리 재귀 최적화를 지원하지 않으면, 개발자가 꼬리 재귀 방식으로 개발해도 성능 및 메모리의 이점을 얻을 수 없다.

밑에 코드는 재귀와 꼬리 재귀를 사용한 코드다.

int Recursive(int n)
{
 if(n==1) return 1;
 return n + Recursive(n-1);
}


int Tail_Recursive(int n, int acc)
{
 if(n==1) return acc;
 return Tail_Recursive(n-1, n + acc );
}

일반적인 재귀 함수는 마지막, return 연산이(n + 함수(n-1)) 필요한 반면에 꼬리 재귀는 return 연산이 필요가 없다. 매개변수로 필요한 연산을 전달한다.

꼬리 재귀의 이점은 컴파일러가 지원한다는 것이다. 컴파일러가 꼬리 재귀를 최적화할 수 있으면 최적화하는 과정에서 꼬리 재귀를 반복문으로 변경하기 때문이다. 그러므로 기존 재귀 함수의 문제점인 메모리와 성능에 대한 문제점을 해결할 수 있다.