# Recursion and Sorting in the MIPS Assembly Language

### Recursion (Factorial) in MIPS assembly language

Recursion  occurs when a function/procedure calls itself. Following is the C++ code of a program that performs the factorial operation through recursion. It has two parts. The first part is the main part of the program that takes some integer as the input from the user, passes this number on to the factorial function, gets the result back from the factorial function and displays the result. The second part is the factorial procedure which performs the factorial operation by recursively calling itself until the base case is reached, at which point the nested calls to the factorial procedure start returning.

### Recursion example in c language

```int main ()

{

int x;

cin >> x;

cout << fact(x);

return 0;

}

int fact (int n)

{

if (n < 1)                      //Do not enter a negative number

{

return (1);          //Base Case

}

else

{

return n*fact(n-1); //Recursive call by the function to itself

}

}```

Recursive Factorial in MIPS using pcspim

You are required to do the following:

1. Take some integer as input from the user on run time by using the console of PCSPIM.
2. Make a factorial procedure and pass the input to it.
3. Calculate the factorial in a recursive manner.
4. Get the result back in the main part of your program and print it on the console.

MIPS assembly language code to calculate factorial of a number with recursion is given below.  Comment is provided with each instruction for better understanding of user.

Type and run this program for the number 7. What is the result: 5040

The first value pushed on to the stack is the value of \$ra which contains the return address to the main after the jal fact call in the main, the second value pushed on to the stack is the value in \$a0 for the first time which is n = 7, the third value pushed on to the stack is the value of \$ra which contains the return address within the fact function after the jal fact call from within fact and the fourth value pushed on to the stack is the value in \$a0 after doing (n-1), i.e., 6 for this example.

What is moved into \$ra when the function fact is called for the first time and why: 0x00400040 is moved into \$ra when the function fact is called for the very first time from the main. It is the value of the return address inside the main after the jal fact instruction. What is moved into \$ra when the function fact is called for the second time and why: 0x004000a0 is moved into \$ra when the function fact is called from within itself. It is the value of the return address inside the function fact after the jal fact instruction.

The stack grows until the recursion meets the base condition. Until that time, on each function call the value of \$a0 is decremented by 1 to perform (n-1) and the function fact is called to perform fact(n-1). Each time the value of \$ra and \$a0 are pushed on to the stack before performing any other operation. Once the base condition is met, recursive procedure calls start to return with appropriate value in \$v0 and on each return the respective values of \$a0 and \$ra are popped in proper order until we reach the main, thus the stack shrinks. At this time the stack is at its original state from where we started.

### SORTING in MIPS assembly language using pcspim

The following C++ Code sorts a given array using the bubble sort algorithm. It is composed of the main part and two functions. The array is defined in the main and the function/procedure sort is called from the main. The procedure sort calls the procedure swap if the elements are not already sorted and so on. (This code has been taken from your text book)

### Sorting code in c language

```int main ()

{

int v = {5, 4, 3, 2, 1};

int n=5;

sort(v[], n);

return 0;

}

int sort(int v[], int n)

{

int i,j;

for (i=0; i<n; i++)

{

for (j=i-1; j>=0 && v[j] > v[j+1]; j--)

{

swap(v[], j);

}

}

}

int swap(int v[], int k)

{

int temp;

temp = v[k];

v[k] = v[k+1];

v[k+1] = temp;

}```

### Performing Sorting of an Integer Array in the MIPS Assembly Language

following code for the procedure sort and procedure swap on this work

Code: