Like Tree1Likes
  • 1 Post By Salem

Help with Recursion. I'm so lost on this homework problem.

This is a discussion on Help with Recursion. I'm so lost on this homework problem. within the C Programming forums, part of the General Programming Boards category; Here's the problem description: “Write a recursive function that displays all the binary (base 2) numbers represented by a string ...

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    33

    Help with Recursion. I'm so lost on this homework problem.

    Here's the problem description:

    “Write a recursive function that displays all the binary (base 2) numbers represented by a string of xs, 0s, and 1s. The xs represent digits that can be either 0 or 1. For example, the string 1x0x represents the numbers 1000, 1001, 110, 1101. The string xx1 represents 001, 011, 101, 111.”
    Additional comments: The program has only two functions, main() and display(), but your display() may call other functions. The number will be no longer than 79 digits. Hint: Start with short strings, i.e., "0", "1", "x", "01", "00", "0x","1x", "xx", and reason out what would be necessary for them.

    EXAMPLES
    Binary number: 1xx01
    10001
    10101
    11001
    11101

    Binary number: 11x0x11xx
    110001100
    110001101
    110001110
    110001111
    110011100
    110011101
    110011110
    110011111
    111001100
    111001101
    111001110
    111001111
    111011100
    111011101
    111011110
    111011111

    Note: Your output does not need to have same order as above.

    Attempt at solution: I've been spending a lot of time trying to figure recursion out. I've gotten closer, and my understanding of function stacks is getting better. I just get so lost with all the function calls. I try to visualize in my head what all the function calls are going to do once the recursion is over, but I can't keep track. Anyone have a good way to visualize this?

    I spoke to my instructor about this. His clues were to travel from right to left, first placing 1s in all the x positions, then use function stacks to replace the previous x positions with 0s and 1s. Here's my work so far. I'm at a loss of how to make this thing work. Please help!

    -Thanks

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int display( char *string1, int size );
    
    int main()
    
    {
      char string[80];
      int i, size;
    
      printf("Binary number: ");
      fgets( string, 80, stdin);
      for ( i = 0 ; i < 80 ; i++ )
        if ( string[i] == '\n' )
          string[i] = '\0';
      size = strlen( string );
      display( string, size - 1 );
      return(0);
    
    }
    
    int display( char *string, int i )
    
    {
      if ( i == 0 )
      {
        return 0;
      }
      if ( string[i] != 'x' )
      {
        i -= 1;
        display( string, i );
        return 0;
      }
      if ( string[i] == 'x' )
      {
        string[i] = '0';
        i -= 1;
        display( string, i );
        printf("%s\n", string );
        i += 1;
        string[i] = '1';
        printf("%s\n", string );
        return 0;
      }
      return(0);
    }

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    2,747
    Did the instructor mention or cover strdup or malloc in recent courses?

    Because, I am not seeing a easy solution that uses recursion in a useful manner without either strdup or malloc functions.

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,755
    If the first call is
    display("11x0x11xx");

    Then the recursive calls would be
    display("1100x11xx");
    display("1110x11xx");

    You only need to be able to find the first 'x' in a string.

    If you can't find an x, then print the string (and don't call the function recursively).
    stahta01 likes this.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Oct 2012
    Posts
    33
    The instructor said there is no need for malloc.

    Do you think you could elaborate further Salem? An if statement would get me first x, then how do I create two recursions, one for the 0, and another for the 1? I can't seem to fathom how to make the Recursion change the whole string without printing any x's. Keep in mind I am a total Recursion newb!

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    2,747
    Quote Originally Posted by Kurtanius21 View Post
    The instructor said there is no need for malloc.
    You have not covered strdup being needed or not.

    This is a case where I think C++ string type would make the recursion simple to write while using C-string (char array) type is hard to write.

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    2,747
    Quote Originally Posted by stahta01 View Post
    You have not covered strdup being needed or not.
    I thought of a way to do it using strcpy and two local variables (char arrays).

    I would think about using the suggested replace_first_x() function; suggested by other related assignments on the web.
    http://www.eecs.wsu.edu/~aofallon/cp...labs/Lab11.htm

    This seems like a poor problem to solve using recursion and C; but, all of C solutions can not be elegant.

    Links that might help
    http://www.cplusplus.com/reference/cstring/strcpy/
    http://www.cplusplus.com/reference/cstring/strchr/


    Tim S.
    Last edited by stahta01; 12-06-2012 at 05:00 AM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    2,747
    My solution was a lot more elegant than I expected.

    @Kurtanius21: If you want help you need to respond with updated code and questions.

    I strongly suggest making the suggested helper function replace_first_x.

    The function prototype I used. It returns 0 if no x is found or 1 if an x is found and replaced.
    Code:
    int replace_first_x( char *inputString, char *outStringA, char *outStringB);
    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  8. #8
    Registered User
    Join Date
    Oct 2012
    Posts
    33
    I'm trying to follow your suggestion stahta. I'm still having trouble. I'm trying to implement the replace_first_x() function as you suggested. Here's what I got
    Code:
    int replace_first_x( char *inputstring, char *outstringA, char *outstringB )
    
    {
      char *pch;
    
      pch = strchr(inputstring, 'x');
      while ( pch != NULL)
      {
        *pch = '1';
        strcpy(outstringA, inputstring );
        *pch = '0';
        strcpy(outstringB, inputstring);
        return 1;
      }
      return 0;
    }
    Confusion: I'm guessing no printf statement should go inside this function, because the inputstring should have x's in it. Fine. But I'm not getting good printfs when I run it through display()

    Code:
    int display( char *string )
    
    {
    
      char stringA[80], stringB[80];
    
      if ( replace_first_x(string, stringA, stringB) == 0 )
        return 0;
      display(string);
      printf("%s\n", stringA);
      return(0);
    
    }
    I'm just trying to test A. My output is:

    Binary number: 1xx1
    1011
    11x1



    Please help!
    -Thanks
    Last edited by Kurtanius21; 12-06-2012 at 08:19 PM.

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    2,747
    Because you did some work; I fixed the two/three obvious errors.

    1. replace_first_x should only replace the first x.
    2. print string if no x was replaced
    3. do NOT do recursion with "string" variable.

    NOTE: The recursion step needs to always be done with input closer to the final solution or you get an program that runs forever or crashes.

    You still need to fix the rest of the issues.

    Tim S.

    PS: I am not likely to help this much in the future.

    Code:
    int display( char *string )
    {
    
      char stringA[80], stringB[80];
    
      if ( replace_first_x(string, stringA, stringB) == 0 ){
        printf("%s\n", string);
        return 0;
      }
      display(stringA);
      return(0);
    }
    
    
    int replace_first_x( char *inputstring, char *outstringA, char *outstringB )
    {
      char *pch;
    
      pch = strchr(inputstring, 'x');
      if ( pch != NULL)
      {
        *pch = '1';
        strcpy(outstringA, inputstring );
        *pch = '0';
        strcpy(outstringB, inputstring);
        return 1;
      }
      return 0;
    }
    Last edited by stahta01; 12-06-2012 at 08:51 PM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  10. #10
    Registered User
    Join Date
    Oct 2012
    Posts
    33
    Wow! It works if I add the display(stringA) after the display(stringB)! I really don't have any idea why! Anyone care to explain how this thing works? I really want to understand recursion, not just hope and pray the thing works if I add a line.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int display( char *string );
    int replace_first_x( char *inputstring, char *outstringA, char *outstringB );
    
    int main()
    
    {
      char string[80];
      int i;
    
      printf("Binary number: ");
      fgets( string, 80, stdin);
      for ( i = 0 ; i < 80 ; i++ )
        if ( string[i] == '\n' )
          string[i] = '\0';
      display( string );
      return(0);
    
    }
    
    int display( char *string )
    
    {
    
      char stringA[80], stringB[80];
    
      if ( replace_first_x(string, stringA, stringB) == 0 )
      {
        printf("%s\n", string);
        return 0;
      }
      display(stringB);
      display(stringA);
      return 0;
    }
    
    int replace_first_x( char *inputstring, char *outstringA, char *outstringB )
    
    {
      char *pch;
    
      pch = strchr(inputstring, 'x');
      while ( pch != NULL)
      {
        *pch = '1';
        strcpy(outstringA, inputstring );
        *pch = '0';
    strcpy(outstringB, inputstring);
        return 1;
      }
      return 0;
    }
    -Thanks Stahta!

  11. #11
    Registered User
    Join Date
    May 2009
    Posts
    2,747
    I suggest stepping through the program using the debugger; to me it is obvious how it works.
    But, you really need to understand recursion.

    I am far from a recursion expert; but, the factorial example needs to be understood before you try this more advance problem.

    Do you understand the factorial example?

    If not learn the basics of recursion and then look at this again.

    I feel like I gave you too much of the answer now.

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  12. #12
    Registered User
    Join Date
    May 2009
    Posts
    2,747
    To write a valid recursion you need.

    1. A stopping condition
    2. A recursive step(s)
    3. The recursive step(s) must not be done with the exact same input parameters as was passed into the recursive function.
    3a If the variables are the same, the data in the variables must be different.
    4. The recursive step(s) should be closer to being done than what was passed into the recursive function.

    The steps 3 & 4 above was primarily learned from trial and error; it could be wrong and is likely incomplete.

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursion difficulties, very lost
    By LearnOnTheFly in forum C Programming
    Replies: 10
    Last Post: 03-27-2012, 09:15 PM
  2. Homework help: Sudoku and "explosive recursion"
    By green_ghoul in forum C Programming
    Replies: 13
    Last Post: 11-22-2011, 11:16 PM
  3. Problem with homework
    By somniferium in forum C Programming
    Replies: 21
    Last Post: 10-15-2011, 01:09 PM
  4. Replies: 27
    Last Post: 10-11-2006, 05:27 AM
  5. homework problem
    By Unregistered in forum C++ Programming
    Replies: 5
    Last Post: 08-09-2002, 08:12 PM

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