Recursion

Consider the recursive functions represented by the following code segment:

int bar(int n){
     if (n == 1) return 0;
     else return 1 + bar(n/2);
}
int foo(int n){
     if (n == 1) return 1;
     else return 1 + foo(bar(n));
}

The smallest positive integer n for which foo(n) returns 5 is ______. (*answer in integer*) *Note:* Ignore syntax errors (if any) in the function.

Consider the following ANSI-C function.

int func(int start, int end){
  int length=end+1-start;
  if((length<1)||(start<0)||(end<0)){ return(0); }
  if(length%3==0){
    return(func(start+1, end));
  } else if(length%3==1){
    return(1+func(start, end-1));
  } else {
    return(func(start+2, end));
  }
}

The maximum possible value that can be returned from this function is ____________. (*answer in integer*) *Note*: Ignore syntax errors (if any) in the function.

#include <stdio.h>
int foo(int S[],int size){
    if(size == 0) return 0;
    if(size == 1) return 1;
    if(S[0] != S[1]) return 1+foo(S+1,size-1);
    return foo(S+1,size-1);
}
int main(){
    int A[]={0,1,2,2,2,0,0,1,1};
    printf("%d",foo(A,9));
    return 0;
}

The value printed by the given C program is _______. (Answer in integer)

Consider the following ANSI C function:

int SomeFunction(int x, int y)
{
  if ((x == 1) || (y == 1)) return 1;
  if (x == y) return x;
  if (x > y) return SomeFunction(x - y, y);
  if (y > x) return SomeFunction(x, y - x);
}

The value returned by SomeFunction(15, 255) is __________.

Consider the following ANSI C program.

#include <stdio.h>

int foo(int x, int y, int q)
{
    if ((x <= 0) && (y <= 0))
        return q;
    if (x <= 0)
        return foo(x, y-q, q);
    if (y <= 0)
        return foo(x-q, y, q);
    return foo(x, y-q, q) + foo(x-q, y, q);
}

int main()
{
    int r = foo(15,15,10);
    printf("%d", r);
    return 0;
}

The output of the program upon execution is ________.

Consider the following C functions.

int fun1(int n) {               int fun2(int n) {
  static int i = 0;                static int i = 0;
  if (n > 0) {                     if (n > 0) {
     ++i;                             i = i + fun1(n);
     fun1(n-1);                       fun2(n-1);
  }                                }
  return(i);                       return(i);
}                                }

The return value of fun2(5) is __________.

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

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

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