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

[Kurtanius21]

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

#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);
}

[stahta01]

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.

[Salem]

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).

[Kurtanius21]

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!

[stahta01]

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.

[stahta01]

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.

[stahta01]

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.

int replace_first_x( char *inputString, char *outStringA, char *outStringB);

Tim S.

[Kurtanius21]

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

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()

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

[stahta01]

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.

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;
}

[Kurtanius21]

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.

#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!

[stahta01]

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.

[stahta01]

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.