재귀함수

재귀함수란?

• 정의 단계에서 자신을 참조하는 함수
• 매개변수는 바뀌면서 함수의 복사본을 호출
• 주로 큰 문제를 작은 부분문제로 바꾸어 해결할 때 사용

재귀함수의 꼴

주의사항

• 반드시 기저사례를 쓴다.(종료조건)
• f(a)에서 f(b)를 호출하는 경우에는 사용 x(사이클 발생 -> 무한 루프)
• 반복문으로 쓸 수 있다면 반복문으로!(함수 호출 코스트 때문)
• 함수 호출 코스트란?
  - 스택에 프레임 쌓기
  - 복귀할 주소
  - arr, n, 반환값을 저장할 공간 등
• 재귀 함수는 단순히 반복적으로 함수를 호출하는 것이 아니라 문제 해결 + 함수 호출 구조임
  

예시

팩토리얼

<재귀함수>

int Factorial(int n) {
	if (n <= 1) return 1;
    return n * Factorial(n - 1);
}

<반복문>

int mul = 1;
for (int i = 1; i <= n; i++) {
	mul *= i;
}

공간복잡도

재귀함수 : O(n)
반복문 : O(1)

시간복잡도

재귀함수: O(n)
반복문 : O(n)

시간복잡도는 같으나 재귀함수는 앞에서 말했듯이 공간을 할당하고 프레임을 쌓는데에 시간이 소모되기 때문에 대부분의 경우에서는 반복문이 더 빠르다. -> 반복문으로 구현할 수 있다면 반복문으로!

피보나치

이해하기 어렵다면

• 찍어보기. 디버깅하기. 흐름을 기억하고 그리고 나서 그걸 기반으로 재귀함수를 구현해보자.