[재귀 함수]
재귀 : 원래의 자리로 되돌아가는 것
재귀 함수 : 같은 형태의 작은 단위 자기 자신을 호출하는 것
[recursion 함수 사용시 ]
장점 : 반복적 작업 좀 더 간결하게 표현 가능, 수정 용이, 변수 단순화
단점 : 코드 흐름 직관적으로 파악 어려움. 메모리 많이 사용. 스위칭 비용 발생
다르게 생각하기 : 문제를 작게 쪼개기 -> 가장 작은 단위로 쪼개기 -> 문제 해결하기
public int arrSum(int[] arr) {
int sum = 0;
for(int i = 0; i < arr.length; i++) {
sum+= arr[i];
}
return sum;
}
해당 문제를 재귀함수 사용시
가장 작은 단위로 쪼개졌을 때 arrSum([]) ==0; // 문제가 더는 작아지지 않는 순간 가장 작은 경우의 해결책을 적용 -> 연쇄적으로 문제 해결
public int arrSum (int[] arr) {
if (arr.length == 0) { // 빈 배열을 받았을 때 0을 리턴하는 조건문.
return 0; // 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
}
return arr[0] + arrSum(arr); // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum함수
} // 재귀 (자기 자신을 호출)을 통해 문제를 작게 쪼개나가는 코드[재귀 사용]
-
주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있을 때
-
중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려울 때
-
변수 사용을 줄여 mutable state(변경 가능한 상태)를 제거하여 프로그램 오류 가능성을 줄일 때
[재귀적 사고 연습하기]
재귀 함수의 입력값과 출력값 정의
문제를 쪼개고 경우의 수를 나누기 (입력값, 문제의 순서, 크기)
단순한 문제 해결하기
복잡한 문제 해결하기
코드 구현하기
[재귀함수 템플릿]
public type recursive(input1, input2, ...) {
// Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (탈출)
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive Case (문제 작게 쪼개기)
// 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
// 예1. someValue + recursive(input1Changed, input2Changed, ...)
// 예2. someValue * recursive(input1Changed, input2Changed, ...)
}예외값과 범위값 꼭 확인해야!!
[팩토리얼 반복문 vs 재귀함수]
// 반복문 팩토리얼
public int Factorial(int number) {
int result = 1;
for(int count = number; count > 0; count --) {
result = result * count;
}
return result;
}
// 재귀 팩토리얼
public int Factorial(int number) {
if(number <= 1) {
return 1;
}
return number * Factorial(number -1);
}