[JAVA] 재귀함수

재귀함수

• 정의 단계에서 자신을 재참조하는 함수

• 자기 자신을 다시 호출해 작업을 수행하는 함수

재귀 함수 장점

• 변수를 여러 개 사용할 필요 X

• 반복문을 사용하지 않아도 되므로 코드가 간결해짐, 수정 용이

재귀 함수 단점

• 코드 흐름을 직관적으로 파악 X

• 반복하여 메서드를 호출하게 되면서 지역변수, 매개변수, 반환값을 모두 process stack에 저장해야함->반복문에 비해 메모리를 더 많이 사용

• 메서드를 호출->복귀를 위한 컨텍스트 스위칭 비용 발생

• Stack이 너무 커질 경우 StackOverFlow 발생

사용하는 상황

• 주어진 문제를 비슷한 구조로 더 작게 쪼갤 수 있을 때
• 중첩된 반복문이 많거나 중첩 횟수를 예상하기 어려울 때
• 적은 변수를 사용해 mutable state를 줄여 프로그램 오류가 발생할 수 있는 가능성을 없앨 수 있을 때

재귀함수 템플릿

function recursive(input1, input2, ...) {
// Base Case : 문제를 더 이상 쪼갤 수 없는 경우
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive Case
// 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
// 예1. someValue + recursive(input1Changed, input2Changed, ...)
// 예2. someValue * recursive(input1Changed, input2Changed, ...)
}