Corrected exercises recursive algorithm

The following corrected exercises concern the principle of recursive algorithm, for example Fibonacci, the Towers of Hanoi and many other cases math. The exercises include simple recursion, tail recursion, cross-recursion or mutual recursion, and the principle of memoization (for more details on this last point, please see the principle of dynamic programming).

recursive algorithm

Exercise 1

Rewrite the following algorithms in recursive form in terminal form when possible.

recursive algorithm corrected exercises recursive terminal multiple recursion call tree

recursive algorithm

recursive algorithm

A last one for the road. This time you have to understand what it does before making it terminal recursive!

gcd algorithm

We consider that n is a positive integer or zero.

terminal recursive algorithm

terminal recursive algorithm

algo3 is already recursive but not terminal. Since the algorithm returns 2^not, we will change its structure to make it terminal.

terminal recursive algorithm

For the last algorithm, we must first understand that it calculates the gcd between a and b. Do a test by hand, you will understand that the first branch is useless, so we will remove it for the recursion. The variable r is not present to replace the value of a and b, so it will not fit in the recursion.

gcd algorithm

Exercise 2

The Fibonacci problem (1170 – 1250):

“Originally possessing a pair of rabbits, how many pairs do you get in twelve months if each pair generates a new pair every month from the second month of its existence? Rabbits never die.”

So if we take an example of the first 7 months.

Month

1

2

3

4

5

6

7

Couple

1

1

2

3

5

8

13

a – Express the population of couples of month n as a function of the previous months.

b – Write an iterative algorithm that calculates the number of couples after 12 months.

c – Modify the iterative algorithm to calculate the number of months after which the population of rabbit pairs exceeds 300.

d – Write the recursive algorithm to calculate the number of pairs of rabbits after n months.

has -

The number of pairs of rabbits in month n is the sum of the pairs existing the month before (in month n − 1) and the new pairs in month n.

However, the text specifies that all the couples existing two months before (at month n − 2) reproduce.

Therefore, at month n ≥ 2 the number of rabbits is equal to the sum of month n-1 and n-2. At month 0 and month 1, there is only one pair.

b-

Corrected exercises recursive algorithm recursive algorithm

vs -

Corrected exercises recursive algorithm recursive algorithm

d-

fibonacci recursive algorithm

We will not calculate the complexity above. For those who want to lose their heads, I invite you here: https://miashs-www.u-ga.fr/prevert/Prog/Complexite/nombresFibonacci.html

Exercise 3

a – Write an algorithm that calculates the maximum of 2 real numbers 

b – Write a recursive algorithm that calculates the maximum of 3 real numbers using the algorithm of a. Show call tree.

c – Write a recursive algorithm that calculates the maximum of 4 real numbers using the algorithm of a. Show call tree.

d – Is the algorithm recursive?

has -

maximum recursive algorithm

b-

maximum recursive algorithm

Here, Maximum2 acts as the terminal condition of the recursive algorithm. The call stack is as follows:

maximum recursive algorithm

vs -

maximum recursive algorithm

The call stack is as follows:

maximum recursive algorithm

d – Although it looks like a recursion, it's more of a function overload or function call to reduce the size of the problem. It is not a recursive algorithm per se.

Exercise 4

a – Are the algorithms below recursive algorithms? 

b – Are they terminal?

c – Do they end?

log recursive algorithm

power recursive algorithm

sum recursive algorithm

has -

The log and sum algorithms are recursive: each contains at least one call to itself, on the other hand, power is not: it calls the algorithm then. It is necessary to replace then by power.

b- 

log is terminal, power and sum are not because they require computation during the recursion.

vs -

log terminates for any integer x. The iteration of integer division by 2 leads to 0, and the base case 0 ends with the execution of return. 

For the power algorithm (corrected), the base case 0 ends with the execution of returning. If the algorithm terminates for the value n−1 then it also terminates for the value n is executing return. Don't forget that a user can enter anything like power(2, – 5) so you have to check his termination.

sum does not end when n is strictly positive. Indeed, the algorithm for n terminates only if the algorithm terminates for n+1. However, there is no strictly positive integer for which the algorithm stops.

Exercise 5

a – We want to write a recursive function that calculates the square of an integer. To do this, we will have to use a relation between square(n) and square(n-1) knowing that square(1)=1. Represent the call stack for carre(5).

b – Combinations are a mathematical concept describing the different ways of choosing a given number of objects from a set of given size. For example how much it is possible to draw 6 Lotto balls out of 60 in the reel. Or draw 3 cards from a tarot deck. The combination of choosing p elements from n elements is denoted C(p,n)=(n/p)*C(p-1, n-1). We got C(0,n)=1 and C(n,n)=1. 

Write the non-terminal recursive function then the terminal recursive function, and show the call stack for C(3,7). Via the terminal function, deduce the iterative function.

c – For combinations, we generally prefer to avoid the b method because the divisions can create rounding problems. We will instead use the following relationship: C(p,n)=C(p,n-1)+C(p-1,n-1). Write the recursive function and the stack or tree calls for C(2,4).

