재귀 함수

Mixer·2022년 5월 24일

비유를 통한 이해

프로그램이 실행되는 전체 과정을 공장의 생산 라인에서 여러 직원들이 제품을 생산하는 과정으로 비유해 보자.

그러면 프로그램의 입력은 곧 제품의 기초 재료가 되고, 소스 코드는 직원들의 매뉴얼에 비유할 수 있다.
각 직원은 하나의 함수를 담당한다고 가정하겠습니다. 그러면 프로그램이 실행되는 흐름은 다음과 같아진다.

프로그램에 들어온 입력을 (생산 라인에 들어온 기초 재료를) 여러 함수들이 (여러 직원들이) 순차적으로 처리하여 (순차적으로 가공하여) 정답을 구해내는 (제품을 완성하는) 과정

그러면 이제 프로그램의 실행 과정에 재귀 함수가 포함되는 경우를 추가 해보자
이를 생산 라인에 비유하기 위해, 직원을 다음과 같이 조금 더 명확히 재정의 해보자

매뉴얼에 적힌 내용대로 실제로 일을 하는 주체
중요한 것은 소스 코드는 그저 매뉴얼에 불과하다는 사실이다.
즉, 매뉴얼은 하나만 있지만 같은 매뉴얼대로 작업하는 직원은 여럿이 될 수도 있다.

이것이 재귀 함수를 이해하는 첫 단계

하나의 매뉴얼이라고 하더라도 세부적인 작업 내용은 정확히 그 직원이 이전 단계로부터 넘겨받은 재료의 상태에 따라 달라질 수 있다.
이렇게 이전 단계로부터 넘겨받은 재료는 곧 함수의 인자 (또는 전역 변수)가 된다.

즉, 재귀 호출은 다음과 같이 비유할 수 있다.

한 직원이 자신과 같은 매뉴얼에 따라 작업하는 다른 직원에게 특정 상태의 재료들을 건네며 작업을 요청하고 그 결과물을 돌려받는 과정

한 가지 더 눈여겨볼 점은 여기서는 오로지 순차적인 작업만을 가정하고 있기 때문에 직원 A가 직원 B에게 일을 넘겼다면 B가 일을 모두 마치고 결과물을 A에게 돌려주기 전까지 A는 아무것도 하지 않는다는 점이다.

즉, A는 B가 최종적으로 만들어 낸 결과물만이 필요할 뿐 그 사이에 무슨 일이 일어나는지에 대해서는 전혀 신경쓰지 않아도 된다.

재귀는 같은 일을 하는 함수끼리 상태만 달리해 호출 하는 것이다.
재귀 호출된 함수가 무슨 일을 했는진 (다른 재귀 호출이 있던지 등) 중요하지 않으며, 어떤 결과만 돌려주는것만이 중요하다
재귀를 사용하는 함수는 반드시 재귀 호출을 하지 않는 경우 (예외 케이스)를 하나 이상 포함해야 하며, 그렇지 않으면 재귀 호출이 무한히 발생하게 된다.

Minthug'life