# Q1. on Recursion

Consider the following recursive C function. If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main()?

void get (int n)
{
if (n < 1) return;
get(n-1);
get(n-3);
printf("%d", n);
}

A. 15
B. 25
C. 35
D. 45

Solution:
B. 25

Explanation:

As per given condition if n < 1 then it return to the main function.
So, Let’s see simple solution in tree form for all values from 1 to 6 for get(6). And find the number of invocation of get() function till condition satisfied.

# Q2. on Recursion

What will be the output of the following C program?

void count(int n)
{
static int d = 1;
printf("%d ", n);
printf("%d ", d);
d++;
if(n > 1) count(n-1);
printf("%d ", d);
}
int main()
{
count(3);
}

- GATE-CS-2016 (Set 1)

A. 3 1 2 2 1 3 4 4 4
B. 3 1 2 1 1 1 2 2 2
C. 3 1 2 2 1 3 4
D. 3 1 2 1 1 1 2

Solution:
A. 3 1 2 2 1 3 4 4 4

Explanation:

When count(3) function called:
It will print value of n = 3 and d =1.
And then d++ will change value of d = 2.
Output after count(3) : 3 1

Then count(2) will be called:
It will print value of n = 2 and d = 2.
So 2 2 will be printed and d will become 3. And then d++ will change value of d = 3.
Output after count(2) : 3 1 2 2

Then count(1) will be called:
It will print value of n = 1 and d = 3. And then d++ will change value of d = 4.
Output after count(1) : 3 1 2 2 1 3

After that when condition n>1 becomes false, count(1) will print value of d = 4 and finish its execution. Then count(2) will print value of d = 4. And count(3) will print value of d = 4.
So final Output will be: 3 1 2 2 1 3 4 4 4

# Q3. On Recursion

The function f is defined as follows:

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

Assuming that arbitrarily large integers can be passed as a parameter to the function, consider the following statements.

i. The function f terminates for finitely many different values of n ≥ 1.

ii. The function f terminates for infinitely many different values of n ≥ 1.

iii. The function f does not terminate for finitely many different values of n ≥ 1.

iv. The function f does not terminate for infinitely many different values of n ≥ 1.

Which one of the following options is true of the above?

- Gate IT 2007

A. i and iii
B. i and iv
C. ii and iii
D. ii and iv

Solution: D. ii and iv

Explanation:

The function f is terminated for any value of n which is, power of 2. There are infinite numbers, which are power of 2.

Therefore,

(ii) The function f terminates for infinitely many different values of n ≥ 1.
In this "infinitely many different values of n>=1" means infinite numbers. So, It is correct.

(i) The function f terminates for finitely many different values of n ≥ 1.
In this "finitely many different values of n>=1" means finite numbers. So, It is incorrect.

(iii) The function f does not terminate for finitely many different values of n ≥ 1.
In this "finitely many different values of n>=1" means finite numbers. So, It is incorrect.

(iv) The function f does not terminate for infinitely many different values of n ≥ 1.

In this "infinitely many different values of n>=1" means infinite numbers. So, It is correct.

# Q4. On Recursion

Consider the code fragment written in C below :
void f (int n)
{
if (n <=1)
{
printf ("%d", n);
}
else
{
f (n/2);
printf ("%d", n%2);
}
}

What does f(173) print?

- Gate IT 2008

A. 010110101
B. 010101101
C. 10110101
D. 10101101

Solution: D. 10101101

Explanation:

The f(int n) function return binary digit of decimal n number.
Binary number of 172 is 10101101.

# Q5. On Recursion

In general, in a recursive and non-recursive implementation of a problem (program) :
- UGC NET CS 2015 Dec - II

A. Both time and space complexities are better in recursive than in non-recursive program.
B. Both time and space complexities are better in non-recursive than in recursive program
C. Time complexity is better in recursive version but space complexity is better in non-recursive version of the program.
D. Space complexity is better in recursive version but time complexity is better in non-recursive version of the program.

Solution:
B. Both time and space complexities are better in non-recursive than in recursive program.

Explanation:
In general, in a recursive and non-recursive implementation of a problem (program), Both time and space complexities are better in non-recursive than in recursive program.

# Q6. On Recursion

Consider the following C-program:

void foo(int n, int sum)
{
int k = 0, j = 0;
if (n = = 0) return;
k = n % 10;
j = n / 10;
sum = sum + k;
foo (j, sum);
printf ("%d,", k);
}

int main ()
{
int a = 2048, sum = 0;
foo (a, sum);
printf ("%d\n", sum);
getchar();
}

What does the above program print?

- GATE-CS-2005

A. 8, 4, 0, 2, 14
B. 8, 4, 0, 2, 0
C. 2, 0, 4, 8, 14
D. 2, 0, 4, 8, 0

Solution: D. 2, 0, 4, 8, 0

Explanation:

foo function prints all the digits of a number stored in variable a.
In code, k= n % 10 modulus operator will return the remainder. for n=2048, then k = 2048 %10 will store the value k = 8.

j is integer datatype in foo function. So, after division if the decimal part will be truncated and only the integer part will be stored in j. For j=2048/10, j = 204.8, but decimal part will truncated, so j =204.