Primitive Calculator

for the following problem:

"You are given a primitive calculator that can perform the following three operations with the current number 𝑥: multiply 𝑥 by 2, multiply 𝑥 by 3, or add 1 to 𝑥. Your goal is given a positive integer 𝑛, find the minimum number of operations needed to obtain the number 𝑛 starting from the number 1.

INPUT FORMAT: The input consists of a single integer 1 ≤ 𝑛 ≤ 1000000

Output Format: In the first line, output the minimum number 𝑘 of operations needed to get 𝑛 from 1. In the second line output a sequence of intermediate numbers.

Example:

Input: 5

Output:

3

1 2 4 5

Here, we first multiply 1 by 2 two times and then add 1. Another possibility is to first multiply by 3 and then add 1 two times. Hence “1 3 4 5” is also a valid output in this case."

This is my solution in C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<long> lookup;

long Min_sequence(long x){ // Compute the minimum number of operations needed to obtain the number x starting from the number 1 for 3 following operations
                           //  multiply by 2, multiply by 3, or add 1 to 
    if(x==1) 
        return lookup[x];
    else if(lookup[x]!=0)
        return lookup[x];
    else if(x%3==0&&x%2==0)
        lookup[x]=min(Min_sequence(x/3)+1,min(Min_sequence(x-1)+1,Min_sequence(x/2)+1));
    else if(x%3==0)
        lookup[x]=min(Min_sequence(x-1)+1,Min_sequence(x/3)+1);
    else if(x%2==0)
        lookup[x]=min(Min_sequence(x-1)+1,Min_sequence(x/2)+1);
    else
        lookup[x]=Min_sequence(x-1)+1;
        
    return lookup[x];
};

void back_track(long n){ // Print sequence of intermediate numbers from 1 to n 
    if(n%3==0&&n%2==0)
        if(lookup[n]==lookup[n/3]+1)
            back_track(n/3);
        else if(lookup[n]==lookup[n/2]+1)
            back_track(n/2);
        else
            back_track(n-1);
     else if(n%3==0)
        if(lookup[n]==lookup[n/3]+1)
            back_track(n/3);
        else
            back_track(n-1);
    else if(n%2==0)
        if(lookup[n]==lookup[n/2]+1)
            back_track(n/2);
        else
            back_track(n-1);
    else if(n!=1)
           back_track(n-1);
    
    cout<<n<<" ";
}

int main() {
  int input; // Entered number to calculator
  std::cin >> input;
  lookup.assign(input+1,0);

  cout<<Min_sequence(input)<<endl; // Calculate minimum number of operations

  back_track(input);  // Print sequence of intermediate numbers 

  system("pause");
  return 0;
}
 

The algorithm works well for low values of input, but when it comes to values of input more than 6880, it throws exception. Unhandled exception at 0x000D4889 in Test.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x006A2FEC).