Recursion stack

1. Implementing pow(x, n) through recursion
2. Execution context, stack
3. Recursion tasks

In the code, functions can call other functions to perform subtasks. A special case of a sub-call is when a function calls itself. This is called recursion .

In this chapter, we will look at how recursion is built from within and how it can be used.

Implementing pow(x, n) through recursion

To raise x to a natural degree n - you can multiply it by yourself n times in a cycle:

1	function pow(x, n) {

2	var result = x;

3	for ( var i=1; i

4	result *= x;

5

}

6

7	return result;

8

}

And you can do it easier.

After all, x n = x * x n-1 , i.e. can take one x out of the degree. Thus, the value of the function pow(x,n) obtained from pow(x, n-1) multiplying by x .

This process can be continued. For example, pow(2, 4) calculate pow(2, 4) :

1	pow(2, 4) = 2 * pow(2, 3);

2	pow(2, 3) = 2 * pow(2, 2);

3	pow(2, 2) = 2 * pow(2, 1);

4	pow(2, 1) = 2;

... That is, for the degree of pow(2, n) we get the result as 2 * pow(2, n-1) , then reduce n by one more, and so on. This process stops at n==1 , since it is obvious that pow(x,1) == x .

The code for this calculation is:

1	function pow(x, n) {

2	// пока n!=1, сводить вычисление pow(..,n) к pow(..,n-1)

3	return (n != 1) ? x*pow(x, n-1) : x; (n != 1) ? x*pow(x, n-1) : x;

4

}

5

6	alert( pow(2, 3) ); // 8

They say that “the pow function recursively calls itself ”.

The value on which the recursion ends is called the basis of the recursion . In the example above, the base is 1 .

The total number of nested calls is called the recursion depth . In the case of a degree, there will be n calls in total. The maximum recursion depth is limited to about 10000 , but this number depends on the browser and can be 10 times less.

Recursion is used when calculating a function can be reduced to its simpler call, and it can be reduced to a simpler one, and so on, until the value becomes obvious.

Execution context, stack

Now we will look at how recursive calls work.

Each function call has its own execution context.

The execution context includes local variables of the function and other service information necessary for its current execution.

Whenever a function is called, the interpreter switches the context to a new one. This process consists of several steps:

1. The current function is suspended.
2. Information about its execution, that is, the current context is entered into a special internal data structure: the “stack of contexts”.
3. A new function is launched, a context is created for it.
4. At the end of the sub-call, the previous context gets out of the stack, execution in it resumes.

For example, to call:

1	function pow(x, n) {

2	return (n != 1) ? x*pow(x, n-1) : x; (n != 1) ? x*pow(x, n-1) : x;

3

}

4

5	alert( pow(2, 3) );

The following passes:

pow(2, 3)

The function pow launched, with arguments x=2 , n=3 . These variables are stored in the execution context, schematically shown below:

• Context: {x: 2, n: 3}

pow(2, 2)

Line 2 calls pow , with arguments x=2 , n=2 . For this function, a new current context is created (highlighted in red), and the previous one is saved in the “stack”:

• Context: {x: 2, n: 3}
• Context: {x: 2, n: 2}

pow(2, 1)

Again a nested call in line 2 , this time with arguments x=2 , n=1 . A new current context is created, the previous one is added to the stack:

• Context: {x: 2, n: 3}
• Context: {x: 2, n: 2}
• Context: {x: 2, n: 1}

Exit pow(2, 1) .

When calling pow(2, 1) there are no nested calls. The function for n==1 immediately ends its work, returning 2 . The current context is no longer needed and is removed from memory, the previous one is restored from the stack:

• Context: {x: 2, n: 3}
• Context: {x: 2, n: 2}

Processing of the external call pow(2, 2) resumed.

Exit pow(2, 2) .

... And now pow(2, 2) can finish its work by returning 4 . The context of the previous call is restored:

• Context: {x: 2, n: 3}

