Question

How to rewrite the bin() function below using recursion instead of a for loop in C?

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdint.h>

char* bin(int x, int i);

int main(int argc, char **argv) {
char* binstr = bin(10, 0);
printf("%s\n", binstr);
free(binstr);

return 0;
}

char* bin(int x, int i){
int bits = log10((double) x)/log10(2)+1;
char* ret = malloc((bits+1)*sizeof(char));


for(int i = 0; i < bits; i++){
ret[bits-i-1] = (x & 1) ? '1' : '0';
x >>= 1;
}

ret[bits] = '\0';
return ret;
}

Answer 1

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <stdint.h>

char * bin(int x, int i);

int main(int argc, char ** argv) {
  char * binstr = bin(10, 0);
  printf("%s\n", binstr);
  free(binstr);

  return 0;
}

char * bin(int x, int i) {
    // since size of int is 32 bit
    // maximum no of bits in x for any positive value
    // is 31 and one bit for null character
    char* ret = malloc((32) * sizeof(char));
    int j = 0;
    bin_internal(x, ret, &j);
    ret[j] = '\0';
    return ret;
}

// this is the recursive function
// here every time we divide the number by 2
// and compute its result via recursion call for x / 2.
void bin_internal(int x, char* ret, int* j){
    if(x == 0)
        return;
    bin_internal(x >> 1, ret, j);
    ret[*j] = (x & 1)? '1': '0';
    (*j) ++;
}

OUTPUT:-

if you have any doubt, feel free to ask in the comments.