Recursion and Iteration

When we start learning the basics of programming, as a rule, the first program we write prints the string "Hello, world!". Then we get acquainted with variables, operators, functions. And usually, the first ones a beginner gets to know are the conditional operator and the loop operator. Immediately, there is a desire to write some simple function: the factorial of a number, raising to a power, or calculating the binomial coefficient. In most cases, a beginner programmer implements the iterative version of functions. However, few know that any iterative function can also be implemented recursively.

Recursion is a method of data processing organization in which the program (or function) calls itself either directly or from other programs (functions).

A function is called recursive if, during its processing, it is called again, either directly or indirectly, through a chain of calls of other functions.

Iteration is a method of data processing organization in which some actions are repeatedly performed, not leading to recursive calls of programs (functions).

Theorem. Any algorithm implemented in recursive form can be rewritten in iterative form and vice versa.

Next, we will consider a set of elementary functions, implemented both using loop operators and using a recursive approach. Before writing recursive functions in any programming language, it is usually necessary to write a recurrence relation that defines the method of calculating functions. The recurrence relation must contain at least two conditions:

I) the condition for continuing recursion (recursion step);

II) the condition for ending recursion.

Recursion will be implemented using a call to the function itself. In this case, the condition for continuing recursion should be checked first in the body of the function. If it is true, then we exit the function. Otherwise, we make a recursive step.

The iterative version of functions will be implemented using the for loop operator.

1. Factorial of a number. The factorial of a non-negative integer $n$ is the product of all natural numbers from 1 to $n$ and is denoted by $n$!. If $f(n)=n$!, then the following recurrence relation holds:

The first equation describes the recursion step – the method of calculating $f(n)$ through $f(n-1)$. The second equation indicates when to stop calculating the function. If it is not set, then the function will work indefinitely.

For example, the value $f(3)$ can be calculated as follows:

$f(3)=3\cdot f(2)=3\cdot 2\cdot f(1)=3\cdot 2\cdot 1\cdot f(0)=3\cdot 2\cdot 1\cdot 1=6$

Obviously, calculating $f(n)$ requires making $n$ recursive calls.

The idea of the cyclic implementation is to directly calculate the factorial of a number using the loop operator:

$f(n)=1\cdot 2\cdot 3\cdot \dots \cdot n$

2. Power of a number in linear time. Calculating the power of a number $f(a,n)=a^n$ with a linear (O($n$)) time estimate can be defined using the following recurrence relation:

In the iterative version, it is enough to calculate the product $a\cdot a\cdot \dots \cdot a$ ($n$ factors of $a$).

3. Power of a number in logarithmic time. Calculating the power of a number $f(a,n)=a^n$ with a time estimate of O(log${}_{2}n$) is defined as follows:

For example, raising to the tenth power can be implemented as follows:

Since squaring is equivalent to one multiplication, to calculate $a^{10}$, it is enough to perform 4 multiplications.

4. Sum of the digits of a number. The sum of the digits of a natural number $n$ can be found using the function $f(n)$, defined as follows:

The condition for continuing recursion: the sum of the digits of a number equals the last digit plus the sum of the digits of the number without the last digit (the number divided by 10).

The condition for ending recursion: If the number is 0, then the sum of its digits is 0.

For example, the sum of the digits of the number 234 will be calculated as follows:

$f(234)=4+f(23)=4+3+f(2)=4+3+2+f(0)=4+3+2+0=9$

5. Number of ones. The number of ones in the binary representation of the number $n$ can be calculated using the function $f(n)$, defined as follows (& - bitwise 'AND' operation):

As a result of the operation n = n & (n – 1), the last one in the binary representation of the number $n$ is destroyed:

$n=a_1{a}_2\dots a_{k-1}{a}_{k}10\dots 0$

$n–1=a_1{a}_2\dots a_{k-1}{a}_{k}01\dots 1$

n & (n – 1) = a_1a_2…a_{k-1} 000…0

The recursive call of the function $f$ will be made as many times as there are ones in the binary representation of the number $n$.

6. Binomial coefficient. The value of the binomial coefficient equals

and is defined by the recurrence relation:

int c(int k, int n){ if (n == k) return 1; if (k == 0) return 1; return c(k - 1, n - 1) + c(k, n - 1);}

Considering that

the value of the binomial coefficient can be calculated using a loop. In this case, all division operations will be integer. If $k>n–k$, then use the relation

to avoid Time Limit when calculating, for example, the value

int Cnk(int k, int n){ long long res = 1; if (k > n - k) k = n - k; for (int i = 1; i <= k; i++) res = res * (n - i + 1) / i; return (int)res;}

