im having BAD trouble with this recursion

ok I CANT understand the logic of this recursion

the function is this:

Code:

void f(int A[], int n, int B[]){
     
     if (!n)
             f(A,n-1,B);
     if (A[n-1]!=B[n-1])
                        A[n-1]=A[n-1]+B[n-1];
     }

i think the output is obvious for n!=0, i tried to see the output for n=0

Code:

#include <stdio.h>

void f(int A[], int n, int B[]){
     
     if (!n)
             f(A,n-1,B);
     if (A[n-1]!=B[n-1])
                        A[n-1]=A[n-1]+B[n-1];
     }

int main(void){
    
   int x[3] = {1,2,3};
    int y[3] = {2,3,4};
   
   
    int i;
    
    f(x,0,y);
    
    for (i=0;i<3;i++){
        printf("%d ",x[i]);
        }
    printf("\n");
    for (i=0;i<3;i++){
        printf("%d ",y[i]);
        }
    
    getchar();
    
    return 0;
    
}

the output here is

Code:

1 2 3
2 3 3

I CANT understand WHY, what's the logic behind this??????????

but then if I change the order of x,y declaration:

Code:

#include <stdio.h>

void f(int A[], int n, int B[]){
     
     if (!n)
             f(A,n-1,B);
     if (A[n-1]!=B[n-1])
                        A[n-1]=A[n-1]+B[n-1];
     }

int main(void){
     
    int y[3] = {2,3,4};
   int x[3] = {1,2,3}; // notice how i put x after y
   
    int i;
    
    f(x,0,y);
    
    for (i=0;i<3;i++){
        printf("%d ",x[i]);
        }
    printf("\n");
    for (i=0;i<3;i++){
        printf("%d ",y[i]);
        }
    
    getchar();
    
    return 0;
    
}

the output is:

Code:

1 2 3
2 3 4

what's going on!!!!!!!!!???????????

I am sworn to secrecy, Jack.

Really, get yourself some pieces of paper and a pencil, and work it out by hand. You'll learn more than by having someone post about it.

