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