Triangular numbers. Recursion Job return in java

Question

Please explain the operation of the code using the example of n equal to 5:

int triangle(int n) { if(n==1) \\почему он здесь запоминает 1?, явного присваивания нет же! return 1; else return( n + triangle(n-1) ); }

As for me, so is a duplicate of Stackoverflow.com/questions/120510 Linking.

Accepted Answer · 2016-06-27T18:13:54

No one here remembers anything.

Just the method will be called until the method parameter is equal to 1 .

See an example with n = 5; :

 1. triangle(5) -> n==1 ? Нет - Возвращаю [5 + Вызываю triangle(5-1(4))] 2. triangle(4) -> n==1 ? Нет - Возвращаю [4 + Вызываю triangle(4-1(3))] 3. triangle(3) -> n==1 ? Нет - Возвращаю [3 + Вызываю triangle(3-1(2))] 4. triangle(2) -> n==1 ? Нет - Возвращаю [2 + Вызываю triangle(2-1(1))] 5. triangle(1) -> n==1 ? Да - Возвращаю [1] Рекурсия прекращена

And now, when the value of the method call is received, we go up the bottom-up actions in order to get the final result.

5. triangle(1) Returned value [1] ;

4. triangle(2) return [2 + (triangle (1) = 1) ] = 3

3. triangle(3) return [3 + (triangle (2) = 3) ] = 6

2. triangle(4) return [4 + (triangle (3) = 6) ] = 10

1. triangle(5) return [5 + (triangle (4) = 10) ] = 15

 Результат: 15.

Answer 2 · 2016-06-27T18:28:35

When the method calls itself, new local variables and parameters are allocated a place in the stack and the method code is executed with these new initial values.

Each time you return from a recursive call, the old local variables and parameters are removed from the stack, and execution continues from the moment you call inside the method .

if - to exit recursion.

If you exaggerate greatly, then, let's say, you need to calculate the value with the input parameter 3 .

To make it easier to understand, imagine that on the fly more and more new functions are created automatically, with different names, but with the same type of received value and return value (tobish the same signature).

so the int triangle(int n) function goes,
n is 1? not! Then you need to return n + triangle(n-1) ? Yes! But there is a new call, but we need to return something .. Then copy this function with a different name and call it. And here we wait for now.
int triangle2(int n) function appears
n is 1? not! Then you need to return n + triangle2(n-1) ? Yes! Again, you have to wait for someone. Turn on the brake. We wait. And the challenge is giving the next new feature.
int triangle3(int n) rushes into the scene
n is 1? Yes! Hooray! Then I return her (unit) and move away from here. Pokeda!
the unit arrives in triangle2 and is added to n which is defined for this method, that is, 2 . 1 + 2 = 3. This function also leaves for the Maldives to rest. Troika returns to the first method.
the rescued very first function triangle takes the result of executing triangle2 and adds it to n already belonging to it, that is, 3. Three plus three = 6.
there is no need to do anything further and no need to do - we return the result to the outside world

Even more clearly. Roughly speaking, the result is:

 int triangle(int n) { return n + triangle2(2); // 3 + ? .... ожидаем получения результата от другой функции } int triangle2(int n) { return n + triangle3(1); // 2 + ? .... ожидаем получения результата от другой функции } int triangle3(int n) { return 1; // ничего не надо делать, т.к. n == 1 - на тебе единицу обратно } triangle(3);

Therefore, in fact, no one remembers anything. One method waits for the execution of another method, but with a different parameter.

Most likely with small input data, as above, when there are three calls in a row - there will be nothing to optimize.
But if 1000, for example, then most likely something is optimized, because
@pavel: For this, the compiler will have to know very well math.
Compilation and so the thing is not fast, and to sort through all the possibilities for convolution will slow down the process several times more.

Triangular numbers. Recursion Job return in java

2 answers 2

More articles: