7-F 재귀로 풀시 런타임애러

안녕하세요. 해당문제를 재귀로 푸니 런타임애러가 발생했습니다. 대충 시간복잡도가 3000만 이하면 다 될 줄 알았는데 재귀로 푸니 스택오버플로우가 발생하던데 보통 몇 정도만 재귀로 푸는게 맞을까요..?

#define CRTSECURE_NO_WARNINGS

#include <iostream>

#include <vector>

#include <cstring>

#include <algorithm>

#include <queue>

#include <map>

#define INF 1e9

using namespace std;

int N, dp[1000004];

int go(int idx) {

if (idx == 1) return dp[idx] = 0;

int& ret = dp[idx];

if (ret != INF) return ret;

ret = go(idx - 1) + 1;

if (idx % 3 == 0) ret = min(ret, go(idx / 3) + 1);

if (idx % 2 == 0) ret = min(ret, go(idx / 2) + 1);

return ret;

}

int main()

{

fill(dp, dp + 1000004, INF);

cin >> N;

cout<<go(N)<<'\n';

while (N != 1) {

if (dp[N - 1] + 1 == dp[N]) {

cout << N << ' ';

N--;

}

else if (N % 3 == 0 && dp[N / 3] + 1 == dp[N]) {

cout << N << ' ';

N /= 3;

}

else if (N % 2 == 0 && dp[N / 2] + 1 == dp[N]) {

cout << N << ' ';

N /= 2;

}

}

cout << 1 << '\n';

}