재귀함수
재귀란 원래의 자리로 되돌아가거나 되돌아오는 것을 말한다.
그러니까 재귀함수는 자기 자신을 호출하는 함수를 말한다.
재귀함수를 사용하면 불필요하게 여러 반복문을 사용하지 않기 때문에 코드가 간결해지고 변수를 여러 개 사용하지 않아도 된다는 장점이 있다.
하지만 아직 익숙하지 않은 입장에선 반복문보다 코드 흐름을 한번에 이해하기가 어려웠고,
반복하여 메서드를 호출하며 지역변수, 매개변수, 반환 값을 모두 process stack에 저장하기 떄문에 반복문에 비해 메모리를 더 많이 사용하게 된다는 단점이 있다.
또한 메서드를 호출하고 메서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생한다는 단점이 있다.
이런 재귀 함수를 언제 사용하냐면,
- 문제의 크기를 점점 작은 단위로 쪼갤 수 있을 때
- 재귀 호출이 종료되는 시점이 존재할 때
사용한다.
재귀적 사고를 하기 위해선 다음과 같은 순서에 따라 문제를 파악하면 된다.
- 재귀함수의 입력 값과 출력 값을 정의한다.
: 문제를 가장 추상적 혹은 단순하게 정의한다.
ex) 함수 arrSum이 int타입을 요소로 갖는 배열을 입력받고, int타입을 리턴한다할 때,
arrSum: [int] -> int 이런 식으로 단순하게 정리한다.
- 문제를 쪼개고 경우의 수를 나눈다.
:문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다.
- base case 해결하기
: 재귀의 탈출 조건을 먼저 정리한다.
- 남아있는 문제 해결하기
: base case를 제외하고 남아있는 문제를 정리한다.
- 코드 구현
:1~4번까지 정리한 내용을 바탕으로 코드를 구현한다.
//factorial로 본 예제
// 반복문으로 구현한 팩토리얼 메서드
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);
}
for문처럼 반복해서 어떤 문제를 해결해야할 때 사용할 수 있는 함수였다.
처음엔 응..? 싶었는데, 기존에 for문을 사용해서 풀었던 형식의 문제들을 재귀함수를 이용해서 푸니까 더 간결하게 코드를 작성할 수 있어서 편했다.
다만 같은 연산을 여러번 처리해야한다는 단점이 있다고 해서, 이부분은 어떻게 처리해야하는지 궁금해졌다.
(추후에 배운다고 했으니... 우선은 재귀함수를 사용하는 것에 먼저 익숙해져야겠다)
재귀함수를 이용해서 문제를 풀 때 실수했던 가장 큰 이유는,
재귀함수를 돌리면서 변수를 설정했던 것이다..
이 메서드가 다시 실행되면서 변수가 설정한 값으로 초기화 되는 것을 생각 안하고 변수에 구한 값을 담아주려했다.
public class Solution {
public int factorial(int num){
//TODO n! 값을 리턴
int result = 1;
if ( num <= 1){
return 1;
}
result = result * num;
return factorial(num-1);
}
}이런 식으로 값을 넣어주려했다. (반복문과 단단히 착각했던 것...)
이렇게 안되는 걸 보고 아! 이러면 변수가 다시 1이 되니까 안담기는 구나.. 하고 알았다.
그리고 문제를 풀다가
java.lang.StackOverflowError이런 에러가 빈번하게 발생했는데, 이 에러는 보통 스택 메모리가 너무 많은 메소드 호출을 처리하지 못할 때 발생한다고 한다.
스택 메모리는 각 메소드 호출이 발생할 때마다 해당 호출에 대한 메모리를 할당하며, 메소드 호출이 계속되면 스택이 계속 쌓이게된다고 한다.
그니까 무한 재귀호출때문에 발생했다.
base case를 제대로 설정해주지 않았기때문에 발생했다. 그래서 최대한 base case를 먼저 정의하고나서 문제를 푸는 코드를 작성해야한다는 것을 알았다.
