Page 49 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes
Note that using mult to multiply by 4 is generally a slow instruction compared to
the doubling a value twice, or logical left shifting by 2 bits.
In ELSE2 we need to access arr[ size - 1 ]. This then has to be placed on the stack
because we’ll need to use the value after the jal call.

We use andi (bitwise and immediate) to test for even or odd. Essentially we mask all
but the least significant bit and test if that value is 0 or 1. Fortunately, this trick
works for UB and 2C representations.

ELSE3 is quite short because we don’t access the array elements. We don’t even need
to worry about $v0 because the call to jal sumOdd fills it in for us. All we have to do
is to restore the return address and jump back.

Array access tends to bloat the length of recursive function code in assembly language.
Conclusion
If you were to translate a plain C function, which had calls to helper functions, you’d find
the code to be very similar to the recursive function call.

The main difference is jal does not call the same function. It calls a different one. However,
it’s all pretty much the same after that. The best way to see this is to write a non-recursive
function in C, with helper functions, then translate it back.

Question
Summarise it in your own words.
Source: http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Mips/case_rec.html

3.3 Summary

Recursion is a computer programming technique involving the use of a procedure,
subroutine, function, or algorithm that calls itself in a step having a termination condition.

Recursive algorithms break down a problem into smaller pieces which you either already
know the answer to, or can solve by applying the same algorithm to each piece, and then
combining the results.

Recursion may provide a simpler solution than an iterative one.
A recursive function is a function that calls itself during its execution.

A function is called “recursive” if a statement within body of that function calls the same
function.
Recursive functions are common in computer science because they allow programmers to
write efficient programs using a minimal amount of code.
The speed of a recursive program is slower because of stack overheads.

If proper cases are not included in the function to stop the execution, the recursion will
repeat forever, causing the program to crash, or worse yet, hang the entire computer
system.

3.4 Keywords

Algorithm: An algorithm is a set of instructions, sometimes called a procedure or a function, that
is used to perform a certain task.

42 LOVELY PROFESSIONAL UNIVERSITY