Advertisements
Advertisements
Question
The following function task() is a part of some class. Assume ‘m’ and ‘n’ are positive integers greater than 0. Answer the questions given below along with dry / run working.
int task(int m, int n)
{ if(m=n)
return m;
else if (m>n)
return task(m-n, n);
else
return task(m, n-m)
}- What will the function task() return when the value of m=30 and n=45?
- What function does task() perform, apart from recursion?
Solution
- 15
- It returns the difference between its arguments.
Explanation:
The task function compares two arguments for equality and calls itself repeatedly until both arguments are equal.
APPEARS IN
RELATED QUESTIONS
If the Fibonacci number is defined recursively as F(n) = `{(0, "n" = 0), (1, "n" = 1), ("F"("n" - 1),+ "F"("n" - 2) "otherwise"):}`
to evaluate F(4), how many times F() is applied?
Using this recursive definition
`"a"^"n" = {(1, "if" "n" = 0), ("a" × "a"^("n" - 1), "otherwise"):}`
how many multiplications are needed to calculate a10?
What is recursive problem-solving?
Define factorial of a natural number recursively.
Power can also be defined recursively as
`"a"^"n" = {(1, "if" "n" = 0), ("a" × "a"^("n" - 1), "if n is odd"), ("a"^("n""/"2) × "a"^("n""/"2), "if n is even"):}`
Construct a recursive algorithm using this definition. How many multiplications are needed to calculate a10?
A single-square-covered board is a board of 2n x 2n squares in which one square is covered with a single square tile. Show that it is possible to cover this board with triominoes without overlap.
Give one reason, why iteration is better than recursion.
Differentiate between direct recursion and indirect recursion.
Assertion: Recursion utilises more memory as compared to iteration.
Reason: Time complexity of recursion is higher due to the overhead of maintaining the function call stack.
