CODEWITHSUNDEEP
c++recursionsegmentation-faultruntime-error
ArekBulski
ArekBulski

Reputation: 5078

C++ recursion causing segfault?

I had my student write this code today and it segfaults and I dont quite understand why. The problem is counting letters for English pronouncation of numbers. Its one of earliest Project Euler problems. Is there a problem with recursion or something?

#include<iostream>
using namespace std;

int dlugosc(int x)
{
    if(x == 1) return 3;
    if(x == 2) return 3;
    if(x == 3) return 5;
    if(x == 4) return 4;
    if(x == 5) return 4;
    if(x == 6) return 3;
    if(x == 7) return 5;
    if(x == 8) return 5;
    if(x == 9) return 4;
    if(x == 10) return 3;
    if(x == 11) return 6;
    if(x == 12) return 6;
    if(x == 13) return 7;
    if(x == 14) return 8;
    if(x == 15) return 7;
    if(x == 16) return 7;
    if(x == 17) return 9;
    if(x == 18) return 8;
    if(x == 19) return 8;
    if(x == 20) return 6;
    if(x == 21) return 10;
    if(x == 22) return 10;
    if(x == 30) return 6;
    if(x == 40) return 6;
    if(x == 50) return 5;
    if(x == 60) return 5;
    if(x == 70) return 7;
    if(x == 80) return 6;
    if(x == 90) return 6;
    if(x == 100) return 11;
    if(x == 200) return 11;
    if(x == 300) return 13;
    if(x == 400) return 12;
    if(x == 500) return 12;
    if(x == 600) return 11;
    if(x == 700) return 13;
    if(x == 800) return 13;
    if(x == 900) return 12;
    if(x < 100) return dlugosc(x-x%10) + dlugosc(x%10);
    if(x < 1000) return dlugosc(x-x%100) + dlugosc(x-x%10) + dlugosc(x%10) + 3;
    if(x == 1000) return 11;
}

int main()
{
    int ile = 0;
    for(int i=1; i<=1000; i++)
    {
        ile += dlugosc(i);
    }   
    cout << ile;
    return 0;
}

Upvotes: 0

Views: 59

Answers (1)

Zeta
Zeta

Reputation: 105886

The recursion does not exit for the input x=110. You can check this quickly via gdb or by hand:

if(x < 1000) return dlugosc(x-x%100) + dlugosc(x-x%10) + dlugosc(x%10) + 3;

Since x - x%10 is x if x is divisible by 10, the second term (dlugosc(x-x%10)) will recurse infinitely for x = 110.

Upvotes: 4

Related Questions