What does the computer do with 2 distinct values that need to be returned and are in the same memory scope?

Asked

Viewed 109 times

-1

I have this code with this single function, it performs the product between 'a' and 'b' that it receives from the "main" function. I would like to know how the function contained in this code deals with the return of 2 values to the "top scope", if you do a table test of what it is doing, you will realize that within the same scope it has to return two distinct values, What does she do with those values then? Sum? For if the answer is really sum, I arrived at the right result.

#include <stdio.h>

int funcao (int a, int b)
{
    if (b==0)
        return 0;

    if (b%2==0)
        return funcao(a+a, b/2);

    return funcao(a+a, b/2)+a;
}

int main () 
{
    int a, b;

    printf("Entre com 'a' e 'b' respectivamente: ");
    scanf("%d %d", &a, &b);

    printf("Resultado: %d", funcao(a,b));

    return 0;
}
c recursion

  • ...executes the two Returns... No! When finding the first instruction return the execution of the function is interrupted and processing flow is returned to the point where the function was called by returning the value of the expression passed to the return or void if nothing is past.

  • Right, so you’re saying that when it returns from a scope, it ignores the Return it’s in and goes to the second Return, which is responsible for returning some value to the top scope, that’s it?

  • I’m saying that by finding exactly the first return the function for e is returns with a value exactly at the point where the function was previously called. Everything that is after Return is ignored.

  • I understand what you say, you are explaining to me the nature of Return as a diversion of flow, and I had been asking about your performance within my code, even so I managed to understand, thank you. However, I think I did not express myself well, I will reformulate, a function that receives an x value from the previous memory scope, and within its current scope generates another value to return, which is the case of mine, what does it do with these two distinct values, sum? I’ll even edit the question

  • Where in your code are two values being returned? Here return 0; return zero, here funcao(a+a, b/2); returns the function result and here return funcao(a+a, b/2)+a; returns the result of the plus function a.

  • This is a recursive function, to better understand, I suggest reading here, here and here. In your case, nowhere does the function return 2 values, in all return's, always only one is returned. Only in some cases, the value is calculated using the result of a recursive call (but it is still a single value)

  • It’s more to the side than hkotsubo said, I made this call to understand what I say: https://ibb.co/LpTSwSh

  • 'F' would be the function, note that F(16,2) for example, receives '0' from the previous scope and generates 16 in its scope, F(8,4) receives 16 from the previous scope and generates 8 in its scope, until it returns to the beginning

  • What I want to know is if it’s a pattern the C add, for example, received 16 from the previous scope and generated 8 in the current scope, before returning to the top scope then it has to add 8+16, right?

  • That is not what you are trying to do https://ideone.com/iTOWKU . That phrase F(16,2) for example, gets '0' from the previous scope makes no sense. What is exchanged of information between function contexts are the parameters as input and value returned as output.

Show 5 more comments

2 answers

2


First, follow a reading suggestion that can help in understanding functions in general: What happens when we call a function?.

That said, I think we can first see how it would be if the funcao nay was recursive, and then we see how the recursive version doesn’t change so much. So let’s modify a little bit the funcao so that it is no longer recursive:

int funcao(int a, int b) {
    if (b == 0)
        return 0;
    if (b % 2 == 0) // em vez de chamar "funcao", estou chamando "outra_funcao"
        return outra_funcao(a + a, b / 2);
    return outra_funcao(a + a, b / 2) + a;
}

int outra_funcao(int a, int b) {
    if (b == 0)
        return 0;
    if (b % 2 == 0)
        return outra_funcao(a + a, b / 2);
    return outra_funcao(a + a, b / 2) + a;
}

outra_funcao is practically equal to funcao, with the difference that the funcao original is no longer recursive.

What happens when we call funcao(3, 1)?

In this case, the function will receive the values 3 and 1, which correspond to the parameters a and b. That is, to funcao(3, 1), we have to a=3 and b=1.

So the code doesn’t enter the first if, since b is not equal to zero. And how b is an odd number, so b % 2 is 1, so he also does not enter the second if.

Then he falls on the last return, that is:

return outra_funcao(a + a, b / 2) + a

That is, the funcao is returning only one value. This value is the result of the expression outra_funcao(a + a, b / 2) + a. And this expression is doing basically two things:

  • calling for outra_funcao(a + a, b / 2)
  • taking the result of the above call and adding a

The result of all this is the value returned by funcao. At no time has 2 values being returned. We have only one function call (outra_funcao), the result of which is summed with another value (in the case of, a), and the result of these operations becomes a single value, which is returned by funcao.

Well, what do we call it funcao(3, 1), we have to a=3 and b=1, then the expression above ends up turning:

return outra_funcao(3 + 3, 1 / 2) + 3

Which in turn turns out to be:

return outra_funcao(6, 0) + 3
// como são inteiros, 1 / 2 é "arredondado" para zero

That is, to know the result of this expression, we need to know the value of outra_funcao(6, 0).

And when we call outra_funcao(6, 0), we have a=6 and b=0 (those a and b inside outra_funcao are not the same a and b of funcao). In this case, you will enter the first if, and so it returns zero.

That is to say, return outra_funcao(6, 0) + 3 is the same as return 0 + 3, which is the same as return 3. Concluding, funcao(3, 1) returns 3.

But notice that funcao and outra_funcao do basically the same thing. So to have two redundant functions, when I can have one?

int funcao(int a, int b) {
    if (b == 0)
        return 0;
    if (b % 2 == 0)
        return funcao(a + a, b / 2);
    return funcao(a + a, b / 2) + a;
}

