[Javascript] 재귀함수 (알고리즘)

 

 알고리즘이란 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다.

 

알고리즘에 대한 공식적인 정의는 없지만, 좋은 알고리즘의 조건은 존재한다.

• 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다.
• 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다.
• 타당성 : 구현할 수 있고 실용적이어야 한다.
• 입력 : 정의된 입력을 받아들일 수 있어야 한다.
• 출력 : 답으로 출력을 내보낼 수 있어야 한다.
• 유한성 : 특정 수의 작업 이후에 정지해야 한다.
• 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다.

그리고 알고리즘을 구현하는 방식으로 재귀 알고리즘이 있으며, 이것이 재귀함수이다.

 

 재귀함수란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다. 재귀 호출이나 되부름 이라고 불리기도 한다.

 

재귀함수를 표현하는 방식으로 가장 많이 쓰이는 예가 팩토리얼이다.

 

function fac(n){
	if(n <= 1){
    	return 1;
    }else{
    	return n * fac(n-1);
    }
}

 

5! 을 fac함수를 이용해 구한다고 하면, n자리에 5를 넣고 fac(5)에서 5는 1 보다 크기 때문에 5 와 fac(4) 를 곱하여 return하게 된다.

 

fac(4)역시 1보다 크기 때문에 4와 fac(3)을 곱하게 되고, 이과정이 반복되어 5!의 결과값이 나오게 된다.

 

피보나치 수열을 나타낼 때도 사용 될 수 있다.

 

피보나치 수열 식

피보나치 수열은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

 

이 특성을 이용하여 재귀함수를 작성하면 다음과 같다.

 

function f(n) {
	if(n === 0){
    	return 0;
    }
	if(n === 1){
    	return 1;
    }
    
    return f(n - 1) + f(n - 2)
};

이렇듯 재귀함수를 이용하여 반복적인 작업을 통해 표현할 수 있는 여러 수식이 존재한다.

 

재귀함수 작성에 있어서 가장 중요한 점은 종료 조건을 달아주어야 한다는 것이다.

 

종료 조건이 없다면 무한히 함수가 돌아가며, 컴퓨터에 무리를 줄 수 도 있기 때문이다.

 

재귀함수는 반복문에 비해서 코드가 간결하고, 오류 수정하기에 용이하다.

 

다만 간단한 재귀함수의 경우 반복문을 쓰는 것이 훨신 낫기도 하고 기억공간을 많이 요구하기 때문에,

 

재귀함수를 사용할 것인지 반복문을 사용할 것인지 잘 판단하여 결정해야 한다.