a – To find a link between square(n) and square(n-1), we use the formula: (n+ 1)² = n² + 2n+ 1. We write it as a function of n to n-1: n² = (n−1)²+2(n−1)+1 hence square(n)=square(n-1)+2*n-1. That's it !

square recursive algorithm

The call stack is:

square recursive algorithm

b – Everything is said in the statement, all that remains is to write it down.

recursive algorithm combination

Here is the list of calls for C(3,7):

recursive algorithm combination

And now for the terminal version, it's a little more complicated because you have to wonder about what you have to keep in memory for the recursion. At each iteration we did n/p times the previous one, so n/p * (n-1)/(p-1). We could have written it n(n-1)/p(p-1). So we could store the multiplication of decreasing n on one side and decreasing p on the other.

recursive algorithm combination

Here is the call stack for C(3,7,1,1):

recursive algorithm combination

We deduce the iterative function from the terminal function. Just do a Until the stopping condition is reached.

recursive algorithm combination

c – We already have the recursive relation in the statement.

recursive algorithm combination

Here is the call tree for C(2,4):

recursive algorithm combination

Exercise 6

We define the McCarthy function as follows:

McCarthy's algorithm

What does the function do for n>100? for n=98, 99, 100? In general for n<=100?

We are going to do a bit of math… If n > 100 we will have n-10. The problem arises when we start with n<=100. Calculate for 98, 99 and 100. We will do a direct demonstration.

For n between 90 and 100 inclusive – i.e. 11 consecutive values, this will be useful later. We will do Carthy(Carthy(n+11)) so we will exceed the value of 100. So we will have Carthy(n+1) in the end. If n+1 is still not greater than 100, we put the cover back. So we stop when we go from 100 to 101, or Carthy(101)=101-10=91.

In resumes what we left at the beginning of the previous paragraph. On the last 11 consecutive values, we will have a result of 91. We note that any number between 0 and 89, to which we add 11 as long as it is less than 90 will have a final value between 90 and 100 inclusive.

We deduce that Carthy on a value of 100 or less will give the value of 91.

It needed a bit of math. Computer science is just another syntactic way of doing math!

Exercise 7

We are talking about recursion cross when two functions call each other recursively.

We will test on a cross recursion to know if a number is even (true) or odd (false). Here is the proposal:

cross recursive algorithm

Test for even(2), odd(3), even(3), and odd(2). Is the algorithm correct? Otherwise change it to check the correction ← PS: if the teacher asks that, it's because the algo has a problem CQFD

Obviously the algo is not correct. Take even(3) → odd(2) → even(1) → odd(0) → even(-1) → odd(-2) → etc. This is because the stop conditions only work if the number of the even method is even and the odd method is odd. We will only change the odd method.

even odd cross recursion

It's up to you to retest if it's correct now!

Exercise 8

It is impossible to conclude on the recursive without mentioning the famous Towers of Hanoi (the obsession of students and sometimes also of lecturers and teachers!). So we're going to take it slowly.

towers of hanoi

There are n trays of different sizes, and 3 rods, numbered from 0 to 2.

Initially, all trays are located on stem i. The goal is to transfer them to the rod j, respecting the following rules:

– You can only move one board at a time.

– The trays must always be arranged in decreasing size on a rod (the largest at the bottom then in decreasing order going up on the rod).

1 – Solve the problem by hand if n = 2, i = 0 and j = 2 (so 2 trays, they are all base on rod 0 and we want to put them on rod 2).

2 – Solve the problem by hand if n = 3, i = 0 and j = 2 (so 3 trays, they are all base on rod 0 and we want to put them on rod 2).

3 – Suppose a friend of yours knows how to solve the problem for some n, and any which i and j. You are asked to solve the problem for n + 1. You have the right to use your friend's help. How do you do it?