7. Recursive function. For a given natural $n$, let's calculate the value of the function $f(n)$, defined by the recurrence relations:

$f(2\cdot n)=f(n),$

$f(2\cdot n+1)=f(n)+f(n+1),$

$f(0)=0,f(1)=1$

The direct implementation of the function $f(n)$ looks like this:

int f(int n){ if (n <= 1) return n; if (n % 2) return f(n / 2) + f(n / 2 + 1); return f(n / 2);}

In such an implementation, some values of the function $f$ may be calculated several times. Let's consider another approach to calculating the values of $f$. Let's define the function

$g(n,i,j)=i\cdot f(n)+j\cdot f(n+1),$

for which the following equalities hold:

$g(2\cdot n,i,j)=g(n,i+j,j),$

$g(2\cdot n+1,i,j)=g(n,i,i+j),$

$g(0,i,j)=i\cdot f(0)+j\cdot f(1)=j$

Using the given relations, the value $f(n)=g(n,1,0)$ can be calculated with a time estimate of O(log $n$).

int g(int n, int i, int j){ if (!n) return j; if (n % 2) return g(n / 2, i, i + j); return g(n / 2, i + j, j);}

int f(int n){ return g(n, 1, 0);}

8. Ackermann function. The Ackermann function A($m$, $n$) is defined recursively as follows:

A(0, $n$) = $n$ + 1,

A($m$, 0) = A($m$ – 1, 1),

A($m$, $n$) = A($m$ – 1, A($m$, $n$ – 1))

The recursive implementation of the Ackermann function looks like this:

int a(int m, int n){ if (!m) return n + 1; if (!n) return a(m - 1, 1); return a(m - 1, a(m, n - 1));}

For small values of $m$, the Ackermann function can be expressed explicitly:

A(0, $n$) = $n$ + 1

A(1, $n$) = 2 + ($n$ + 3) – 3 = $n$ + 2

A(2, $n$) = 2 · ($n$ + 3) – 3 = 2 · $n$ + 3

A(3, $n$) = 2${}^{n+3}$ – 3

9. Selection for reconnaissance [ACM, 1999]. From $n$ soldiers, lined up in a row, it is necessary to select a few for reconnaissance. To do this, the following operation is performed: if there are more than 3 soldiers in the row, then all soldiers standing in even positions are removed, or all soldiers standing in odd positions are removed. This procedure is repeated until there are 3 or fewer soldiers left in the row. They are sent for reconnaissance. Calculate the number of ways in which such reconnaissance groups can be formed exactly with three people.

Input. The number of soldiers in the row $n$ (0 < $n$ ≤ 10${}^7$).

Output. The number of ways in which soldiers can be selected for reconnaissance in the above manner.

Solution. Let's denote by $f(n)$ the number of ways in which reconnaissance groups can be formed from $n$ people in the row. Since we are only interested in groups of three scouts, $f(1)=0$, $f(2)=0$, $f(3)=1$. That is, from three people, only one group can be formed, from one or two – none.

If $n$ is even, then by applying the operation defined in the problem for removing soldiers in the row, we will have either $n$ / 2 soldiers left, who stood in even positions, or $n$ / 2 soldiers, who stood in odd positions. Thus, $f(n)=2\cdot f(n/2)$ for even $n$.

If $n$ is odd, then after removal, either $n$ / 2 soldiers, who stood in even positions, or $n$ / 2 + 1 soldier, who stood in odd positions, will remain. The total number of ways for odd $n$ equals

$f(n)=f(n/2)+f(n/2+1).$

Thus, the obtained recurrence formula for calculating the value of $f(n)$:

$f(n)=2\cdot f(n/2)$, if $n$ is even

$f(n)=f(n/2)+f(n/2+1)$, if $n$ is odd

$f(1)=0,f(2)=0,f(3)=1$

The implementation of the function $f$ looks like this:

int f(int n){ if (n <= 2) return 0; if (n == 3) return 1; if (n % 2) return f(n / 2) + f(n / 2 + 1); return 2 * f(n / 2);}

REFERENCES

1. "Algorithms: Design and Analysis", Cormen T., Leiserson C., Rivest R., Stein C., – Moscow, Saint Petersburg, Kiev, 2005 – 1292 p.

2. "Practice and Theory of Programming", Book2. "Practice and Theory of Programming", Volume 2. Vinokurov N.A., Vorozhtsov A.V., - Moscow: Fizmatkniga, 2008 - 288 p.