팩트(10)가 호출되면 팩트(9), 팩트(8), 팩트(7) 등을 호출하지만 숫자는 100에 도달하지 않습니다. 따라서 기본 케이스에 도달하지 못했습니다. 스택에서 이러한 함수에 의해 메모리가 소진되면 스택 오버플로 오류가 발생합니다. 함수가 자신을 호출하는 프로세스를 재귀라고 하며 해당 함수를 재귀 함수라고 합니다. 재귀에 대해 이해하는 가장 인기있는 예는 요인 함수입니다. 파일 시스템의 파일 수가 다를 수 있으므로 재귀는 통과하여 내용을 열거하는 유일한 실용적인 방법입니다. 파일 시스템을 트래버스하는 것은 트리 통과와 매우 유사하므로 트리 순회 뒤에 있는 개념은 파일 시스템 탐색에 적용할 수 있습니다. 좀 더 구체적으로 말하자면, 아래 코드는 파일 시스템의 사전 주문 통과의 예입니다. 위의 함수 Count()는 재귀에서 1에서 9 사이의 모든 숫자에서 숫자 10까지 계산합니다. 예를 들어 Count(1)는 2,3,4,5,5,6,7,8,9,10을 반환합니다.

카운트(7)는 8,9,10을 반환합니다. 결과는 10에서 숫자를 빼는 원형 교차로 방법으로 사용할 수 있습니다. 단일 자체 참조만 포함하는 재귀는 단일 재귀라고 하며 여러 자체 참조를 포함하는 재귀는 다중 재귀라고 합니다. 단일 재귀의 표준 예는 선형 검색과 같은 목록 통과를 포함하거나 요인 함수를 계산하는 반면, 다중 재귀의 표준 예는 깊이 우선 검색과 같은 트리 순회를 포함합니다. (예, Eval이라는 함수를 기대하는 경우 위의 코드에서 인터프리터 패턴을 발견하는 것이 쉽지 않다는 것을 알고 있습니다. 그러나 실제로 인터프리터 패턴은 함수가 무엇이라고 부르는지 또는 어떤 작업을 하는지 알려주지 않으며 GoF 책은 위의 것을 명시적으로 나열합니다. [구조화 된 데이터를 사용 하는 함수] 일반적으로 그들의 인수를 즉시 구조 구성 요소로 분해 하 고 해당 구성 요소를 처리 합니다. 즉각적인 구성 요소 중 하나가 입력과 동일한 데이터 클래스에 속하는 경우 함수는 재귀적입니다. 이러한 이유로 이러한 함수를 (구조적으로) 재귀 함수라고 합니다.

위의 정의는 Scheme과 같은 함수형 프로그래밍 언어로 간단하게 변환됩니다. 이는 재귀적으로 구현된 반복의 예입니다.