Strings

A string is usually encoded as an array of char. To encode char it is common to use the ASCII Code where each character is represented as an 8 bits number namely a byte. To follow the same reasoning we say that strings are encoded as arrays of bytes. To mark the end of a string a special ASCII code is used namely 'NULL' (0).

Strings can be interpreted in a different ways. For instance the string "123" is an integer while the string "Abba" is not.

A palindrome is a string which can be read from both sides. For example "Abba" is a palindrome while "123" is not. The string "Dromedaren Alpotto planerade mord" is pallindrome while "123321" is a number but also a palindrome. For more examples check out this link.

Recursion

When the program jumps to a subroutine usually it saves the return adress in the special register $ra. Sometimes it is more practical to let subroutines call other subroutines. In this case, the programmer should take extra care and save $ra before the next jump. The most convenient way to save registers is the stack. In the case where a subroutine calls itself then this process is called recursion.

Exampel: if you want to compute 5! then you know that 5! = 1*2*3*4*5 = 120. In a higher level language you will implement the function as follows:

       factorial(n) 
          {

	       if (n==0) return 1;

	       else return n*factorial(n-1);

	  }

(check the following page for the submission rules and deadlines)

• You have to start from the following file: lab_2.s. All the commands are well explained in this file Patterson and Hennessy.

• Write a subroutine strLength_r that computes the length of a null-terminated string with recursion. Notice that in the given file there exists already a subroutine strLength which counts the length with a normal iteration (loop). Think first of a base case and a recursive step then write a recursive version.

• Write a subroutine strIsInt that checks wether a string is a positive integer or not. You are free to choose to implement it as a recursive one or iterative.

• Write a recursive subroutine strIsPalindrome_r that checks wether a string is a palindrome or not. We will assume that it doesn't matter if the letters are in capital format or not.