계속 보면 어지럽습니다. 그만 보세요. 재귀함수도 그렇습니다!
1. 재귀 함수?
- 재귀 함수는 자기 자신을 다시 리턴하는 재귀 함수를 가지는 자기 자신을 다시 리턴하는 재귀 함수를 가지는 자기 자신을 다시 리턴하는 재귀 함수를 가지는 자기 자신을 다시 리턴하는 재귀 함수를 가지는...
- 자기 자신을 다시 리턴하는 함수이다.
- 이게 무슨 의미인가?
- 반복문과 똑같이 작동한다.
- 반복문처럼 '조건'을 가지고 그 조건에 맞으면 함수를 끝내게 된다.
- 가독성이 다른 반복의 코드보다 좋다.
2. 예시
- 한동안 우리를 한참 괴롭히던 피보나치 함수의 재귀 함수 버전이다.
function fibonacci(num) {
if(num === 0) {
return 0;
} else if(num === 1) {
return 1; // 앞의 if와 else if로 탈출 조건을 만들어 주었다.
} else {
num = fibonacci(num - 2) + fibonacci(num - 1) // 우리가 원하는 답을 다시 num에 넣는다.
return num;
}
}
- 반복문 버전보다 훨씬 간단하다.
- 하지만 효율적이지는 않다. 계속해서 함수를 불러오기 때문에 스택에 무리가 간다.
3. 재귀 함수를 어떻게 쓸 수 있을까?
입력값과 출력 값을 확인한다.
- 어떤 입력을 받아서 출력을 하는지를 정확히 알아야 함수가 리턴하는 값이 다시 자신으로 들어와 작동할 수 있는지를 알아야 한다.
문제를 쪼개서 생각한다.
- 입력값을 기준으로 경우의 수를 생각해 본다.
- 원하는 답으로 가기 위해 한 단계씩 진행되는 과정을 생각해 본다.
탈출 지점 만들기
- 재귀 함수를 돌다가 원하는 답이 리턴되는, 즉, 가장 작은 단위로 해결된 결과를 리턴한다.
- 이를 base case라고 한다.
문제를 계속 쪼개어 준다.
- 더 작은 단위로 문제를 쪼개어 준다. 재귀함수를 탈출하지 못하고 돌 때마다 해결해야 할 문제가 계속 줄어드는 것이다.
- 이를 recursive case라고 한다.
대충은 알겠지만 계속 사용해 보아야 부족함 없이 쓸 수 있을 것 같다. 재귀 함수는 반복문으로 사용할 수 도 있는데 이것도 생각을 해 보아야 할 문제이다.