4 – Write the recursive function that solves this problem for all n, i, j (If you can do it without cheating, congratulations! Otherwise it's normal, we almost all went through this great moment of misunderstanding and questioning of her career…)

1 – 

The small board is transferred from 0 to 1. 

The large board is transferred from 0 to 2. 

We transfer the small tray from 1 to 2.

2 –

The small board is transferred from 0 to 2. 

We transfer the average plateau from 0 to 1.

We transfer the small board from 2 to 1. (we moved 2 boards from 0 to 1). 

The large board is transferred from 0 to 2. 

The small board is transferred from 1 to 0. 

We transfer the medium board from 1 to 2. 

We transfer the small board from 0 to 2. (we moved 2 boards from 1 to 2).

3 –

We move n trays from i to the location which is neither i nor j (by the series of three manipulations of point 2). We then move the last board (the biggest) from i to j. We call on the friend to move the n trays to j. 

4 –

If you find that… champagne! We will rename for ease the stems in d for the starting one, a for the arrival one and r for the remaining one

towers of hanoi

Exercise 9

Write a program to find the GCD of two numbers using recursion.

Here is the idea behind the algorithm:

gcd algorithm

gcd algorithm

Exercise 10

Write a program to convert a decimal number to binary using recursion.

Here is the idea behind the algorithm:

binary algorithm

binary recursive algorithm

Exercise 11

Write a program to find the LCM of two numbers using recursion.

MCL

Here is the algorithm:

MCL

Exercise 12

Write a program to check if a given string is Palindrome or not.

Exercise 13

The number Pi can be calculated by the following formula:

pi recursive

Write a recursive algorithm to calculate the value of Pi by considering the sequence up to rank n.

Do the same with the following approximations of Pi.

Gregory-Leibniz series:

Corrected exercises recursive algorithm recursive algorithm

And the older series of Madhava, Ramanujan, David and Chudnovsky (the factorial will be a recursive call in its own right):

pi recursive

 

Here is the recursive algorithm:

pi recursive

The other formulas follow the same principle, no need to detail everything. Be careful all the same to use the correct calculation in the recursion! (the algorithms will be easier to write in non-terminal recursive.

Exercise 14

In the 1920s, Wilhelm Ackermann and Gabriel Sudan, then students under David Hilbert, studied the foundations of computability. Sudan is the first to give an example of a primitive recursive but non-recursive function, then called Sudan's function. Soon after and independently, in 1928, Ackermann published his own example of a primitive recursive but non-recursive function. Originally, Ackermann considers a function ϕ(m, n, p) dependent on three variables.

A function of only two variables is given later by Rózsa Péter and Raphael Robinson; it is the latter which is known today as the Ackermann function.

The Ackermann-Péter function is defined recursively as follows:

ackerman

The function grows so fast that it is quickly impossible to write it with a classical number and it is necessary to use Knuth's notation!

ackerman

The solution is very simple, but I do not recommend running the algorithm on a PC.

recursive ackermann

Exercise 15

Here is the function of Sudan, another student of David Hilbert. This function was designed in 1927 so a year earlier than Ackermann's function.

recursive sudan

Here, the more the value of n grows, the more the result of the function of the function explodes. Here is the example for F_1(14,14).

recursive sudan

Nothing very complicated, just copy the mathematical formula in the form of recursion.

recursive sudan

Exercise 16

Takeuchi's function, abbreviated tak or sometimes tarai, is the recursive presentation of a function named after Ikuo Takeuchi (竹内郁雄). The presentation of the function, which, moreover, admits a fairly simple non-recursive definition, may require very long calculations if the compiler which implements it is not efficient. For this reason, it is often used to test the performance of the implementation of recursive functions by the compiler of a programming language.

takeuchi

Takeuchi's original definition was:

takeuchi

tarai is the abbreviation of "to pass around" in Japanese. John McCarthy named this function tak() after Takeuchi.

Recursion has been improved thanks to cross-recursion:

takeuchi

Exercise 17

The Male-Female Hofstadter sequence is defined by:

F(0)=1, M(0)=0 and

hofstadter

Write a recursive algorithm to calculate the Hofstadter sequence.

It is a cross recursive algorithm (also called mutual recursive perfect).

hofstadter mutual recursion

Exercise 18

Some programming languages allow memoization. It is a caching of the return values of a function according to its input values. The purpose of this code optimization technique is to reduce the execution time of a computer program by memorizing the values returned by a function.

Thus, by carrying out the Fibonacci sequence, it is possible to memorize the values already calculated in order to avoid saturating the memory with values already obtained in another branch of the call tree.

In fact, whenever we compute fib(i), we could just cache that result and use it later. So when we call fib(n), we shouldn't have to do much more than 0(n) calls, because there are only O(n) possible values we can cast to fib(n).

Fibonacci Memoization

Exercise 19

Some programming languages allow memoization. It is a caching of the return values of a function according to its input values. The purpose of this code optimization technique is to reduce the execution time of a computer program by memorizing the values returned by a function.

Write an algorithm calculating factorial n (n!) using the principle of memoization.

We will store each value of the factorial in an array:

memoization factorial

The second solution is more technical because it requires having access to the cache memory with for example the import of lru_cache. Thus, the calculation of factorial of large number becomes fast and not greedy in memory.

Exercise 20

And here's a little exercise combining everything you've seen recursion, crossover and memoization.

There are oranges in the kitchen and you have decided to eat some of these oranges every day as follows:

  • Eat an orange.
  • If the number of remaining oranges n is divisible by 2 then you can eat n/2 oranges.
  • If the number of remaining oranges n is divisible by 3 then you can eat 2*(n/3) oranges.

You can only choose one of the actions per day.

Given the integer n, returns the minimum number of days to eat n oranges.

Input: n = 10
Output: 4

Explanation: You have 10 oranges.

Day 1: Eat 1 orange, 10 – 1 = 9.
Day 2: Eat 6 oranges, 9 – 2*(9/3) = 9 – 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 – 2*(3/3) = 3 – 2 = 1.
Day 4: Eat the last orange 1 – 1 = 0.

It takes at least 4 days to eat all 10 oranges.

To share