TIFR CSE 2016 | Part B | Question: 5

Question

Consider the recursive function $\mathsf{mc91}$.

int mc91(int n)
{
    print n
    if (n > 100) {
            return n-10;
    }
    else {
        return mc91(mc91(n+11));
    }
}

Let 

$\mathsf{Out}=\{n : \text{ there is an } x \in \{0, 1, \dots , 100 \} \text{ such that } n \text{ is one of the integers printed by } \mathsf{mc91}(x)\}$

Then which of the following is $\mathsf{Out}$?

• A. $\{ n:  - \infty < n \leq 100 \}$
• B. $\{ n:  0 \leq n \leq 101 \}$
• C. $\{ n:  0 \leq n \leq 110 \}$
• D. $\{ n:  0 \leq n \leq 111 \}$
• E. $\{ n:  0 \leq n < + \infty \}$

Answer 1

For using the values of $x\in \left \{ 0,1,2,3,4,..........,100 \right \}$, the $n$ ranges $\left \{ n:0\leq n\leq 111 \right \}$.

• Taking $x= 0$ 

#include <stdio.h>
int mc91(int );
int main(void)
{
	int i = mc91(0); 
	printf("%d",i);
	return 0;
}

int mc91(int n)
{
    printf("%d\n",n);
    if (n > 100) 
    {
        return (n-10);
    }
    else 
    {
        return (mc91(mc91(n+11)));
    }
}

Output :

0        // Minimum Value printed for the given range of $x$
11
22
33
44
55
66
77
88
99
110
100
111     // Maximum Value printed for the given range of $x$
101
91
102
92
103
93
104
94
105
95
106
96
107
97
108
98
109
99
110
100
111
101      // Maximum value returned for the given range of $x$
............................................................

........................................................

.......................................................

---

• Taking $x= 100$ 

#include <stdio.h>
int mc91(int );

int main(void)
{
	int i = mc91(100);
	printf("%d",i);
	return 0;
}

int mc91(int n)
{
    printf("%d\n",n);
    if (n > 100) 
    {
        return (n-10);
    }
    else 
    {
        return (mc91(mc91(n+11)));
    }
}

Output : 

100
111       // Maximum Value printed for the given range of $x$
101       // Maximum value returned for the given range of $x$
91

Comments

how x=0 is not going into an infinite loop??