Processing of the external call pow(2, 3) resumed.

Exit pow(2, 3) .

The outermost call finishes its work, its result: pow(2, 3) = 8 .

The depth of recursion in this case was: 3 .

As you can see from the illustrations above, the recursion depth is equal to the maximum number of contexts simultaneously stored on the stack.

At the very end, as at the very beginning, execution falls into an external code that is outside of any functions. This code also has a context. It is called a “global context”, and it is the starting and ending point of any nested subcalls.

Pay attention to the memory requirements. In fact, recursion leads to the storage of all data for external calls on the stack. That is, raising to a power n stores in memory n different contexts.

The implementation of the degree through the cycle is much more economical:

1	function pow(x, n) {

2	var result = x;

3	for ( var i=1; i

4	result *= x;

5

}

6	return result;

7

}

Such a pow function will have one context in which the i and result values ​​will consistently change.

Any recursion can be redone into a loop. As a rule, the cycle option will be more efficient.

... But why then need recursion? Yes, simply because the recursive code can be much simpler and clearer! Redesigning into a loop can be non-trivial, especially when different recursive sub-calls are used in the function, depending on the conditions.

In programming, we first of all strive to make the complex simple, and we need improved performance ... Only where it is really needed. Therefore, a beautiful recursive solution is in many cases better.

Disadvantages and benefits of recursion:

• Memory requirements.

• Limited maximum stack depth.

• The brevity and simplicity of the code.

Recursion tasks

Importance: 5

Write the function sumTo(n) , which for a given n calculates the sum of numbers from 1 to n , for example:

1	sumTo(1) = 1

2	sumTo(2) = 2 + 1 = 3

3	sumTo(3) = 3 + 2 + 1 = 6

4	sumTo(4) = 4 + 3 + 2 + 1 = 10

5

...

6	sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

Make three solutions:

1. Using a loop.
2. Through recursion, because sumTo(n) = n + sumTo(n-1) for n > 1 .
3. Using the formula for the sum of an arithmetic progression.

An example of how your function works:

function sumTo(n) { /*... ваш код ... */ }

alert( sumTo(100) ); // 5050

Which solution is the fastest? The slowest? Why?

Is it possible to calculate sumTo(100000) using recursion? If not, why not?

Decision

Cycle solution:

1	function sumTo(n) {

2	var sum = 0;

3	for ( var i=1; i<=n; i++) {

4

sum += i;

5

}

6	return sum;

7

}

8

9	alert( sumTo(100) );

Solution through recursion :

1	function sumTo(n) {

2	if (n == 1) return 1;

3	return n + sumTo(n-1);

4

}

5

6	alert( sumTo(100) );

The formula solution: sumTo(n) = n*(n+1)/2 :

1	function sumTo(n) {

2	return n*(n+1)/2;

3

}

4

5	alert( sumTo(100) );

PS Do I have to say that the formula solution works the fastest? It uses only three operations for any n , and the cycle and recursion require at least n addition operations.

The cycle option is second in speed. It is faster than recursion, since the operations are essentially the same, but there is no overhead for the nested function call.

Recursion in this case is the slowest.

PPS There is a limit on the depth of nested calls, so a recursive sumTo(100000) call sumTo(100000) will sumTo(100000) error.

[Open task in new window]

Importance: 4

The factorial number is a number multiplied by “self minus one”, then “self minus two” and so on, to unity. Denoted by n!

The definition of factorial can be written as:

n! = n*(n-1)*(n-2)*...*1

Examples of values ​​for different n :

1

1! = 1

2	2! = 2*1 = 2

3	3! = 3*2*1 = 6

4	4! = 4*3*2*1 = 24

5	5! = 5*4*3*2*1 = 120

The task is to write the function factorial(n) , which returns the factorial of the number n! using recursive call.

alert( factorial(5) ); // 120

Hint: note that n! can be written as n * (n-1)! for example 3! = 3*2! = 3*2*1! = 6 3! = 3*2! = 3*2*1! = 6

