알고리즘 - 재귀함수 (Recursion Funtion)

재귀 함수란? - Stack의 개념을 활용한 함수의 반복 호출

재귀 함수, 재귀 호출로 불리는 재귀의 개념은 어떠한 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 방식의 함수입니다. Stack처럼 함수의 정보가 하나씩 쌓이면서 종료 조건에 도달한 순간 계속해서 하나씩 처리해 나가는 개념입니다.

 

이런 재귀의 개념을 이용하면 많은 해결하기 위해 많은 과정을 논리적으로 표현하여 소스코드를 간결화할 수 있습니다. 다만, 설계상의 오류로 함수를 무한히 호출을 하던가, 너무 많이 함수의 호출이 반복되면 해당 문제를 해결하기 위해 너무 많은 자원의 소모, 부하를 줄 수 있게 되어 주의가 필요합니다. 

재귀 함수의 특징을 정리하자면 다음과 같습니다.

• 재귀 함수란 자기 자신을 호출하는 형태의 함수 개념들을 일컫는다.
• 재귀 함수를 사용하면 복잡하고, 많은 과정들을 논리적으로 간단하게 표현이 가능하다.
• 재귀 함수의 호출이 깊어지면 성능의 저하가 있을 수 있다.
• 재귀 함수의 무한 호출을 하지 않도록 설계해야 된다.

 

간단한 예시 - 팩토리얼

재귀 함수의 대표적인 예시로 팩토리얼을 예를 들어 보도록 하겠습니다.

팩토리얼을 1부터 그 수까지 모든 자연수를 곱하는 것입니다. 기호는!입니다.

1~5까지 팩토리얼을 보자면 아래와 같습니다.

1! = 1

2! = 2*1  = 2

3! = 3*2*1 = 6

4! = 4*3*2*1 = 24

5! = 5*4*3*2*1 = 120

물론 팩토리얼의 경우 간단하게 반복문을 통해 구현이 가능하지만, 재귀 함수를 통해 만들 수도 있습니다.

아래와 같은 기능을 가진 함수를 만든다고 가정해 봅시다. (C언어)

int Factorial(int number){
	if(number ==1){
    	return 1;
    }
    else{
    	return number * Factorial(number-1);
    }
}

• 인자 : 구하고자 하는 팩토리얼 수
• 완료 조건 : 인자의 값이 1이면 1을 반환
• 그 이외의 값은 인자 값 + 재귀호출(기존의 인자 값 -1)

이 재귀의 호출로 표현한다면 위와 같은 소스코드 표현이 됩니다. 이제 스택의 개념을 적용하여 재귀 함수의 호출이 어떻게 진행되는지 한번 알아보도록 하겠습니다.

 

3! 팩토리얼을 구하기 위해 인자로 5를 집어넣었다고 가정해 보도록 하겠습니다.

그림처럼 Stack의 개념으로 차곡차곡 함수가 재귀 호출을 해나가며 과정을 계속해서 기억하다가 종료 조건에 도달하면 하나씩 마무리를 지어가면서 모든 함수가 완료됩니다.

 

팩토리얼 같이 간단한 개념에서는 굳이 재귀의 개념을 적용을 해야 되는지 의문점이 생길 수도 있지만,  차차 배워가는 다양한 문제들에서 재귀의 개념을 적용하면 정말 간결한 표현으로 해결을 할 수 있는 문제들이 많기 때문에 알아두시길 권장합니다.