Questions & Answers of Recursion

Question No. 35

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

Question No. 147

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

Question No. 149

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

 

 

Question No. 121

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

Question No. 124

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

Question No. 149

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 = 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

Question No. 152

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

Question No. 238

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()?

Question No. 242

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

Question No. 42

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;
}

Question No. 50

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?

Question No. 51

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?

Question No. 42

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)?