Now funcao is recursive (it is called within itself). Despite this, its functioning remains basically the same:

  • calling in funcao(3, 1), that is to say, a=3 and b=1
    • does not enter any of the if's, that is, falls into the return funcao(a + a, b / 2) + a
    • which in turn is the same as return funcao(3 + 3, 1 / 2) + 3, which is the same as return funcao(6, 0) + 3
    • so now I need to calculate funcao(6, 0) - is another function call (just because it called the same funcao, does not change the fact that it is another call "independent")
      • in funcao(6, 0), we have to a=6 and b=0 (how is it another function call, those a and b are not the same as the first call)
      • as b=0, enters the first if and returns zero
    • as funcao(6, 0) returned zero, the expression return funcao(6, 0) + 3 is the same as return 0 + 3, which is the same as return 3
  • that is to say, funcao(3, 1) returns 3

At no time is there the "return of two values". A funcao always returns only one worth. What happens is that in some cases the value is obtained through an expression that may involve another function call (and no matter if it is the same function or other, the idea is the same: we have to get the value returned by the call to be able to calculate the final result of the expression).

There’s no such thing as "top scope," "previous scope," none of that. It is only one function that can call another, that can call another, that can call another (and that "other" can be even the same function, with different arguments). The important thing is that all these calls are not calling themselves eternally, and that at some point they return some value, which will be used by the previous call, which will be used by the previous one, and so on, until the first call, which will return the final result.

Another example: funcao(3, 4). We have to:

  • a=3 and b=4, enters the second if, then return funcao(a + a, b / 2) → funcao(6, 2)
    • funcao(6, 2) → a=6 and b=2, enters the second if, then return funcao(a + a, b / 2) → funcao(12, 1)
      • funcao(12, 1) → a=12 and b=1, does not enter any if, returns funcao(a + a, b / 2) + a → funcao(24, 0) + 12
        • funcao(24, 0) → a=24 and b=0, enters the first if, returns zero
      • funcao(12, 1) returns funcao(24, 0) + 12 → 0 + 12 → 12
    • funcao(6, 12) returns funcao(12, 1) → 12
  • funcao(3, 4) returns funcao(6, 2) → 12

That is, the result is 12.

Another way to visualize:

chamada recursiva

If the above image does not load, follow the same ASCII diagram:

+- funcao(3, 4) --------------------------------------------+
|  a=3, b=4                                                 |
|  entra no segundo if                                      |
|  retorna funcao(6, 2)                                     |
|              ↓                                            |
|       +- funcao(6, 2) ---------------------------------+  |
|       |  a=6, b=2                                      |  |
|       |  entra no segundo if                           |  |
|       |  retorna funcao(12, 1)                         |  |
|       |              ↓                                 |  |
|       |       +- funcao(12, 1) ---------------------+  |  |
|       |       |  a=12, b=1                          |  |  |
|       |       |  não entra em nenhum if             |  |  |
|       |       |  retorna funcao(24, 0)  + 12 ----+  |  |  |
|       |       |              ↓                   |  |  |  |
|       |       |       +- funcao(24, 0) -------+  |  |  |  |
|       |       |       |  a=24, b=0            |  |  |  |  |
|       |       |       |  entra no primeiro if |  |  |  |  |
|       |       |       |  retorna zero         |  |  |  |  |
|       |       |       +---------- | ----------+  |  |  |  |
|       |       |                   ↓              |  |  |  |
|       |       |  retorna          0  +  12 ←-----+  |  |  |
|       |       |  retorna 12                         |  |  |
|       |       +---------- | ------------------------+  |  |
|       |                   |                            |  |
|       |  retorna 12 ←-----+                            |  |
|       +---------- |------------------------------------+  |
|                   |                                       |
|  retorna 12 ←-----+                                       |
+-----------------------------------------------------------+

To repeat: there is no such thing as "top scope," bottom, back, etc. What we have is called a function. When you call a function, it is executed, and only after it returns, the code that called the function continues where it left off. When one function calls another (or itself), it has to wait for the call to end, only to catch the returned result and be able to use it.

There’s no such thing as "The standard of C is to add" (as asked in the comments). You’re the one who said you should make a sum:

funcao(a + a, b / 2) + a
                     ↑
         Aqui você disse para somar

This code adds the result of funcao(a + a, b / 2) with a. Only to make this sum, he needs to know the result of funcao(a + a, b / 2) - then it calls the function again to know what that result is (only that this call may end up making another call, which may make another, and another, etc., until at some point they fall into the first if and begin to return the results to those who called them).

If instead of this sum, it had any other operation (subtraction, multiplication, another function call, or any other valid expression), it would be done. The "default" is not to add, it is to call the functions, to take the results and to use them in the way that the code indicates - if the code says to add, as is the case, it adds.

Anyway, it’s "just" that.

  • 1

    Thank you very much, finally I had time to read this your text and I understood perfectly the behavior of this recursive function through your diagram, I ran a few times with different values and it worked here, I am very grateful.

-1

I do not know if I understand, but it is not returning two values. It is returning the sum of 'a + (call of the function itself ( value a,value b))'.

Recursive function inputs and cycles: input a == 2, b == 2

recursiveness:

Enter 2,2 -> Respect the second if that generates the inputs -> 4,1 -> Enter the last Return that generates the inputs (8,0.5) added with 4 ( (a+a,b/2) +a) in this part the (8,0.5) generates 0 that added with 4 results in 4. With this respect the input 2*2 = 4.

Enter 3,3 -> Enter the last Return that generates (6,1.5)+3 -> The (6,1.5) enters the last condition that generates (12,(1.5)/2)+6 - > the input (12,(1.5/2) enters the first condition that returns 0, so it is 6+3 = 9.

I don’t know what all the fuss is about, but it works. I hope I helped

Browser other questions tagged c recursion

You are not signed in. Login or sign up in order to post.