UVA 3n+1 (проб 100), что не так в моей программе C++

Question

Я пытался решить проблему 3n+1 (UVa 100), вот мой код, но, согласно онлайн-оценке UVa, моя программа дает неправильный ответ, мой код прошел все тестовые случаи, о которых я могу думать, но не смог определить, что не так, пожалуйста Помоги мне найти ошибку.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> Num;// for Memoization till 1000000

int counter(long int j)  {
    if(j > 1000000) {
        if(j%2 == 1)  return(counter((3*j+1)>>1)+2);
        else return(counter(j>>1)+1);
    }
    else {
        if(Num[j] != 0) return Num[j];
        if(j%2 == 1)  Num[j] = counter(3*j+1)+1;
        else Num[j] = counter(j>>1)+1;
    }
}

int main() {
    Num.resize(1000001);//auto initilizes the vector with 0
    Num[1] = 1; // set the counter for n = 1 as 1;
    int X,Y;
    while ( cin >> X >> Y )  {
        int x = X , y = Y, mxl = 0;
        if(X > Y) swap(X,Y);
        for ( long int j = Y; j >= X; --j)  {
            if(Num[j] == 0)  counter(j);
            if(mxl < Num[j])  mxl = Num[j];
        }
        cout << x << " " << y << " " << mxl << endl;
    }
return 0;
}

Answer 1

int counter(long int j)  {
    if(j > 1000000) {
        if(j%2 == 1)  return(counter((3*j+1)>>1)+2);
        else return(counter(j>>1)+1);
    }
    else {
        if(Num[j] != 0) return Num[j];
        if(j%2 == 1)  Num[j] = counter(3*j+1)+1;
        else Num[j] = counter(j>>1)+1;
    }
}

Где ваше возвращаемое значение в случае, когда Num[j] == 0 в этом последнем сегменте кода (внешний else)?

Вы установили Num[j] к правильному значению, но никогда не возвращайте его.

Я подозреваю, что вы ищете что-то вроде (избавиться от совершенно ненужного if..return..else так же конструирует):

int counter(long int j)  {
    if(j > 1000000) {
        if(j%2 == 1)
            return(counter((3*j+1)>>1)+2);
        return(counter(j>>1)+1);
    }
    if(Num[j] != 0)
        return Num[j];
    if(j%2 == 1)
        Num[j] = counter(3*j+1)+1;
    else
        Num[j] = counter(j>>1)+1;

    return Num[j];  // This is important.
}

---

Я должен отметить, однако, что рекурсия не может быть идеальным инструментом для использования здесь. С одной стороны, вероятность того, что последовательность может быть очень длинной, означает, что вам может не хватить места в стеке, прежде чем вы получите решение.

Во-вторых, рекурсивные звонки не обходятся без затрат. Много времени может быть потрачено на настройку и разбор кадров стека при поиске вашего решения.

Я бы предпочел итеративное решение, чтобы избежать этих потенциальных проблем.