Register

Recent questions tagged recursion

5 votes
5 answers
181
Number of moves of smallest disc in tower of Hanoi
______ is the number of moves of the smallest disc in Tower of Hanoi implementation where the tower consisting of 17 discs (numbered from 0 to 16) Answer given: $2^{16}$ = 65536 Please explain
______ is the number of moves of the smallest disc in Tower of Hanoi implementation where the tower consisting of 17 discs (numbered from 0 to 16)Answer given: $2^{16}$ ...
User Avatar
1 votes
1 answer
182
Finding time complexity of Dynamic programming problem
The answer to the above problem is A but I am expecting it to be D as constant amount of work is required to solve each subproblem.
The answer to the above problem is A but I am expecting it to be D as constant amount of work is required to solve each subproblem.
User Avatar
1 votes
1 answer
183
time complexity=?
void xyz(char *s) { if(s[0]=='\0') return; xyz(s+1); xyz(s+1); printf("%c",s[0]); } void main() { xyz("123"); } if the input string constant is of length $n$ then what is the time complexity? $O(2^n)$ $O(n^2)$ $O(n)$ $O(n\log n)$
void xyz(char *s) { if(s[0]=='\0') return; xyz(s+1); xyz(s+1); printf("%c",s[0]); } void main() { xyz("123"); }if the input string constant is of length $n$ then what is ...
User Avatar
1 votes
1 answer
187
How many recursive calls are made by gcd function ?
I have already gone through the links of stackoverflow on this topic but still couldn't understand it clearly , so please explain the logic behind this .
I have already gone through the links of stackoverflow on this topic but still couldn't understand it clearly , so please explain the logic behind this .
User Avatar
0 votes
1 answer
188
Size of stack required is ?
A(n) { if(n>=1) { A(n-1); // statement 1 print n; //statement 2 A(n-1);// statement 3 } }
A(n) { if(n>=1) { A(n-1); // statement 1 print n; //statement 2 A(n-1);// statement 3 } }
User Avatar
0 votes
4 answers
190
what is the output of foo(10)?
int foo(unsigned int n) { int c,x=0; while(n!=0) { if(n&01) x++; n>>=1; } return c; }
int foo(unsigned int n) { int c,x=0; while(n!=0) { if(n&01) x++; n>>=1; } return c; }
User Avatar
15 votes
4 answers
193
GATE IT 2008 | Question: 82
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? $010110101$ $010101101$ $10110101$ $10101101$
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?$010110101$...
User Avatar
59 votes
4 answers
198
GATE CSE 2014 Set 2 | Question: 40
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 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)$ wi...
User Avatar
29 votes
6 answers
199
GATE CSE 1998 | Question: 2.12
What value would the following function return for the input $x=95$? Function fun (x:integer):integer; Begin If x > 100 then fun = x – 10 Else fun = fun(fun (x+11)) End; $89$ $90$ $91$ $92$
What value would the following function return for the input $x=95$?Function fun (x:integer):integer; Begin If x 100 then fun = x – 10 Else fun = fun(fun (x+11)) End;$...
User Avatar
53 votes
5 answers
200
GATE CSE 2005 | Question: 81a
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; } } The space complexity of the above code is? $O(1)$ $O(n)$ $O(n!)$ $n^n$
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; } }The space complexity of the a...
User Avatar
64 votes
8 answers
204
GATE CSE 2007 | Question: 44
In the following C function, let $n \geq m$. int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function? $\Theta(\log_2n)$ $\Omega(n)$ $\Theta(\log_2\log_2n)$ $\Theta(\sqrt{n})$
In the following C function, let $n \geq m$.int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); }How many recursive calls are made by this function?$\Theta(\...
User Avatar
26 votes
1 answer
205
GATE CSE 2007 | Question: 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)$? $5$ $7$ $9$ $18$
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 ...
User Avatar
28 votes
3 answers
206
GATE CSE 2004 | Question: 31, ISRO2008-40
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: $5$ $6$ $7$ $8$
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:$5$$6$$7$$8$
User Avatar
33 votes
8 answers
210
GATE CSE 1991 | Question: 01,x
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___________.
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 (includin...
User Avatar
Page: