자바 프로그래머스에서 열심히 코딩 공부를 하던 중,
재귀함수가 사용된 것을 처음 보았다.
재귀함수는 자기 함수에서 자기 자신을 호출하는 함수를 말하는 것으로,
반복적인 연산 처리에 특히 유용하게 사용되는
재귀함수에 대해 알아보았다.
재귀메서드, 재귀함수 개념
재귀메서드, 재귀함수는 함수가 자기 자신을 호출하는 것을 말함.
- 일반적 구조
public int 메서드명(입력값) {
if (종료조건) { // 종료 조건 만족하면 종료
return 기본값;
}
return 재귀함수(조정된 입력값); // 자기자신 호출
}
재귀함수는 함수 내에서 자신을 호출하고,
호출할 때마다 입력값을 조정하여
종료조건을 만족할 때까지 자신을 호출하도록 설계된다.
재귀함수 동작 원리
재귀 함수는 스택 자료구조를 통해 동작함
각각의 재귀 호출은 스택 프레임에 쌓이고,
함수가 종료되면 해당 스택 프레임 제거
최종적으로 최하위 호출부터 차례대로 결과를 반환한다.
재귀함수 예시
<팩토리얼 구하는 메서드 작성>
public int factorial(int n) {
if (n == 0 || n == 1) { // 종료 조건
return 1;
}
return n * factorial(n - 1); // 자기 자신 호출
}
<제곱 구하는 메서드 작성>
private int pow(int base, int exponent) { // 종료 조건
if(exponen == 0) return 1;
return base * pow(base, exponent - 1); // 자기 자신 호출
}
재귀함수 장단점
장점
- 간단하고 간결한 코드 작성 가능
- 반복적인 문제를 효율적으로 해결할 수 있음
- 문제를 하위 문제로 분할하여 해결할 수 있음
단점
- 재귀 호출 시 스택 메모리를 사용하므로 메모리 부하 발생 가능
- 종료 조건을 설정하지 않으면 무한 반복에 빠질 수 있음
- 반복문보다 함수 호출에 추가적인 오버헤드가 발생할 수 있음