Advertisements
Advertisements
Question
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?
Solution
Power:
power (5, 2) = 5 x 5 = 25
power (x, n) raise x to the power n
Algorithm:
power (x, n)
if n = 0 --base case
1
else --recursion step
if n is odd
x * power (x, n - 1)
else
p = power (x, n/2)
p * p
To find a10:
| Power (a, 10) n = 10 even (a, 10) |
| ⇓ |
| Power (a, 5) n = 5 odd (a, 5) |
| ⇓ |
| Power (a, 4) n = 4 even (a, 4) |
| ⇓ |
| Power (a, 2) n = 2 even (a, 2) |
| ⇓ |
| Power (a, 1) n = 1 odd (a, 1) |
| ⇓ |
| Power (a, 0) n = 0 (a, 10) |
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.
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.
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?
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.
