제귀함수

재귀 함수는 호출한 함수 내에서 다시 함수를 호출하는 것을 말하며, 간단한 예는 다음과 같습니다.

int factorial(n)
{
	if(n<=1) return 1;
	return n * factorial(n-1);  
}

코드를 간단하게 해석한다면,

1. if(n⇐1) return 1;

• 해당 함수에서 재귀 함수 호출을 멈추는 종료 조건입니다.

2. return n * factorial(n-1);

• 함수 내에서 함수를 재 호출하는 부분입니다.

이 코드가 실행되는 과정을 생각해보면 다음과 같습니다.

만일 n == 5라면

1. 종료 조건을 지나치고 return 값을 반환하기 위해 함수를 호출할 것입니다. 그 함수의 값을 반환받기 전까지는 대기할 것입니다.
2. 4번 반복합니다.
3. 이번에는 종료 조건에 부합하기에 값을 반환할 것입니다.
4. 이전에 대기하고 있던 함수가 동작하며, 값을 반환할 것입니다.

재귀 함수는 동작시 stack의 형태로 돌아갑니다. 그리고 for문에 비해 메모리와 시간적으로 안 좋기에 기왕이면 사용하지 않는 것을 권합니다.