Thread: recursive functions with arrays as parameters

You're probably getting an integer overflow. A java int type is 32 bits, and overflows are guaranteed to wrap. Neither property is guaranteed in C.

Or you're mucking up the computation of array lengths. Your coding is less than clear and - to say the least - the technique is not exactly a thing of beauty. When you don't code clearly, you increase the chances of making a stupid error.

The first step would be some sane indentation.

Code:

#include<stdio.h>
void raisePowerOf2(int array[], int pow);
int main()
{
  int a[2] = { 1, -1 };
  raisePowerOf2(a, 5);

  return 0;
}

void raisePowerOf2(int array[], int pow)
{
  int i, qtnt = 0;
  for (i = 0;; i++) {
    if (array[i] == -1)
      break;
  }
  const int len = i + 1;
  int store[len + 1];

  for (i = len - 2; i >= 0; i--) {
    store[i + 1] = (array[i] * 2) % 10 + qtnt;
    qtnt = (array[i] * 2) / 10;

  }
  store[len] = -1;

  if (pow == 1) {
    for (i = 0; i < len; i++)
      printf("%i", store[i]);
  }

  if (pow > 1)
    raisePowerOf2(store, pow - 1);

}

public class NewClass4 {
  void raisePowerOf2(int array[], int pow) {
    final int len = array.length;
    int store[] = new int[len + 1];
    int qtnt = 0;
    for (int i = len - 1; i >= 0; i--) {
      store[i + 1] = (array[i] * 2) % 10 + qtnt;
      qtnt = (array[i] * 2) / 10;
    } 
    if (pow == 1) {
      for (int i = 0; i < len + 1; i++)
        System.out.print(store[i]);
    }
    if (pow > 1)
      raisePowerOf2(store, pow - 1);
  }

  public static void main(String s[]) {
    int a[] = { 1 };
    new NewClass4().raisePowerOf2(a, 5);
  }
}

The thing that strikes me as being odd is that in the C code, the for loop starts at len-2

Originally Posted by Salem

The thing that strikes me as being odd is that in the C code, the for loop starts at len-2

I think there is no problem with len-2,there I wrote 2 to exclude the last element in each array which is -1.

I have to use malloc() and free() to work with microsoft compiler. Each recursion adds a leading zero to store, even though it's not needed most of the time. After the for loop with % and /, qtnt will always be zero since store is longer than it needs to be.

Code:

#include <stdio.h>
#include <stdlib.h>
void raisePowerOf2(int array[], int pow);
int main()
{
    int a[2] = {1,-1};
    raisePowerOf2(a, 32);
    return 0;
}
 
void raisePowerOf2(int array[], int pow){
    int i, len, *store, qtnt=0;
    for(i=0; array[i] != -1 ; i++);
    len = i;
    store = malloc((len+2)*sizeof(*store));
    for(i = len-1; i >= 0; i--){
        store[i+1]=(array[i]*2)%10+qtnt;
        qtnt=(array[i]*2)/10;
    }
    store[0] = qtnt;
    store[len+1] = -1;
    if(pow > 1)
        raisePowerOf2(store, pow-1);
    else{
        for(i=0; i <= len; i++)
            printf("%d",store[i]);
    }
    free(store);
}

This version uses malloc() and realloc() to resize an allocated array only as needed:

Code:

#include <stdio.h>
#include <stdlib.h>
void raisePowerOf2(int **pa, int pow);
int main()
{
    int * a = malloc(2 * sizeof(*a));
    a[0] = 1;
    a[1] = -1;
    raisePowerOf2(&a, 32);
    free(a);
    return 0;
}
 
void raisePowerOf2(int **pa, int pow){
    int *a = *pa;
    int i, len, a2, qtnt = 0;
    for(i = 0; a[i] != -1; i++);
    len = i;
    for(i = len-1; i >= 0; i--){
        a2 = a[i]*2;
        a[i]=a2 % 10 + qtnt;
        qtnt=a2 / 10;
    }
    if(qtnt){
        len += 1;
        *pa = a = realloc(a, (len+1) * sizeof(*a));
        for(i = len; i > 0; i--)
            a[i] = a[i-1];
        a[0] = qtnt;
    }
    if(pow > 1)
        raisePowerOf2(pa, pow-1);
    else{
        for(i = 0; i < len; i++)
            printf("%d", a[i]);
    }
}