함수형 프로그래밍에서 재귀가 중요한 이유는 루프를 금지해서가 아니라 상태를 드러내기 위해서다
함수형 프로그래밍을 처음 볼 때 가장 낯선 장면 가운데 하나가 재귀다. 명령형 코드에서는 for나 while로 자연스럽게 풀던 반복을, 함수형 코드에서는 자기 자신을 다시 호출하는 방식으로 표현하는 경우가 많기 때문이다.
하지만 핵심은 “루프를 없애는 마술”이 아니다. 더 중요한 차이는 반복 과정에서 무엇이 바뀌는지를 더 분명하게 드러낸다는 점에 있다.
재귀는 숨은 상태를 인자로 꺼내 놓는다
명령형 루프에서는 보통 두 가지가 숨어 있다.
- 몇 번째 반복인지 나타내는 카운터
- 중간 결과를 쌓아 두는 누적값
재귀로 바꾸면 이 둘이 함수 인자로 밖으로 드러난다. 그래서 함수가 “지금 어디까지 왔는가”, “무엇을 쌓아 가고 있는가”를 더 직접적으로 보여 준다.
이 점은 특히 계산 규칙을 테스트하거나, 상태 전이를 추적해야 하는 코드에서 장점이 있다. 재귀가 멋져 보여서가 아니라, 반복에 숨어 있는 상태를 드러내기 때문이다.
꼬리 재귀는 재귀를 실용적으로 만드는 핵심이다
에를랑(Erlang) 공식 문서는 함수 본문의 마지막 표현식이 함수 호출이면 tail recursive call, 즉 꼬리 재귀 호출이 이뤄진다고 설명한다. 그리고 이런 꼬리 재귀 호출을 이용한 무한 루프는 호출 스택을 소진하지 않고 원칙적으로 계속 실행될 수 있다고 적고 있다.
이 차이는 실무적으로 크다.
- 일반 재귀는 호출이 깊어질수록 스택을 계속 쌓는다.
- 꼬리 재귀는 마지막 호출을 다음 반복처럼 처리할 수 있다.
그래서 함수형 코드에서 재귀를 쓸 때 중요한 것은 “재귀를 쓰느냐”보다 꼬리 재귀 형태로 정리할 수 있느냐에 더 가깝다.
누산기 패턴은 함수형 반복의 가장 실용적인 형태다
꼬리 재귀를 이해할 때 자주 만나는 형태가 누산기(accumulator) 패턴이다. 중간 결과를 함수 바깥 변수에 저장하는 대신, 다음 호출의 인자로 넘기는 방식이다.
이 방식이 좋은 이유는 단순하다.
- 현재 상태가 인자로 명시된다.
- 마지막 호출에서만 다음 단계로 넘어가므로 최적화 여지가 커진다.
- 함수가 어떤 중간 결과를 들고 있는지 테스트하기 쉽다.
즉 누산기 패턴은 함수형 프로그래밍의 미학이라기보다, 반복을 더 예측 가능하게 만드는 도구다.
순수 함수와 재귀는 자주 같이 나오지만 같은 개념은 아니다
순수 함수는 같은 입력에 대해 같은 출력을 돌려주고, 바깥 상태에 부작용을 만들지 않는 함수를 뜻한다. 재귀는 그런 순수 함수를 작성할 때 자주 쓰이는 표현 방식일 뿐, 둘은 같은 말이 아니다.
재귀 함수도 외부 상태를 읽거나 쓰면 순수하지 않을 수 있고, 반대로 반복문을 쓴다고 해서 반드시 비순수한 것도 아니다. 그래서 함수형 프로그래밍을 공부할 때는 “재귀 = 순수함”처럼 묶어 이해하기보다, 재귀는 반복을 표현하는 방식, 순수 함수는 부작용을 다루는 규칙으로 따로 보는 편이 좋다.
핵심 정리
함수형 프로그래밍에서 재귀가 중요한 이유는 루프를 금지해서가 아니다. 반복 과정에 숨어 있던 상태를 인자로 꺼내 놓고, 그 흐름을 더 분명하게 보여 주기 때문이다.
특히 에를랑 문서가 설명하는 꼬리 재귀와 누산기 패턴을 이해하면, 재귀는 “신기한 문법”이 아니라 반복을 더 명시적으로 다루는 실용적인 방법으로 보이기 시작한다. 함수형 프로그래밍의 핵심은 결국 마술이 아니라 상태를 어떻게 드러내고 다룰지에 있다.