기본 경우에 도달하는 과정
정수 n이 0 이상일 때 0부터 n까지의 합은 n과 그 이전 합을 이용해 정의할 수 있다. n=0의 값은 0으로 직접 정하고, 나머지는 n에 n−1까지의 합을 더한다.
기본 경우가 존재하더라도 호출이 그쪽으로 이동하지 않으면 끝나지 않는다. 입력 범위를 제한하고 매 단계에서 어떤 양이 줄어드는지 확인해야 종료를 설명할 수 있다.
되돌아올 상태가 필요한 이유
재귀 호출이 끝난 뒤에도 처리할 일이 남아 있다면 호출마다 그 상태를 보관해야 한다. 일반적인 구현에서는 호출 스택이 복귀 위치와 지역 값을 관리한다. 따라서 재귀 깊이가 깊어지면 메모리 사용도 늘어날 수 있다.
꼬리 재귀는 재귀 호출 이후에 별도의 계산이 남지 않는 형태다. 그러나 모든 언어와 실행 환경이 이를 스택 사용 없이 최적화한다고 가정해서는 안 된다. 실제 지원 여부는 언어와 구현의 규칙에 달려 있다.
자연스러운 표현과 계산량은 별개다
트리의 각 노드 아래에 같은 형태의 부분 트리가 있으므로 재귀로 순회 절차를 표현하기 쉽다. 큰 문제를 나누어 같은 방법으로 해결하는 분할 정복에도 재귀가 자주 쓰인다.
반면 같은 부분 문제를 반복해서 계산하는 재귀는 매우 느릴 수 있다. 이미 얻은 결과를 저장하거나 계산 순서를 바꾸면 중복을 줄일 수 있다. 코드가 짧다는 사실이 계산량이 적다는 뜻은 아니다.
반복문과의 관계
여러 재귀 알고리즘은 명시적인 스택이나 반복문으로 바꿔 구현할 수 있다. 재귀와 반복 중 무엇을 선택할지는 자료 구조, 필요한 상태, 가독성과 자원 제한에 따라 달라진다.
재귀가 항상 반복보다 느리거나 항상 더 이해하기 쉽다고 일반화할 수는 없다. 실행 횟수와 저장 공간을 분석하고 실제 입력 크기에 맞춰 선택해야 한다.