재귀는 하나의 메서드 안에서 자기자신을 다시 호출하는 것입니다.

재귀의 최대 범위

재귀 호출을 너무 많이하면 변수들이 메모리를 모두 할당해서 StackOverFlowError예외가 발생합니다. 재귀 호출은 아무리 많아도 20,000번 이내로 해야합니다.

재귀 정의

1단계: 상태 정의하기

재귀는 하나의 문제를 부분 문제들로 나누어 해결해 나가면서 원본 문제의 답을 찾는 알고리즘입니다. 입력되는 변수들이 필요하고, 답을 결정하는 변수들을 상태라고 합니다. 따라서 부분문제는 하나의 상태에 대한 답을 찾는 문제입니다.

2단계: 종료 조건 작성하기

재귀로 부분 문제들을 생성해 나가다보면 언젠가는 종료해야 합니다. 따라서 부분문제들로 상태가 변해가다가 결국에는 종료조건에 도달하여 답을 내야합니다.

3단계: 점화식 세우기

상태와 종료 조건을 정의한 후에는 가장 큰 상태가 어떤 과정을 거쳐 종료 조건에 도달하는지 정의해야 합니다. 가장 큰 상태를 어떤 규칙으로 더 작은 상태로 만들어야합니다. 이런 규칙을 점화식이라고 합니다.