A recursion algorithm

Question

Ok, this may seem trivial to some, but I'm stuck.

Here's the algorithm I'm supposed to use:

Here’s a recursive algorithm. Suppose we have n integers in a non-increasing sequence, of which the first is the number k. Subtract one from each of the first k numbers after the first. (If there are fewer than k such number, the sequence is not graphical.) If necessary, sort the resulting sequence of n-1 numbers (ignoring the first one) into a non-increasing sequence. The original sequence is graphical if and only if the second one is. For the stopping conditions, note that a sequence of all zeroes is graphical, and a sequence containing a negative number is not. (The proof of this is not difficult, but we won’t deal with it here.)

Example: Original sequence: 5, 4, 3, 3, 2, 1, 1

Subtract 1 five times: 3, 2, 2, 1, 0, 1

Sort: 3, 2, 2, 1, 1, 0

Subtract 1 three times: 1, 1, 0, 1, 0

Sort: 1, 1, 1, 0, 0

Subtract 1 once: 0, 1, 0, 0

Sort: 1, 0, 0, 0

Subtract 1 once: -1, 0, 0

We have a negative number, so the original sequence is not graphical.

This seems simple enough to me, but when I try to execute the algorithm I get stuck.

Here's the function I've written so far:

//main
 int main ()
{
     //local variables
     const int MAX = 30;
     ifstream in;
     ofstream out;
     int graph[MAX], size;
     bool isGraph;

     //open and test file
     in.open("input3.txt");
     if (!in) {
         cout << "Error reading file. Exiting program." << endl;
         exit(1);
     }

     out.open("output3.txt");

     while (in >> size) {
         for (int i = 0; i < size; i++) {
             in >> graph[i];
         }

        isGraph = isGraphical(graph, 0, size);

        if (isGraph) {
             out << "Yes\n";
         }else
             out << "No\n";

     } 

     //close all files
     in.close();
     out.close();

     cin.get();
     return 0;
 }//end main

 bool isGraphical(int degrees[], int start, int end){

     bool isIt = false;
         int ender;      

     inSort(degrees, end);

     ender = degrees[start] + start + 1;

     for(int i = 0; i < end; i++)
            cout << degrees[i];
     cout << endl;

     if (degrees[start] == 0){
        if(degrees[end-1] < 0)
            return false;
        else
            return true;
     }
     else{

    for(int i = start + 1; i < ender; i++) {
        degrees[i]--;
    }
         isIt = isGraphical(degrees, start+1, end);
     }

     return isIt;
 }

 void inSort(int x[],int length)
 {
    for(int i = 0; i < length; ++i)
     {
         int current = x[i];
         int j;
         for(j = i-1; j >= 0 && current > x[j]; --j)
         {
                 x[j+1] = x[j];
         }
         x[j+1] = current;
     }
 }

I seem to get what that sort function is doing, but when I debug, the values keep jumping around. Which I assume is coming from my recursive function.

Any help?

EDIT: Code is functional. Please see the history if needed.

With help from @RMartinhoFernandes I updated my code. Includes working insertion sort.

I updated the inSort funcion boundaries

I added an additional ending condition from the comments. But the algorithm still isn't working. Which makes me thing my base statements are off. Would anyone be able to help further? What am I missing here?

Side remark: isn't the last one `degrees[end-1]` instead of `degrees[end]` in your stopping condition? — Howard, Sep 26 '11 at 16:52
If you want help with a recursion algorithm, you should first get help with a recursion algorithm. — Reinstate Monica - Goodbye SE, Sep 29 '11 at 11:46

score 2 · Accepted Answer · edited Jan 18 '21 at 12:34

Ok, I helped you out in chat, and I'll post a summary of the issues you had here.

The insertion sort inner loop should go backwards, not forwards. Make it for(i = (j - 1); (i >= 0) && (key > x[i]); i--);
There's an out-of-bounds access in the recursion base case: degrees[end] should be degrees[end-1];
while (!in.eof()) will not read until the end-of-file. while(in >> size) is a superior alternative.

score 0 · Answer 2 · answered Sep 26 '11 at 16:55

0

Are you sure you ender do not go beyond end? Value of ender is degrees[start] which could go beyond the value of end. Then you are using ender in for loop

for(int i = start+1; i < ender; i++){ //i guess it should be end here

answered Sep 26 '11 at 16:55

Vineet G

175
1
1
8

I'm only subtracting 1 from the first [ender] variables. I added changed it to for(int i = start+1; i < ender && i < end; i++){ , which made it so it at least didn't crash. But the algorithm is still off... – OghmaOsiris Sep 26 '11 at 17:34

score 0 · Answer 3 · answered Sep 26 '11 at 17:46

I think your insertion sort algorithm isn't right. Try this one (note that this sorts it in the opposite order from what you want though). Also, you want

for(int i = start + 1; i < ender + start + 1; i++) {

instead of

for(int i = start+1; i < ender; i++)

Also, as mentioned in the comments, you want to check if degrees[end - 1] < 0 instead of degrees[end].

A recursion algorithm

3 Answers3