## Description

__QUESTION 1 (100 marks)__

Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. A function is considered recursive if it calls itself.

The following function computes *x ^{n}* recursively, where

*x*is an integer number and

*n*is a non-negative integer number.

int power(int x, unsigned int n)

{

int y;

if (n == 0)Â Â Â Â Â Â return 1;

if (n & 1)Â Â Â Â Â Â return x * power(x, n – 1);

else

{ y = power(x, n >> 1);Â Â Â Â Â return y * y;

}Â }

Draw ** a detailed flowchart **and write an ARM assembly

**to calculate**

__program__*x*

^{n}**, where**

__using the above recursive function__*n*is passed-by-value through the stack to the function and the returned value is stored in the stack just above the parameter.

__No other registers may be modified by the__

__power__

__function.__Once the control is

*returned back from the function (i.e., after calculating*

__completely__*x*), the returned value must be stored in a local variable (called

^{n}*result*) in the main function.

*Your code should be highly optimized, i.e., use as little number of instructions as possible.*You should utilize a big enough stack so that you can calculate *x ^{n}* for various

*n*values.

How many stack frames are needed to calculate *x ^{n}*, when

*n*= 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12?