재귀여서 그래요

재귀 함수는 깊이 들어갈 때마다 스택 메모리에 계속 누적이 되게 됩니다. 해당 메모리는 또 메모리 제한에 포함이 되기 때문에, 그만큼 메모리를 더 많이 잡아먹게 되는 것이라고 볼 수 있겠습니다. 해당 코드는 dp 함수로 깊이 들어가서 값을 리턴받고 이를 bin 배열에 저장해주는 재귀함수 구조라서, 제대로 된 다이나믹 프로그래밍이라고 볼 수 없습니다. 다이나믹 프로그래밍으로 문제를 풀려면, 재귀함수로 더 깊이 들어가는 것이 아니라 이전에 bin 배열에 저장하신 값을 다시 재활용을 해야 합니다. 이렇게 풀면 int 1000000개 만큼의 메모리만 소모하고, 추가적으로 더 많은 메모리를 잡아먹지는 않게 됩니다.

추가로 재귀함수로 피보나치 수열 문제를 풀 경우 값이 k일 때 시간 복잡도는 O(1.618^k)이지만, 올바른 다이나믹 프로그래밍으로 문제를 풀 경우 O(k)가 나오게 되므로 이것도 재귀함수를 사용하시면 안 되는 이유라고 보실 수 있겠습니다.