GATE CS Recursion questions

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 …

#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 C functions. int fun1(int n) { static int i= 0; if (n > 0) { ++i; fun1(n-1); } return (i); } int fun2(int n) { static int i= 0; if (n>0) { i = i+ fun1 (n) ; fun2(n-1) ; } return (i); } The return value of $\text{fun}2 (5)$ is _________

Consider the following $\text{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 C functions foo and bar given below: int foo(int val) { int x=0; while(val > 0) { x = x + foo(val--); } return val; } int bar(int val) { int x = 0; while(val > 0) { x= x + bar(val-1); } return val; } Invocations of $foo(3)$ and $bar(3)$ will result in:

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 $\text{fun1}(5)$ is called is

Consider the following function written in the C programming langauge : 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 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$:_____.

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

double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += foo(i); } return sum; } } Suppose we modify the above function $foo()$ and stores the value of $foo(i) \ 0 \leq i < n$, as and when they are computed. With this modification the time complexity for function $foo()$ is significantly …

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:

Consider the following recursive function: function fib (n:integer);integer; begin if (n=0) or (n=1) then fib := 1 else fib := fib(n-1) + fib(n-2) end; The above function is run on a computer with a stack of $64$ bytes. Assuming that only return address and parameter are passed on the stack, and that an integer value and an address takes $2$ bytes each, …

Consider the following recursive definition of $fib$: fib(n) := if n = 0 then 1 else if n = 1 then 1 else fib(n-1) + fib(n-2) The number of times $fib$ is called (including the first call) for evaluation of $fib(7)$ is___________.