Self-test 7:
Recursive functions

What is the output of following code?

#include <iostream>
using namespace std;

int rec(int n)
{
    if (n <= 2)
        return n;

    return rec(n-1) + rec(n-2);
}

int main(void)
{
    cout << rec(5) << endl;
    return 0;
}

Solution

Top-Down Tracing:

                   rec(5)
                 /       \
           rec(4)         rec(3)
          /     \         /    \
      rec(3)  rec(2)*  rec(2)*  rec(1)*
      /    \       
 rec(2)*  rec(1)*

The result is the sum of all bottom nodes, marked with asterisks in the above tree. This top-down tracing approach is a good way, not only to solve this kind of questions by hand, but is also a good way to understand how recursion works.

Let us change the input argument to 7. What is the expected result? (This question is designed for you to practice tracing recursive calls as discussed in the last question.)

Solution

21

Try to guess the purpose of the following code and then rewrite it using recursion.

int mysterious(int x)
{
    if (x == 0)
        return 1;
    else
    {
        int counter;
        for (counter = 0; x != 0; ++counter)
            x /= 10;

        return counter;
    }
}

Solution

The mysterious function will count the number of digits in the given integer argument. The following may be its recursive version:

int count_digits_recursive(int x)
{
    if (x < 10) 
        return 1;
    else
        return count_digits_recursive(x/10) + 1;
}

Write a recursive function that prints out the octal representation of number n. That is, convert a non-negative integer from base 10 to base 8.

Solution
```
void octal(int n)
{
    if (n < 8)
        cout << n ;
    else
    {
        octal(n/8);
        octal(n%8);
    }
}
```
Write a recursive function to compute the greatest common divisor of two positive integers. The function's protype should be: int gcd(int, int);. Hint: the Euclidean algorithm

Solution
```
int gcd(int m, int n) 
{
    if(n == 0) 
        return m;
    else
        return gcd(n, m%n);
}
```
Which of the following statements is not a disadvantage of recursion?
1. Difficult to trace and debug
2. More demanding memory resources
3. Elegant and concise solution
4. More computational time
Solution

C.

Self-test 7: Recursive functions

Self-test 7:
Recursive functions