Why it is giving a segmentation fault

Question

1.00/5 (2 votes)

See more:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

C++

#include <iostream>

int collatz_calculator(int n, int count)
{
    if(n==1)
    {
        count++;
        return count;
    }
    if(n%2==0)
    {
        count++;
        collatz_calculator(n/2, count);
    }

    else{
        count++;
        collatz_calculator(3*n+1, count);
    }

}

int largest_col_seq()
{
    int count=0;
    int max=0;

    int i=999999;
    int largest=0;
    for(i; i>10; i--)
    {
        int num=collatz_calculator(i, count);
        if(num>max)
        {
            max=num;
            largest=i;
        }
    }
    return largest;

}

int main()
{
    std::cout<<largest_col_seq()<<std::endl;
}

What I have tried:

I have tried with debugging, I have not much experience in debugging can you suggest any method of how to know what is the problem here

Posted 10-Sep-18 18:19pm

Member 13277493

Updated 10-Sep-18 22:21pm

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Accepted Answer · 2018-09-10T19:42:00

Almost certainly, you are blowing out the top of the stack.
Every time you call a function in C++ it takes an amount of space on the stack - which is recovered when the function returns - for the return address and the parameters, and more for some local variables. On a 64 bit system, the minimum stack space used is 8 bytes (64 bits for a pointer to the return location), but you also add two integers, for another 8 bytes, each time you call collatz_calculator.

Since you are calling it recursively, that's probably what is happening.

You can increase the stack from the default 1Mb:

PROJECT ... Properties ... Configuration Properties ... Linker ... System ... Stack Reserve Size=number of bytes required

but I'd probably look at a non-recursive solution.

CPallini · Accepted Answer · 2018-09-10T22:22:00

With compilers supporting it, you may try tail recursion.

C++

#include <iostream>

int collatz_calculator(long long n, int count)
{
    if ( n == 1 )
    {
      return ( count + 1 );
    }

    n = ( n % 2) ? 3 * n +1 : n / 2;

    return  collatz_calculator (n, count + 1 );
}

std::pair<int, int> largest_col_seq(int upper_limit)
{
    int max = 0;
    int max_index = 0;
    for(long long i = upper_limit; i>10; i--)
    {
        int num = collatz_calculator(i, 0);
        if(num>max)
        {
            max = num;
            max_index = i;
        }
    }
    return std::make_pair(max_index, max);
}

int main()
{
    auto max_pair = largest_col_seq(999999);
    std::cout << "maximum sequence length at index = " << max_pair.first << ", length = " << max_pair.second << std::endl;
}

compiled with g++ and optimization at level 2 (-O2) outputs

maximum sequence length at index = 837799, length = 525

on my Linux box.

Why it is giving a segmentation fault

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0