Segmentation fault C++ in recursive function

Question

Why do I get a segmentation fault in my recursive function. It happens every time i call it when a value greater than 4 as a parameter

#include <iostream>
#include <limits>

using namespace std;    

int printSeries(int n){
    if(n==1){       
        return 1;
    }
    else if( n==2){     
        return 2;
    }
    else if( n==3){
        return 3;
    }
    else if( n==4){
        return printSeries(1) + printSeries(2) + printSeries(3);
    }
    else{       
        return printSeries(n-3) + printSeries((n-2) + printSeries(n-1));
    }
}


int main(){

        //double infinity = numeric_limits<double>::max();

        for(int i=1; i<=10; i++){
            cout << printSeries(i) << endl;
        }

    return 0;

}

This works fine, but i'm not sure that returns the correct result:

return printSeries(n-3) + printSeries(n-2) + printSeries(n-1);

Add std::cout << n << ','; at the top of your printSeries() function. — sbi
– sbi, Commented Apr 29, 2010 at 17:39

kennytm · Accepted Answer · 2010-04-29 17:36:10Z

18

return printSeries(n-3) + printSeries( (n-2) + printSeries(n-1) );
//                                     ^^^^^^^^^^^^^^^^^^^^^^^^

Incorrect nesting of parenthesis causes infinite recursion, which leads to stack overflow (segfault).

Consider when n = 4,

f(4) = 1 + f(2 + f(3))
     = 1 + f(2 + 3)
     = 1 + f(5)
     = 1 + [ f(2) + f(3 + f(4)) ]
     = ...

answered Apr 29, 2010 at 17:36

kennytm

526k110 gold badges1.1k silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

the_drow Over a year ago

Shouldn't that throw an exception?

kennytm Over a year ago

@the_drow: Why should it throw an exception?

Rich Adams Over a year ago

@the_drow: Why? It's perfectly valid, it just causes infinite recursion.

sbi Over a year ago

@the_drow: Unfortunately, there's no std::programmer_error in C++. You might want to propose it, though.

the_drow Over a year ago

I meant a stackoverflow exception

|

Owen S. · Accepted Answer · 2010-05-04 02:25:59Z

4

The parentheses problem mentioned above is the source of the infinite recursion. But there's another problem with the code even if you fix the parentheses for case 5 to be like case 4:

printSeries(4) recursively invokes printSeries 3 times.
printSeries(5) recursively invokes printSeries 6 times.
printSeries(6) recursively invokes printSeries 12 times.
printSeries(10) recursively invokes printSeries 156 times.
printSeries(20) recursively invokes printSeries 69747 times.
printSeries(50) recursively invokes printSeries over 6 trillion times.

In other words, your code is doing way more work than it should. Do you see why?

edited May 4, 2010 at 2:25

answered Apr 29, 2010 at 21:28

Owen S.

7,8851 gold badge30 silver badges44 bronze badges

Collectives™ on Stack Overflow

Segmentation fault C++ in recursive function

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related