함수의 재귀적 호출

재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소이고, C언어는 이렇듯 중요한 재귀를 지원하는 언어이다.

재귀함수란, 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다.

"재귀 함수를 실행하는 중간에 다시 재귀 함수가 호출되면, 재귀 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 된다."

실제로 함수를 구성하는 명령문은 CPU로 이동이 되어서(복사가 되어서) 실행이 된다. 그런데 이 명령문은 얼마든지 CPU로 이동이(복사가) 가능하다. 

따라서 재귀 함수의 중간쯤 위치한 명령문을 실행하다가 다시 재귀 함수의 앞 부분에 위치한 명령문을 CPU로 이동시키는 것은 문제가 되지 않는다. 그래서 재귀적인 형태의 함수호출이 가능한 것이다.

위의 코드에서 Recursive 함수에 0이 전달도면서 '재귀의 탈출조건'이 성립되어 함수가 반환하기 시작한다. 

이렇듯 재귀함수의 정의하는데 있어서 탈출조건을 구성하는 것은 매우 중요한 일이다.

재귀함수의 디자인 사례

- 재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 무기이다. 무엇보다도 재귀함수가 있기에 재귀적인 수학적 수식을 그대로 코드로 옮길 수 있다.

# 팩토리얼

위의 식에서 보이듯 f(0)에 해당하는 0!이 1이므로 이것이 재귀함수의 탈출조건이 된다. (수학적으로 0!과 1!은 모두 그 값이 1로 동일하다) 따라서 이제 위의 식은 재귀함수를 이용해서 그대로 코드로 옮길 수 있다.

함수의 코드만 이해하려  하지 말고 그 과정을 이해하려고 노력해야 한다.