Search code examples
c++algorithmdynamic-programmingmemoization

Recursive solution for 3n+1

I just like to do simple recursion. For a number if it is even then it'll approach to (number/2) and if odd then to (3*number+1). How many time it'll occur to reach 1.

for 10
10-> 5-> 16-> 8-> 4 -> 2 ->1
total process 6

long arr[10000];
long dp(int n)  
{ 
    if(n==2|| n==1) return 1;
    if(arr[n]) return arr[n];

    if(n%2==0) return arr[n]=1+dp(n/2);
    else if(n%2==1) return arr[n]=1+dp(3*n+1);
    return arr[n];
}

I've created function like this one and for some input like 999 or 907 causes segmentation fault.
I wanna know why?

And if I increase array size then its output correctly.
I wanna know why too?

Why its depending on array size as I've taken long as array element data type so it should output correctly for those input?

Solution

  • with 999, you reach 11392

    with 907, you reach 13120

    and those numbers are out of bound.

    Live example