Recursive Function Not Wokring

[yougene]

I'm trying to write a program that assigns seats in either first class(seats 1 through 5) or economy class(seats 6 through 10) using the random function. The array seats[ SIZE ] is supposed to hold a value of 0 or 1 to indicate whether it is already taken or not. My problem is when the random seat is already taken I want the function Assignseat() to run itself again recursively to try and find another seat. For some reason it won't run itself recursively. Any ideas?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10

int assignSeat( int [], int );

int economyCounter = 0;
int firstCounter = 0;
int main()
{
   srand( time(NULL) );

   int seats[ SIZE ] = { 0 };
   int input;

   while (input != -1) {
      printf("Enter 1 for first class, 2 for economy class or -1 to quit: ");
      scanf("%d", &input);
/*
      if (input == 1 || input == 2)
         assignSeat( seats, input );
*/
      if (input == 1) {
         if (firstCounter < 5)
            printf("You have seat %d in first class\n\n", assignSeat( seats, input ) );
         else
            printf("There are no more first class seats\n");
      }
      else if (input == 2)
         printf("You have seat %d in economy class\n\n", assignSeat( seats, input ) );
      else if (input == -1)
         continue;
      else
         printf("You must enter 1, 2, or -1\n");
   }

   return 0;
}



int assignSeat( int seatNumber[], int class )
{
   int i;
/*
   if (class == 1) {
      i = rand() % 5 + 1;

      if (seatNumber[ i ] != 1) {
         seatNumber[ i ] = 1;

         ++firstCounter;
         printf("counter: %d\n", firstCounter);
      }

      else if (firstCounter < 5)
         assignSeat( seatNumber, class );
   }
*/

   if (class == 1) {
      i = rand() % 6 + 1;
      if (seatNumber[ i ] == 0) {
         seatNumber[ i ] = 1;
         ++firstCounter;
      }
      else
         assignSeat( seatNumber, 1 );
   }

   else if (class == 2) {
      i = rand() % 6 + 5;
      if (seatNumber[ i ] != 1)
         seatNumber[ i ] = 1;
      else
         assignSeat( seatNumber, 2 );
   }

   return i;
}

[matsp]

Right,

there are several problems with your recursive function:
1. You are passing teh "seats" as an array into the function, which means that every time you call the function, you pass a new copy of the "seats" variable - not the original variable. This in turn means that no modifications to the "seats" array gets done to the original array, only to the copy.

2. You can get "seat 6" in first class.

3. the variable "input" may actually be -1 on the first try, which would be somewhat annoying, because no one would get a chance to get a seat assigned. Either initialize the variable, or use "do ... while(input != -1)" instead.

4. You don't return the correct seat when you recurse - so you get the same seat as was assigned before.

There's also some room for improvement in the sense that you wouldn't have to use hard-coded constants when recursing, and have two calls that recurse.

--
Mats

[foxman]

1. Actually, matsp, i think you are making a mistake when you say

This in turn means that no modifications to the "seats" array gets done to the original array, only to the copy.

I'm sure you know that when you pass an array you pass in fact the adress of the first element of the array, so there's no copy involve in this


2. You are writing out of bond of the seats array. As you can see

i = rand() % 6 + 5;  // this means the min value is 5 and the max value is 5+5 = 10

Same thing apply to the first element of the array which will never be written

i = rand() % 6 + 1;  // min value is 1

3. Also, i might be wrong for this, but this code

int seats[ SIZE ] = { 0 };

only initialize the first element of the arrray to 0, every other elements will have some "garbage" value.


4. Another thing about your recursive function: it could/will eventually lead to an infinite recursive function call. You should do some entry validation for this to not happen.

[matsp]

1. Actually, matsp, i think you are making a mistake when you say I'm sure you know that when you pass an array you pass in fact the adress of the first element of the array, so there's no copy involve in this

Yes, you are right - I got myself confused (as I always use the "int *" way to pass arrays, not the "int []").

And yes, passengers in first and second class may get the same seat, the second class seat assignment will crash/hang the system due to infinite recursion if there is no seat available.

--
Mats

[MacNilly]

I'm trying to write a program that assigns seats in either first class(seats 1 through 5) or economy class(seats 6 through 10) using the random function. The array seats[ SIZE ] is supposed to hold a value of 0 or 1 to indicate whether it is already taken or not. My problem is when the random seat is already taken I want the function Assignseat() to run itself again recursively to try and find another seat. For some reason it won't run itself recursively. Any ideas?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10

int assignSeat( int [], int );

int economyCounter = 0;
int firstCounter = 0;
int main()
{
   srand( time(NULL) );

   int seats[ SIZE ] = { 0 };
   int input;

   while (input != -1) { // Bad practice, you have not initialized input. Make your loop controller either 0 or 1.
      printf("Enter 1 for first class, 2 for economy class or -1 to quit: ");
      scanf("%d", &input);
/*
      if (input == 1 || input == 2)
         assignSeat( seats, input );
*/
      if (input == 1) {
         if (firstCounter < 5) // WHy a global variable here? NO need for any global variables, EVER
            printf("You have seat %d in first class\n\n", assignSeat( seats, input ) );
         else
            printf("There are no more first class seats\n");
      }
      else if (input == 2)
         printf("You have seat %d in economy class\n\n", assignSeat( seats, input ) );
      else if (input == -1)
         continue;
      else
         printf("You must enter 1, 2, or -1\n");
   }

   return 0;
}



