Practice Questions for Recursion with solution | Programming and Data Structures - GATE CSE Notes

Let's Learn Recursion in Data Structures with solved questions with easy explanation...

Let's get started.

Q1. on Recursion

Output of following program?

#include <stdio.h>
int fun(int n, int *f_p)
{
    int t, f;
        if (n <= 1)
        {
        *f_p = 1;
        return 1;
        }
    t = fun(n- 1,f_p);
    f = t+ * f_p;
    *f_p = t;
    return f;
}

int main()
{
    int x = 15;
    printf (" %d n", fun(5, &x));
return 0;
}

- GATE-CS-2009    

A. 6

B. 8

C. 15

D. 14

Solution: B. 8

---

Q2. on Recursion

Consider the following function

double f(double x)

{

  if (abs(x*x - 3) < 0.01) return x;

  else return f(x/2 + 1.5/x);

}

Give a value q (to 2 decimals) such that f(q) will return q:_____.

- GATE-CS-2014-(SET-2)    

A. 1.73

B. 2.24

C. 4.22

D. 3.42

Solution: A. 1.73

The else part: else return f(x/2 + 1.5/x);

    x/2 + 3/2x  =  (x^2 + 3) / 2x

   So, x will be  (x^2 + 3) / 2x

⟹ (x^2 + 3) / 2x  = x

⟹ (x^2 + 3) = 2x^2

⟹ x^2=3

⟹ x=1.732

The if part: if (abs(x*x - 3) < 0.01) return x;

    abs(x*x - 3) < 0.01

    So, x^2 - 3 < 0.01 and - (x^2 - 3) < 0.01

⟹ x^2 < 3.01 and x^2 > 2.99

⟹ x<1.735 and x>1.729

Answer is either 1.73 or 1.74.

---

Q3. on Recursion

Consider the C function given below.
int f(int j)
    {
        static int i = 50;
        int k;
            if (i == j)
            {
            printf(“something”);
            k = f(i);
            return 0;
            }
        else return 0;
    }
Which one of the following is TRUE? 

- GATE-CS-2014-(Set-2)    

A. The function returns 0 for all values of j.
B. The function prints the string something for all values of j.
C. The function returns 0 when j = 50.
D. The function will exhaust the runtime stack or run into an infinite loop when j = 50

Solution:

    When j is 50, the function may call itself again and again because i and j remain unchanged inside the recursion. There is no exit condition(base Condition) for recursion, So the function will exhaust the runtime stack or run into an infinite loop.

---

Q4. On Recursion

Consider the following C function:
int f(int n)
    {
        static int i = 1;
        if (n >= 5)
        return n;
        n = n+i;
        i++;
        return f(n);
    }
The value returned by f(1) is _____
- (GATE CS 2004), ISRO 2008

A. 5
B. 6
C. 7
D. 8

Solution: C. 7

---

Q5. On Recursion

Consider the following C function. 
int fun (int n)
    {
        int x=1, k;
        if (n==1) return x;
        for (k=1; k<n; ++k)
        x = x + fun(k) * fun(n – k);
        return x;
    }
The return value of fun(5) is __________.

- GATE-CS-2015 (Set 2) 

A. 0
B. 26
C. 51
D. 71

Solution: C.51

for n = 1,

    fun(1) =1

for n = 2,

    fun(2) : x=1+fun(1)*fun(1)
    x=1+1*1
    x=2
    fun(2) = 2

for n = 3,

    fun(3) : x = x+fun(1)*fun(2)
    x= 1+1*2
    x= 3

    x= 3+fun(2)*fun(1)
    x= 3+2*1
    x= 5
    fun(3) = 5

for n = 4,

    fun(4) : x = x+fun(1)*fun(3)
    x= 1+1*5
    x= 6

    x = x+fun(2)*fun(2)
    x= 6+2*2
    x= 10
    x = x+fun(3)*fun(1)
    x= 10+5*1
    x= 15
   fun(4)=15

for n = 5,
    fun(5): x = x+fun(1)*fun(4)
    x= 1+1*15
    x= 16
    

    x = x+fun(2)*fun(3)
    x= 16+2*5
    x= 26
    

    x = x+fun(3)*fun(2)
    x= 26+5*2
    x= 36

    x = x+fun(4)*fun(1)
    x= 36+15*1
    x= 51

    fun(5)= 51

---

Q6. On Recursion

Output of following program?
#include <stdio.h>
int fun(int n, int *f_p)
{
int t, f;
if (n <= 1)
{
*f_p = 1;
return 1;
}
t = fun(n- 1,f_p);
f = t - * f_p;
*f_p = t;
return f;
}

int main()
{
int x = 21;
printf (" %d ", fun(6, &x));
return 0;
}

A. 1

B. 2

C. 3

D. 4

Solution: A. 1

Learn More about Recursion | Programming and Data Structures - GATE CSE Notes

That's it for today. 😊 Practice more and more. Happy Learning. 

Please leave suggestions, query, more about recursion in comment section. 

Keep Learning Keep Sharing Stay  Safe.😷