Decision

According to the properties of factorial, as described in the condition, n! can be written as n * (n-1)! .

That is, the result of the function for n can be obtained as n multiplied by the result of the function for n-1 , and so on up to 1! :

1	function factorial(n) {

2	return (n!=1) ? n*factorial(n-1) : 1; (n!=1) ? n*factorial(n-1) : 1;

3

}

4

5	alert( factorial(5) ); // 120

The basis of the recursion is the value 1 . And it would be possible to make a basis and 0 . Then the code will be slightly shorter:

1	function factorial(n) {

2	return n ? n*factorial(n-1) : 1; n ? n*factorial(n-1) : 1;

3

}

4

5	alert( factorial(5) ); // 120

In this case, the factorial(1) call will be reduced to 1*factorial(0) , there will be an additional recursion step.

[Open task in new window]

Importance: 5

The sequence of Fibonacci numbers has the formula F n = F n-1 + F n-2 . That is, the following number is obtained as the sum of the two previous ones.

The first two numbers are 1 , then 2(1+1) , then 3(1+2) , 5(2+3) and so on: 1, 1, 2, 3, 5, 8, 13, 21... .

Fibonacci numbers are closely related to the golden section and the many natural phenomena around us.

Write the function fib(n) , which returns the n-е Fibonacci number. Work example:

1	function fib(n) { /* ваш код */ }

2

3	alert( fib(3) ); // 2

4	alert( fib(7) ); // 13

5	alert( fib(77)); // 5527939700884757

All function launches from the example above should work quickly.

Decision

Recursion calculation (slow)

Formula solution using recursion:

1	function fib(n) {

2	return n <= 1 ? n : fib(n-1) + fib(n-2); n <= 1 ? n : fib(n-1) + fib(n-2);

3

}

4

5	alert( fib(3) ); // 2

6	alert( fib(7) ); // 13

7	// fib(77); // не запускаем, подвесит браузер

For large values ​​of n it will work very slowly. For example, fib(77) will already be calculated for a very long time.

This is because the function spawns an extensive tree of nested calls. In this case, a number of values ​​are calculated many times. For example, fib(n-2) will be calculated for both fib(n) and fib(n-1) .

You can optimize this by memorizing the already computed values ​​.. And you can simply abandon the recursion, and instead go by the formula from left to right in the cycle, calculating the 1st, 2nd, 3rd and so on numbers to the desired one.

Try it. It does not work out - open the solution below.

Sequential calculation (idea)

We will go according to the formula from left to right:

1	var a = 1, b = 1; // начальные значения

2	var c = a + b; // 2

3

4	/* переменные на начальном шаге:

5

a b c

6

1, 1, 2

7

*/

Now for the next step, assign a and b current 2 numbers and get the new next in c :

1	a = b, b = c;

2	c = a + b;

3

4	/* стало так (еще число):

5

a b c

6	1, 1, 2, 3

7

*/

The next step will give us one more sequence number:

1	a = b, b = c;

2	c = a + b;

3

4	/* стало так (еще число):

5

a b c

6	1, 1, 2, 3, 5

7

*/

Repeat in a loop until we get the desired value. This is much faster than recursion, if only because none of the numbers is calculated twice.

PS This approach to computing is called bottom-up dynamic programming.

Sequential calculation (code)

01	function fib(n) {

02	var a = 1, b = 1;

03	for ( var i = 3; i <= n; i++) {

04	var c = a + b;

05

a = b;

06

b = c;

07

}

08

return b;

09

}

10

11	alert( fib(3) ); // 2

12	alert( fib(7) ); // 13

13	alert( fib(77)); // 5527939700884757

The cycle here begins with i=3 , since the first and second Fibonacci numbers are written in advance in the variables a=1 , b=1 .

[Open task in new window]

There are many areas of application for recursive calls, in particular, working with data structures, such as a document tree. We will definitely meet with them.