Register

recursion

• retagged by
1,089 views
1 1 vote
Consider the following program :
double DO (double X , long int n )
{
double A;
if ( n = = 1 )
return X ;
A = DO (X , n / 2);
if ( n % 2 )
return X * A * A;
return A * A;
}

 

 

 

 

What does DO do ?
(A)X n
(B)n X
(C)X n+1
What number of multiplications are taking place if X = 2 and n = 37
(A)37
(B)36
(C)7
(D)6

ans wid solutn plz

1 Answer

2 2 votes

The function DO computes pow(x, n), ie, x raised to n.

For X = 2, N = 37 there would be following sequence of calls:

DO (2, 37)

    DO (2, 18)

        DO (2, 9)

            DO(2, 4)

                DO(2, 2)

                    DO(2, 1)  // end of recursion

DO(2, 1) will not have any multiplications.

For odd N there would be 2 multiplications and for even N there would be 1 multiplication.

Number of odd N's == 2 (9, 37 -> Note we exclude 1)

Number of even N's == 3 (2, 4, 18)

Therefore number of multiplications should  be 2*2 + 3*1 == 4 + 3 == 7.

Please verify if that answer is correct, I did not verify it.

Voting & Accepting an answer helps improve the community
← Previous · Transactions in SQLNext → · exception
← Previous in category · Pointer and ArrayNext in category → · exception
Position:
Show:

Related questions

8 8 votes
3 3 answers
413
413 views
GO Classes asked Jun 17
413 views
GO Classes DPP | GATE CS | C Programming | Pointer Recursion
What is the output of the following code?#include <stdio.h void update(int n, int *p) { if (n <= 0) return; *p = *p + n; update(n - 2, p); *p = *p + n; } int main() { int...
6 6 votes
2 2 answers
348
348 views
GO Classes asked Jun 17
348 views
GO Classes DPP | GATE CS | C Programming | Recursion
What is the output of the following code?#include <stdio.h int fun(int n) { int x = n; if (n <= 0) return 0; x = x + 2; return x + fun(n - 2); } int main() { printf("%d",...
5 5 votes
4 4 answers
359
359 views
GO Classes asked Jun 16
359 views
GO Classes DPP | GATE CS | C Programming | Mutual Recursion
What is the output of the following code?#include <stdio.h void g(int n); void f(int n) { if (n <= 0) return; printf("F%d ", n); g(n - 1); printf("f%d ", n); } void g(int...
6 6 votes
3 3 answers
345
345 views
GO Classes asked Jun 16
345 views
GO Classes DPP | GATE CS | C Programming | Recursion & Static with Prints
What is the output of the following code?#include <stdio.h void fun(int n) { static int x = 0; if (n == 0) return; x++; printf("%d:%d ", n, x); fun(n - 1); printf("%d:%d ...