Weightage of Recursion

Total 15 Questions have been asked from Recursion topic of Programming and Data Structures subject in previous GATE papers. Average marks 1.80.

Consider the following C program:

#include <stdio.h>

int counter = 0;

int calc (int a, int b) {
int c;

counter++;
if (b==3) return (a*a*a);
else {
c = calc(a, b/3);
return (c*c*c);
}
}

int main (){
calc(4, 81);
printf ("%d", counter);
}
The output of this program is _____.

Consider the following program written in pseudo-code. Assume that x and y are integers.

Count(x,y) {
if (y != 1){
if (x != 1) {
print("*");
Count(x/2, y);
}
else {
y = y-1;
Count(1024, y);
}
}
}

The number of times that the print statement is executed by the call Count(1024,1024) is _____.

Consider the following two functions.

 void fun1 (int n) {         if (n == 0) return;         printf ("%d", n);         fun2 (n - 2);         printf ("%d", n); } void fun2 (int n) {         if (n == 0) return;         printf ("%d", n);         fun1 (++n);         printf ("%d", n); }

The output printed when fun1 (5) is called  is

Consider the following program:

int f(int *p, int n)
{
if (n <= 1) return 0;
else return max(f(p+1,n-1),p[0]-p[1]);
}

int main()
{
int a[] = {3,5,2,6,4};
printf("%d", f(a,5));
}

Note: max(x,y) returns the maximum of x and y.
The value printed by this program is _________.

The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst case time complexity of this function is $\style{font-family:'Times New Roman'}{\mathit0(n^\alpha)}$, then the least possible value (accurate up to two decimal positions) of $\alpha$ is_________ .

Consider the following function written in the C programming languages.
void foo(char *a)
{
if(*a && *a != ‘ ‘)
{
foo(a+1);
putchar(*a);
}
}

The output of the above function on input “ABCD EFGH” is

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 _____.

Suppose you are provided with the following function declaration in the C programming language.

int partition(int a[ ], int n);

The function treats the first element of a[ ] as s pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part.
The following partially given function in the C programming language is used to find the kth smallest element in an array a[ ] of size n using the partition function. We assume $k\leq n.$

int kth_smallest(int a[ ], int n, int k)
{
int left_end = partition(a, n);
if (left_end+1 = =k)
{
Return a[left_end];
}
if(left_end+1) > k)
{
return kth_smallest(________);
}
else
{
return kth_smallest(________);
}
}

The missing argument lists are respectively

Consider the C program below.
#include <stdio.h>
int *A, stkTop;
int stkFunC(int opcode, int val)
{
static int size = 0, stkTop = 0;
switch (opcode)
{
case –1: size = val; break;
case 0: if(stkTop < size) A[stkTop++]= val; break;
default: if (stkTop) return A[– –stkTop];
}
return – 1;
}
int main( )
{
int B[20]; A = B; stkTop = –1;
stkFunc(–1, 10);
stkFunc(0, 5);
stkFunc(0, 10);
printf(“%d\n”, stkFunc(1,0)+stkFun(1,0);
}

The value printed by the above program is ______.

Consider the following recursive C function.

void get (int n)
{
if (n<1) return;
get (n–1);
get (n–3);
printf(“%d”, n);
}

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

Consider the following C program.

#include<stdio.h>
int f1(void);
int f2(void);
int f3(void);
int x = 10;
int main ( )
{
int x = 1;
x + = f1 ( ) + f2 ( ) + f3( ) + f2( );
pirntf (“%d”, x);
return 0;
}

int f1 ( ) { int x = 25; x++; return x;}
int f2 ( ) { static int x = 50; x++; return x;}
int f3 ( ) {x *= 10; return x};

The output of the program is ______.

What is the return value of f(p,p), if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.
int f (int &x, int c) {
c = c - 1;
if (c==0) return 1;
x = x + 1;
return f(x,c) * x;
}

The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed.
void find_and_replace (char *A, char *oldc, char *newc) {
for (int i=0; i<5; i++)
for (int j=0; j<3; j++)
if (A[i] == oldc[j]) A[i] = newc[j];
}

The procedure is tested with the following four test cases.

 (1) oldc = “abc”, newc = “dab” (2) oldc = “cde”, newc = “bcd” (3) oldc = “bca”, newc = “cda” (4) oldc = “abc”, newc = “bac”

The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?

The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed.
void find_and_replace (char *A, char *oldc, char *newc) {
for (int i=0; i<5; i++)
for (int j=0; j<3; j++)
if (A[i] == oldc[j]) A[i] = newc[j];
}

The procedure is tested with the following four test cases.

 (1) oldc = “abc”, newc = “dab” (2) oldc = “cde”, newc = “bcd” (3) oldc = “bca”, newc = “cda” (4) oldc = “abc”, newc = “bac”

If array A is made to hold the string “abcde”, which of the above four test cases will be successful in exposing the flaw in this procedure?

Consider the following C function:

int f(int n)
{static int r = 0;
if (n <= 0) return 1;
if (n > 3)
{r = n;
return f(n-2)+2;
}
return f(n-1)+r;
}

What is the value of f(5)?