[C] 반복문, 재귀, 꼬리재귀

C에서 반복적인 로직을 구현할때 사용할 수 있는 방법론엔 총 3가지가 있는데, 그게 바로 반복문과 재귀함수, 꼬리재귀다.

간단한 팩토리얼 함수를 구현해보며 그 차이점과 장단점을 비교해보겠다.

반복문
먼저 반복문을 통한 구현이다.
가장 기본적인 방법이고, 사실 성능도 이게 제일 좋다.

근데 팩토리얼은 논리구조가 워낙 간단하다보니 티가 그리 나진 않지만, 이게 어떤 상황에서는 코드가 굉장히 길어지고 보기 힘들어질 수가 있다.

이걸 해결하기 위한 좋은 방법 중 하나가 바로 재귀함수다.

재귀함수
재귀함수란 함수에서 함수 자기 자신을 부르면서 일련의 반복을 수행하는 것이다.
특유의 수학적 방법론에 익숙하지 않다면 사용이 좀 어려울 수도 있는데, 대신 적절한 상황에서 잘만 쓴다면 코드의 양이 획기적으로 줄고 간단하며, 보기 편해질 수 있다.

다만 단점으론, 성능을 좀 먹을수도 있단게 걸린다.
함수의 특성상 함수가 호출될때마다 스택에 리턴어드레스와 지역변수들을 스택에 올리게 된다. 근데 이게 메모리나 성능을 좀 먹을 뿐더러, 스택이 워낙 비좁다보니 과하게 호출이 되면 스택오버플로가 떠서 프로그램이 터질 수도 있단거다.

이 2가지 방법의 장점을 오묘하게 섞은게 바로 꼬리재귀다.

꼬리재귀
꼬리재귀는 사실 C에서는 표준 기능이 아니다. 보통 함수형 언어들에서나 정식적으로 지원되고 그러는데.
뭐 그래도 어지간히 미개한 컴파일러가 아니면 다 지원은 한다.
그리고 이게 항상 활성화가 돼있단 보장이 없어서 쓰기 전에 따로 컴파일러 옵션을 확인해줘야한다.

여튼 꼬리재귀는 정확히는, 꼬리호출 최적화라고 한다.
위의 재귀 코드에서는 반환식에 아래와 같이 재귀호출의 리턴값에 n을 곱하는, 추가적인 연산식을 붙여놨었다.
factorial(n-1)** * n**
근데 여기서 저 추가 연산식 *** n**을 완전히 빼버리고, 재귀호출식이 홀로 유일한 표현식이 된다면... 컴파일러가 저 재귀함수를 반복문으로 최적화해준다.

어쨌든 뭐, 제약사항이 늘었으니, 접근방식을 좀 달리해야한다.
팩토리얼의 경우에는 아래와 같이 결과값을 저장할 매개변수를 따로 두는 식으로 구현을 수정한다.

근데 저기서 결과값을 매개변수로 항상 보내줘야하는건, 사용자에게 좀 불편하다.

이럴땐 구현함수와 사용함수를 분리하면 된다.

짜잔.
이러면 재귀의 간결함과 반복문의 성능을 어느정도 절충한 결과물이 나오는 것이다!

근데 뭐 사실 재귀를 굳이 사용할만한 상황은 자주 일어나지 않는다.
평소에는 그냥 상식으로만 알아두고 루프만 써도 충분하다.