im having BAD trouble with this recursion

This is a discussion on im having BAD trouble with this recursion within the C Programming forums, part of the General Programming Boards category; ok I CANT understand the logic of this recursion the function is this: Code: void f(int A[], int n, int ...

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    33

    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!!!!!!!!!???????????

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by jackhasf View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Registered User
    Join Date
    Feb 2009
    Posts
    33
    Quote Originally Posted by Adak View Post
    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

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by jackhasf View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    Registered User
    Join Date
    Feb 2009
    Posts
    33
    Quote Originally Posted by MK27 View Post
    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
    Last edited by jackhasf; 01-26-2010 at 07:22 PM.

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by jackhasf View Post
    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.
    Last edited by MK27; 01-26-2010 at 07:24 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  8. #8
    Registered User
    Join Date
    Feb 2009
    Posts
    33
    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

  9. #9
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    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
    Last edited by _Mike; 01-27-2010 at 03:15 AM. Reason: See 'edit' section

  10. #10
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    > // 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  11. #11
    Registered User
    Join Date
    Feb 2009
    Posts
    33
    Quote Originally Posted by Salem View Post
    > // 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.
    Last edited by jackhasf; 01-28-2010 at 04:40 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How bad is bad
    By caroundw5h in forum A Brief History of Cprogramming.com
    Replies: 21
    Last Post: 11-12-2004, 08:26 AM
  2. Shocking(kind of)
    By Shadow in forum A Brief History of Cprogramming.com
    Replies: 25
    Last Post: 12-10-2002, 07:52 PM
  3. stack and recursion help needed!
    By LouB in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 02:19 PM
  4. recursion project
    By Psycho in forum C++ Programming
    Replies: 4
    Last Post: 03-31-2002, 02:24 PM
  5. good news and bad news
    By Garfield in forum A Brief History of Cprogramming.com
    Replies: 25
    Last Post: 10-27-2001, 07:31 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21