Recursive solution for 3n+1

Question

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?

Answer 1

with 999, you reach 11392

with 907, you reach 13120

and those numbers are out of bound.

Live example

Answer 2

You are indexing the array out of bounds

• For the inputs you are using, the variable n will exceed the array size 10000 during execution. This causes the program to access memory beyond its boundaries, resulting in a segmentation fault.

• If you're trying to memoize the function, I'd suggest using std::map instead of a fixed array. This is an associative array which stores key-value pairs—in this case, each memoized input-output pair—and can quickly retrieve the value associated with a given key. Maps are ideally suited for this application as they can store this data using only as much memory as is actually necessary, automatically growing as needed.

• You could also use std::vector, though this is not recommended. Vectors are like arrays, but they can be resized dynamically, avoiding the problem of indexing out of bounds. The drawback with this approach is that for certain inputs, a very large amount of memory may be required, possibly several gigabytes. If the program is compiled to a 32-bit binary rather than to a 64-bit binary, the program may crash at runtime when it fails to allocate enough memory for the vector.

Implementation using map

#include <iostream>
#include <map>

using namespace std;

long long dp(unsigned long long);

int main() {
    unsigned long long n;

    while(true) {
        cout << "Enter a number, or 0 to exit: ";
        cin >> n;

        if(!cin) {
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            cerr << "Invalid input, please try again." << endl;
            continue;
        }

        if(n == 0)
            return 0;
        else
            cout << dp(n) << endl;
    }

    return 0; // Unreachable
}


long long dp(unsigned long long n) {
    static map<long long, long long> memo;

    if(n == 2 || n == 1) return 1;
    if(memo[n]) return memo[n];

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

Implementation using vector

#include <iostream>
#include <vector>

using namespace std;

long long dp(unsigned long long);

int main() {
    unsigned long long n;

    while(true) {
        cout << "Enter a number, or 0 to exit: ";
        cin >> n;

        if(!cin) {
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            cerr << "Invalid input, please try again." << endl;
            continue;
        }

        if(n == 0)
            return 0;
        else
            cout << dp(n) << endl;
    }

    return 0; // Unreachable
}


long long dp(unsigned long long n) {
    static vector<long long> arr;

    if(arr.size() <= n)
        arr.resize(n + 1);

    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];
}

Answer 3

The segmentation fault comes from overflowing the array. How about you do something like the following?

void rec(int n, int* steps) {
  ++(*steps);
  printf("%d\n", n);
  // termination step if 'n' equals 1
  if(n == 1)
    return;
  if (n % 2 == 0)
    rec(n/2, steps);
  else
    rec(3*n+1, steps);
}

int main(void) {
  int steps = 0;
  rec(10, &steps);
  printf("Steps = %d\n", steps);
  return 0;
}

Output:

10
5
16
8
4
2
1
Steps = 7

The code presented here agrees (of course) with Jarod's answer.

Answer 4

You are overflowing the array because the sequence value exceeds 9999.

Answer 5

If all you want to know is the number of processes that it takes, you should not be using array storage.

int numProcesses = 0;

int hailstone(int n) {

    if (n == 1) {
        return 1;
    } // base case

    ++numProcesses; // if it wasn't the base case the method will do some work so increment numProcesses

    if (n % 2 == 0) {
        return hailstone(n / 2);
    } // n is even
    else {
        return hailstone(3 * n + 1);
    } // n is odd
}

This is untested but I think it should work, and after it finally returns numProcesses should equal the number of times the method was called (so long as it was not called with a parameter of 1).