Recursive Function Not Wokring

This is a discussion on Recursive Function Not Wokring within the C Programming forums, part of the General Programming Boards category; I'm trying to write a program that assigns seats in either first class(seats 1 through 5) or economy class(seats 6 ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    182

    Recursive Function Not Wokring

    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?
    Code:
    #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;
    }

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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

  3. #3
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    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
    Code:
    i = rand() &#37; 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
    Code:
    i = rand() % 6 + 1;  // min value is 1

    3. Also, i might be wrong for this, but this code
    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.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by foxman View Post
    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

  5. #5
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    307
    Quote Originally Posted by yougene View Post
    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?
    Code:
    #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.
    GCC on Fedora Core 10

  6. #6
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    307
    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.
    GCC on Fedora Core 10

  7. #7
    Registered User
    Join Date
    May 2006
    Posts
    182
    >>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.

  8. #8
    Registered User
    Join Date
    May 2006
    Posts
    182
    ^ #4 nailed it. In the midst of tinkering I switched the function type from void to int, but didn't adjust accordingly.

  9. #9
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,682
    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

    Code:
    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

  10. #10
    Registered User
    Join Date
    May 2006
    Posts
    182
    Definately some good habits I should practice. Sometimes I don't take enough time on these exercises.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by foxman View Post
    3. Also, i might be wrong for this, but this code
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    > 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).
    Code:
    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’

  13. #13
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    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

    Code:
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive function
    By Fork in forum C Programming
    Replies: 3
    Last Post: 10-26-2006, 11:27 AM
  2. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  3. Calling a Thread with a Function Pointer.
    By ScrollMaster in forum Windows Programming
    Replies: 6
    Last Post: 06-10-2006, 08:56 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 09:18 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21