CODEWITHSUNDEEP
carraysrecursion
Badshah
Badshah

Reputation: 431

Recursion does not work as wanted

I have an array and I want to fill this array using recursion. It is about the Collatz sequence. It is not necessary to know the problem to understand the code. The code I have written is the following

int recursion(long int n, int *array){
    if(*(array + n)==0){//check if I already have the length of the sequence for this n
        if((n+1)/2==(double)(n+1)/(double)2){//check if n mod 2 == 0
           *(array+n) =recursion((n+1)/2-1,array)+1;
        }       
        else{
           *(array +n)=recursion(3*n+3,array)+1;
        }
    }
    else{
         return *(array+n);
    }
}

So the idea is that if I have an array with zeros except that array[0]=1 and if I write recursion(100,array) then the function checks if at position 100 the array is zero. If it is zero, then the function checks another condition and assigns a number to array[100]. This array[100] is recursively defined. If finally it sees a an array element which is not zero, it returns this array element.

I expect that in this process of recursion for n=100, it will not only find a value for array[100], but also for some other array elements. But if I run this function in my main function, it gives for several array elements a 1 and for array[100] it is also 1, but should be a lot bigger than 1, since I am adding 1 in each recursion. I really don't see what I am overlooking here.

Upvotes: 0

Views: 102

Answers (2)

Effie
Effie

Reputation: 833

  1. Since there is no code that creates the array, are you sure that 3*n+3 is less than array length?

  2. you assign elements the values of function return:

*(array +n)=recursion(3*n+3,array)+1;

but your function doesn't always return a value. C is very strange in not requiring to check whether there actually is a return statement, and in this case compiler guesses it or something...

For gcc, compile with -Wreturn-type, then it will give you a warning:

a.c: In function ‘recursion’:
a.c:16:1: warning: control reaches end of non-void function [-Wreturn-type]
  1. I am a little bit confused from your text. You do know that array[100] is a 101-th element in the array and not 100-th, don't you?

so, assuming that n represents an index in array (that starts with 0) and Collatz is for positive numbers (starting with 1) shouldn't it be:

if( (n+1) % 2 == 0) {
    // this was right one
    array[n] = recursion ( (n+1)/2 - 1, array) + 1; 
} else {
    // this one was probably wrong
    array[n] = recursion ( 3 * (n+1) /*+ 1 - 1 */, array) + 1; 
}

and then call recursion(99,array)

Upvotes: 1

melpomene
melpomene

Reputation: 85767

One thing that's definitely wrong: You have an if in your function, but you only return a value in one of the branches. You should change

else{
     return *(array+n);
}

to

return *(array+n);

in order to make sure the function always returns a value.

By the way, you can simply write array[n] instead of *(array + n).

Upvotes: 2

Related Questions