int assignSeat( int seatNumber[], int class )
{
   int i;
/*
   if (class == 1) { // Maybe a comment here, or an enum class_type CLASS_FIRST = 1, CLASS_ECONOMY = 2 would be more readable...
      i = rand() % 5 + 1;

      if (seatNumber[ i ] != 1) {
         seatNumber[ i ] = 1;

         ++firstCounter; // again, using globals making it very confusing...
         printf("counter: %d\n", firstCounter);
      } // ok, so you printed the global variable firstCounter (uh, first count of what???) and made some random value in seats array = 1...

      else if (firstCounter < 5) // wtf?
         assignSeat( seatNumber, class );
   }
*/

   if (class == 1) {
      i = rand() % 6 + 1;
      if (seatNumber[ i ] == 0) {
         seatNumber[ i ] = 1;
         ++firstCounter;
      }
      else
         assignSeat( seatNumber, 1 );
   }

   else if (class == 2) {
      i = rand() % 6 + 5;
      if (seatNumber[ i ] != 1)
         seatNumber[ i ] = 1;
      else
         assignSeat( seatNumber, 2 );
   }

   return i;
}

Code makes no sense. Full of mad bugs. If I was you, I'd delete that code and start a full rewrite.

Recursive functions follow a basic pattern. They have a [B} BASE CASE [/B] that ends the recursion. If the base case condition is not met, then they call themselves again, passing the arguments from the previous call.

IMO, in this simple problem recursive function is just a waste of time. Doing the same thing, get rid of those ugly globals and unsound recursive functions and we'll talk again.

[MacNilly]

Well I added a lot of comments in your code but they are hidden unless you copy-paste that code into an editor.

At any rate, when people choose a first class, just assign them the next available seat, not some random seat. Just keep a counter of nextseat. = 0. There is nothing random about it. Fill one seat at a time until it's full. Then that's your base_case if you MUST use recursion.

[yougene]

>>MacNilly

This is probably the worst code I've written I'd have to admit. seatNumber[ i ] is set to 1 or 0 depending on whether the seat has been assigned to someone yet or not. If it hasn't been assigned yet, seatNumber[ i ] is set to 1 and then a message stating the seat number( i ) and what class it's in is printed. If the seatNumber is already taken(equals 1) the function is supposed to run again until it finds an available seat. So the base case is seatNumber[ i ] = 0(having the random seat being available).

I would have used sequential assignment but the exercise requires me to use a random number and to check seat status.


>>matsp
"4. You don't return the correct seat when you recurse - so you get the same seat as was assigned before."

So since the returned i from the last recursion of assignSeats has no where to go, the i from the first run of assignSeats is returned?



Thank you for your time guys.

[yougene]

^ #4 nailed it. In the midst of tinkering I switched the function type from void to int, but didn't adjust accordingly.

[ssharish2005]

May be u should have sturctured the array properly. Like say seat from 0 to 4 is for First class and the 5 to 9 is for second class.

And then when you generate the random rumber you should check the value before index the value with the array, that is it within the firstclass or second range. So for example

i = Generate random number

if(Firstclass)
{
     Check(i >=0 && i < 5)
       Then index the i value with seat
}

Same applies to the second class seat instead of 0 to 4, it should be 5 to 9.

ssharish2005

[yougene]

Definately some good habits I should practice. Sometimes I don't take enough time on these exercises.

[iMalc]

3. Also, i might be wrong for this, but this code

int seats[ SIZE ] = { 0 };

only initialize the first element of the arrray to 0, every other elements will have some "garbage" value.

As a matter of fact you are wrong about that. It will initialise all values to zero. Note that not even the first one need be explicitly specified, just {} will do.

[robatino]

> Note that not even the first one need be explicitly specified, just {} will do.
I believe this is only true in C++, and that in C, at least one initializer is required (unfortunate since it's more elegant to allow an empty list and have all elements initialized the same way).

int main(void) {
  int a[5] = {};
  return 0;
}

gcc -W -Wall -ansi -pedantic foo.c
foo.c: In function ‘main’:
foo.c:2: warning: ISO C forbids empty initializer braces
foo.c:2: warning: unused variable ‘a’

[foxman]

It's fun to learn that. In fact i just did some test to verify and check what is the exact behaviour of this and i might be the only one to discover this at this time but when you do something like

int tableau[10] = { 1 };   // tableau means array in english

well it initialize the first element to 1 and all the others to 0.

I simply didn't know.

Oh and by the way, the same thing apply for the empty curly brace on my compiler. It gives an error.