Heap's Algorithm in C++ segmentation fault

Question

I've been working on implementing a recursive version of heap's algorithm. Here is the link to the pseudocode: http://en.wikipedia.org/wiki/Heap%27s_algorithm

Everything has been going fine until I get to the recursive part. I know I haven't put in swapping elements yet but I haven't gotten that far. The run fails without showing an error until I use the gcc debugger which tells me that there has been a segmentation fault. Here is my code:

#include <string>
#include <iostream>
using namespace std;

string* permute(int n, string array[2]){
    if (n==1){
        return array;
    }
    else{
        for(int c=1; c<=n;c++){
            permute(n--,array);
        }
    }
}

int main() {
    string array[2]={"a","b"};
    permute(2,array);
    return 0;
}

How is the return statement in the else part of function permute? And why are you decrementing n inside the loop which runs from 1 to n? — barak manos
– barak manos, Commented Jul 7, 2014 at 14:35

barak manos · Accepted Answer · 2014-07-07 14:46:11Z

5

Let aside the fact that the entire implementation seems wrong, the direct reason for the runtime exception that you're experiencing is your recursive call to permute(2,array), which eventually leads to a stack overflow. This happens because you are calling it with n-- instead of --n (or more precisely, n-1).

edited Jul 7, 2014 at 14:46

answered Jul 7, 2014 at 14:38

barak manos

30.3k10 gold badges67 silver badges117 bronze badges

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

2 Comments

user2514631 Over a year ago

Thank you very much, I'm a beginner so help is always appreciated!

barak manos Over a year ago

@user2514631: You're welcome :) There's a lot more work to be done up there.

lifeOfPI · Accepted Answer · 2014-07-07 14:39:16Z

2

try permute( --n, array ) you are passing a copy of 2 not the decrement

answered Jul 7, 2014 at 14:39

lifeOfPI

3181 silver badge8 bronze badges

Comments

Luca Davanzo · Accepted Answer · 2014-07-07 14:39:03Z

1

You have to use prefix subtraction:

change:

 permute(n--,array);

to:

 permute(--n,array);

In this way, you first decrement 'n' and then call permute.

In first case you never subtract and you have an infinite recursion.

answered Jul 7, 2014 at 14:39

Luca Davanzo

21.6k15 gold badges124 silver badges152 bronze badges

Comments

Paul Evans · Accepted Answer · 2014-07-07 14:39:27Z

0

You shouldn't be post-decrementing n in your recursive call, pre-decrement instead:

permute(--n,array);

answered Jul 7, 2014 at 14:39

Paul Evans

27.7k3 gold badges41 silver badges56 bronze badges

Collectives™ on Stack Overflow

Heap's Algorithm in C++ segmentation fault

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related