Answers/Solutions to Exercises in Chapter 5, Exercise 14

E14: The following recursive program generates and displays all bit combinations for a byte.

#include <stdio.h>

char byte[8];

void bits(int n,char byte[])
{
   int i;

   if (n == 8) { 
     for(i = 0; i < 8; i++)
      putchar(byte[i]);
     putchar('\n');
     return;
   }
   byte[n] = '0';
   bits(n+1,byte);
   byte[n] = '1';
   bits(n+1,byte);
}
    
int main()
{
   bits(0,byte);
   return 0;
}

We rewrite it using global variables instead of arguments being passed along (see below). Will it work? Try to justify your answer.

#include <stdio.h>

char byte[8];
int n;

void bits()
{
   int i;

   if (n == 8) { 
     for(i = 0; i < 8; i++)
      putchar(byte[i]);
     putchar('\n');
     return;
   }
   byte[n] = '0';
   n = n+1;
   bits();
   n = n-1;
   byte[n] = '1';
   n = n+1;
   bits();
}
    
int main()
{
   n = 0;
   bits();
   return 0;
}

A14: No, it will not work. In the correct (former) form, bits( ) is a recursive procedure that extends the possible bits combinations so far by the both possibilities for the n-th bit, and if the end is reached, the combination is displayed (it is akin to depth-first traversal of a complete binary tree of height 8.  bits( )"knows" through the argument n, that n bits has been done so far, and it will do n+1-th bit. In the latter (incorrect) version, the global n will "oscillate" between values 0 and 1.

Back to Answers/Solutions Index                          Back to Answers/Solutions for Chapter 5 Index