Learning by doing (as long as it doesn't take forever), is the best way to go. You *will* remember it better.

Originally Posted by jackhasf

I CANT understand WHY, what's the logic behind this??????????

No offence, but this code does not have any logic to find behind it:

Code:

void f(int A[], int n, int B[]){
     
     if (!n)
             f(A,n-1,B);
     if (A[n-1]!=B[n-1])
                        A[n-1]=A[n-1]+B[n-1];
     }

Okay, so if n is zero, we run f with n = -1. Then we would compare A[-2] to B[-2]. Those are completely invalid subscripts. End of story.

If you did not write this code, forget about it. If you did, perhaps you should explain what you are trying to do, and someone can point you in another direction.

Originally Posted by Adak

I am sworn to secrecy, Jack.

Really, get yourself some pieces of paper and a pencil, and work it out by hand. You'll learn more than by having someone post about it.

Learning by doing (as long as it doesn't take forever), is the best way to go. You *will* remember it better.

hi thanks for the answer

i swear i ve spent more than 5 hours to understand what it does but i just can't

i can't understand why the output can be different when declaring the arrays in a different way, first x then y, or first y then x

is there a difference if we say

int x;
int y;

or

int y;
int x;

???? This is what i can't get here, and it's driving me crazy

Originally Posted by jackhasf

hi thanks for the answer

???? This is what i can't get here, and it's driving me crazy

You are still trying to discuss this as if it makes some kind of sense. IT DOESN'T. This code is NOT USEFUL FOR ANY PURPOSE.

A spambot could write this code, and probably randomly generate questions involving C syntax about it. Sorry. Try again.

Originally Posted by MK27

No offence, but this code does not have any logic to find behind it:

Code:

void f(int A[], int n, int B[]){
     
     if (!n)
             f(A,n-1,B);
     if (A[n-1]!=B[n-1])
                        A[n-1]=A[n-1]+B[n-1];
     }

Okay, so if n is zero, we run f with n = -1. Then we would compare A[-2] to B[-2]. Those are completely invalid subscripts. End of story.

If you did not write this code, forget about it. If you did, perhaps you should explain what you are trying to do, and someone can point you in another direction.

my friend, thanks for the answer

you should tell this to my professor

he put this problem on our exams today and it's DRIVING ME CRAZY

that's why im asking here

thanks again

edit:

when i asked him what's the logic behind this code, he told "you should tell me"

the problem wanted us to make the same function without using recursion which i did but i cant understand the output that it gives me

Originally Posted by jackhasf

you should tell this to my professor

he put this problem to our exams today and it's DRIVING ME CRAZY

Did you transcribe it from memory? The only answer is that it is going to result in "undefined behavior". Here is an array:

Code:

int a[3];
a[0] = 1;
a[1] = 2;
a[2] = 3;

I don't see a possibility for a[-1] or a[-2] here, so the value of such a variable is "undefined" (some languages allow you to count from the end of an array using negative numbers, but C is not one of them). More or less random. Could be anything.

Maybe it was a trick question.

i don't think it was a trick question because the problem was clear

it wanted us to transform this function into another function that uses no recursion but does the same thing

nevermind, i ll just leave it as it is

thanks

Like MK27 said, this is borderline undefined behavior. The only way that code would give the output you got is under specific compiler/optimization levels/cpu types.

Now as to guess why you got the result you did:
I have noticed from experimentation that some compilers store the stack variables in reverse order of the declaration order. So the

Code:

int x[3] = {1,2,3};
int y[3] = {2,3,4};

might be compiled as y,x instead of x,y.
And assuming the compiler is using 32-bit ints and 64-bit word alignment the arrays might get laid out in memory as

Code:

         y     x
|------|---|-|---|-|------|
|rrrrRr|234|p|123|p|rrrrrr|

where 'r' is other random data used by something else and p is alignment padding.

Looking at the function call f(x,-1,y) we see that it does

Code:

if(x[-2]!=y[-2])
  x[-2] = x[-2] + y[-2];

so x[-2] points to y[2] (ie. 4) and y[-2] points to R.
If R happens to be -1 then we get y[2] = 4 + (-1) = 3 and the arrays are now x = {1,2,3}; y = {2,3,3};
On the other hand, if we don't have read access to R the program will crash..
When you reversed the declaration order of x and y you made x[-2] point to (and f() write to) data that doesn't belong to you and the arrays remains unchanged.
(Btw, writing to memory locations you have no idea what they are used for is very very bad)

So to summarize; That code is an ugly hack that will only work under very specific conditions

Edit:
Now that I think about it some more; The assignment was just to rewrite f() to not use recursion, not that the program had to actually work..
Maybe the professor assumed the program would crash so you had to rewrite f() without running the program to see what it does

> // notice how i put x after y
> what's going on!?
Have you shown these results to your "professor". I use the term advisedly, for it seems that they're clueless.

When you change something like the declaration order, and the results come out different, then that's solid evidence for a major screw-up in the code.

As MK27 has already noted, you're accessing outside the array.
Trying to convert it is meaningless, because it doesn't do anything reliably at the moment.

First, get your prof to provide you with a bug-free program, then we can talk.

Originally Posted by Salem

> // notice how i put x after y
> what's going on!?
Have you shown these results to your "professor". I use the term advisedly, for it seems that they're clueless.

When you change something like the declaration order, and the results come out different, then that's solid evidence for a major screw-up in the code.

As MK27 has already noted, you're accessing outside the array.
Trying to convert it is meaningless, because it doesn't do anything reliably at the moment.

First, get your prof to provide you with a bug-free program, then we can talk.

no i haven't showed him anything yet

but I guess I will. I lost 1 hour while taking the exam trying to understand the reason why he would do something like this

well about making the function without recursion

for n!=0 we will have 0 in the if statement so the n will remain n, that means that the function will make just this if statement

Code:

if (A[n-1]!=B[n-1]){
       A[n-1]+=B[n-1];
}

this will give normal results i guess, since if we have for example n=1 it will check the first element of both arrays, but again, we have to know if the user enters n>(number of elements of the arrays)+1 because then we will be checking elements that do not exist(they do, but with no specific values).

then for n=0 the if will be true, and then n will become n-1, the if will be false and will do the checking for n-2

so

Code:

if (A[n-2]!=B[n-2]){
   A[n-2]+=B[n-2];
}

but again, here we can get negative elements, that's why I was scratching my head for more than an hour because I thought I was the wrong here(maybe I still am, not 100% sure).

ps: _Mike, thanks for the explanation, it's the first time I hear this, very interesting.