program help

[red999]

Hi, I am writing a program that allows a user to enter a string of 0s, 1s, and x's. The program will then print out all of the possible combinations that a binary number can have with the string.

Example:
If the input is 1xx0
The output would be
1000
1010
1100
1111

The part that I am having trouble on is that I need to write this program using recursion. I'll let you guys know that I am terrible at recursion =(. Any hints or tips about how I should approach this program would be appreciated. Thanks

#include <stdio.h>
#include <string.h>
#define MAX_SIZE 50

// I may need this
/*int find_x(char number[]){
    int i, loc_of_x;
    for(i= strlen(number) - 1; i >= 0; i--){
        if (number[i] == 'x'){
           loc_of_x = i;
           return loc_of_x;}
        }
    return 0;
    }  */
   
int count_x(char number[]){
    int i, number_of_x;
    for(i=0, number_of_x = 0; (i < strlen(number)); i++){
        if (number[i] == 'x')
           ++number_of_x;
        }
    return number_of_x;
    } 
    
void display(char number[]){
    if (count_x(number) == 0)
       printf("%s\n", number);      
}
        
int main(){
    char number[MAX_SIZE];
    int number_of_x, i;
    
    printf("Binary number: ");
    scanf("%s", number);
    display(number);
    return 0;
    }

[jephthah]

okay, i'll admit it.

I, too, am terrible at recursion.

[red999]

Heh, I tried some stuff =/

#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100

void find_x(char number[], int pos_of_x[]){
    int i, j;
    for(i = strlen(number) - 1 , j = 0; i >= 0; i--){
        if (number[i] == 'x'){
           pos_of_x[j] = i;
           ++j;}
        }
    }
   
int count_x(char number[]){
    int i, number_of_x;
    for(i=0, number_of_x = 0; (i < strlen(number)); i++){
        if (number[i] == 'x')
           ++number_of_x;
        }
    return number_of_x;
    } 
    
void display(char number[], int number_of_x, int pos_of_x[], int i, int n){   
     char first[MAX_SIZE], second[MAX_SIZE];
     if (n == 0)
         printf("%s\n", number);
     else if (number_of_x != 0){
          strcpy(first, number); strcpy(second,number);
          second[pos_of_x[i]] = '1';
          printf("%s\n", second);
          display(number, number_of_x - 1, pos_of_x, i+1, n);
          } 
}
           
int main(){
    char number[MAX_SIZE];
    int num_of_x, i, pos_of_x[MAX_SIZE], n;
    
    printf("Binary number: ");
    scanf("%s", number);
    num_of_x = count_x(number); n = count_x(number);
    if (num_of_x != 0) {
        find_x(number, pos_of_x);
        for (i = 0; i < num_of_x; ++i){
            number[pos_of_x[i]] = '0';}
        printf("%s\n", number);
        }
    display(number, num_of_x, pos_of_x, 0, n);
    scanf("%d", &i);
    return 0;
    }

[VatooVatoo]

As I understand this is not a recursive problem because

F(1) is not defined. Also I cant find any
F(a) = F(a+n) is not possible

so this is not recursive.

[adarshcu]

As i see it , the program is recursive , but i guess it gives partial output. The problem may probably be that u are assigning either 1's or 0's to the positions of x, not a combination of both. Let me know if i ve made a mistake.

[red999]

I figured it out, Thanks

[jephthah]

what was the answer? i'm curious.

[red999]

Turns out that when I turned the 'x' into '0' in my main function, it led me into the wrong direction. This is the final program

void display(int size, int start, char input[], char output[]){   
     if (start == size + 1){
        printf("%s\n", output);
        return;
     }
     if (input[start] != 'x') {
        output[start] = input[size];
        display(size, start+1, input,output);
     } else {
       output[start] = '0';
       display(size, start+1, input,output);
       output[start] = '1';
       display(size, start+1, input,output);
       } 
}
           
int main(){
    char number[MAX_SIZE], out[MAX_SIZE];
    int i;
    
    printf("Binary number: ");
    scanf("%s", number);
    for (i = 0; number[i] != '\0'; ++i){}
    display(i, 0, number, out);
    scanf("%d", &i);
    return 0;
    }

[adarshcu]

In the above code that u ve written .
should it not be

if (input[start] != 'x') {
        output[start] = input[start];
        display(size, start+1, input,output);

if ur prog is working fine. cool one !!

[csurfer]

Your program may be right and giving the right output too but try to use the inbuilt "C" functionality more.Because even after using recursion if you are doing so much work its nothing but "Crime Against Recursion".Try this...

#include<stdio.h>
#include<string.h>
#define MAXSIZE 10
void display(char c,int cnt,int i,char num[],int pos[])
{
     char temp;
     temp=num[pos[i]];
     num[pos[i]]=c;
     if(cnt-1!=0)
     {
               display('0',cnt-1,i+1,num,pos);
               display('1',cnt-1,i+1,num,pos);
     } 
     else printf("\n%s",num);
     num[pos[i]]=temp;
}         

int main(void)
{
    int i,j,nox=0,pos[MAXSIZE];
    char num[MAXSIZE];
    printf("Enter Binary Number : ");
    scanf("%s",num);
    for(i=0;i<strlen(num);i++) 
               if(num[i]=='x')nox++;
    if(nox!=0)
    {
              for(i=0,j=0;i<strlen(num);i++) 
                                if(num[i]=='x')pos[j++]=i;
              display('0',nox,0,num,pos);
              display('1',nox,0,num,pos);
    }
    else printf("%s",num);
    return 0;
}

P.S : Usage of functions is recommended only when a set of instructions are used again and again,to increase readability and to reduce error.Their usage for just two lines of codes as in this function just increases the compile time and gives no noticeable benefit.

[JJS]

First, this is a poor example for recursion, a sort algorithm would make much more sense. So, I assume this is for a class. Anyhow, I would expect to have to handle the case of 1x0x1, which means that you have to replace the x's by putting them in the correct location. The pseudo code for that would be:

main () {
  char number[MAX_SIZE];
  power = count_x();
  max_val = 2 ^^ power;
  replace_x(number, max_val, 0);
}

replace_x(number, max_val, cur_val) {
// You can figure this out
  print_f("%s",  substitute_x(number, cur_val));
// The key is to have a way to end the recursion
  if (cur_val < max_val) {
// For this task, you want all binary values for the x's
    replace_x(number, max_val, cur_val + 1);
  }
}

Later . . . Jim