Introduction (Program Functionality Description)
This week you are going to write a single recursive function m-file to perform Gauss Elimination with partial pivoting on a system of linear algebraic equations. Your function will be passed (through the header) a square [A] matrix and a matching [b] column vector. Your function will return the [x] solution vector to the matrix equations [A][x] = [b].

Deliverables
You will upload to Canvas a single file, titled LastNameFirstInit_Lab7.m, containing the results of Task #1, below.

Introduction to Recursion
Recursion is a programming concept in which a function, when asked to perform process A on system Q, rather than performing process A on system Q, instead
1) performs process B (a subset of process A) on system Q, resulting in a system that looks like Q, but may be “smaller” or “simpler” is some manner (let’s call this system R),
2) launches a new instance of itself, asking the new instance to perform process A on the new system R,
3) waits,
4) receives from the new instance the results of process A performed on system R,
5) performs process C (a different subset of process A), which uses the results it received from the new instance, along with it’s own remains of system Q, n what it receives from the new instance.
The result of this extended process must be equivalent to performing process A on the original system Q (which is what it was asked to do). There are a couple important facets missing from the above description – they will be dealt with later.

Terminology
When a function launches a new instance of itself, it is often referred to as spawning. Thus, the spawned instance is called the child, and the spawner is called the parent. An instance can be both a child and a parent at the same time.
When a parent sends information to its child, I refer to it as “passing down” the information.
When a child sends information to its parent, I refer to it as “passing back” or “passing up” the
information.

Multiple instances of a single program?
It may seem outrageous to have multiple instances of a single program running, but consider the following. Imagine your currently-running function .m-file needs to execute the line of code:
y = cos(0.75)
When MATLAB gets to this line of code, it knows to go the hard drive, find the file named cos.m, launch a processor-based copy of the file, and send to it the value 0.75. While the new program runs, your function is still running, waiting patiently for the results to be returned to it. Now, imagine that your currently running function (KahunaB_Lab7.m) needs to execute the line of code:
x = KahunaB_Lab7(A,b)
MATLAB will go to the hard drive, find the file named KahunaB_Lab7.m, spawn (launch) a new processor-based instance (copy) of the file, and pass to it the values in data structure A and the data structure b. The current instance of the function (the parent) is unaffected – it itself is merely an earlier-spawned, processor-based instance of the actual file on the hard drive. The current instance behaves the same as if it had called the cos built-in function. It waits patiently for the results to be returned. No data structures in the parent instance are affected – remember, the new instance is operating in its own little variable workspace, just as the function cos was when it was running. Keep in mind, it is possible that the “current” instance of KahunaB_Lab7 was actually spawned by a previously running instance of KahunaB_Lab7. It is also possible that the “new” instance of KahunaB_lab6 will spawn yet another instance of KahunaB_Lab7.

Important to grasp recursion concepts
There are several concepts to recursive programming that may take some time to get used to, so you may as well start on them now:
1. There can be multiple instances of one function running at the same time. All but the most recently-spawned instance is waiting patiently for its child to return a solution to its question (just as, earlier in the lab session, many of you were waiting impatiently for your “child” classmate to return the factors of the number handed to him/her).
2. The multiple instances exist in a parent-child-grandchild-greatgrandchild, etc. hierarchy.
3. Each instance is aware only of what it was given by its parent and what it gets back from its child. I repeat, each instance has NO KNOWLEDGE of its parent’s variable workspace.
4. Each instance has its own copy of any variables, so changing a variable in one instance has no effect on any other instance’s variables, and
5. The data structure one instance refers to as ‘x’ may be a completely different data structure than what any other instance refers to as ‘x’. This one’s a biggie.

Critical aspects of a recursive function
During the in-class exercise, we saw that a recursive function’s behavior is different if it is the terminal (last) instance, vs. if it is a non-terminal instance. However, we must remember that there is only one version of the code. This implies that our function will need to include branching – one block of code that is performed if the instance is the terminal instance, and another block of code that is performed if the instance is non-terminal. This branching further implies another facet of the code. How does an instance know if it is the terminal instance? In total, there are five critical components of any recursive function. They are:
1. Code needed to identify whether or not this is the terminal instance
2. What the code must do if this is the terminal instance
3. If the instance is non-terminal, then
4. what the code must to in order to identify the smaller or simpler system that it will pass to its child,
5. the pawning of the child, and
6. what the non-terminal instance does with the results it got back from its child, in order to complete the solution of the problem it was given by its parent
Part 2 and Part 3 will be contained within an if-else statement, i.e. if this instance is terminal do Part 2, else do Part 3.
Inherent in part 3)a. What does it do on the way down? is the question, what does a “smaller” system look like. This is a good starting point of the recursive programming process.
In the next section you can find code that recursively performs the in-class exercise. It explains the structure and components of a recursive process.

Rough Outline of Function Script
Having performed Gauss Elimination with partial pivoting for the HW, you are hopefully familiar with the process. There are four important steps to recursion:
• Identify what a “smaller” system looks like
I discussed this in the lecture on Gauss Elimination. If you don’t remember, go through the posted example, and see if you can figure it out.
• Identify the process to reach the smaller system
This was also discussed in lecture. One part that we haven’t discussed yet is the importance of identifying the format of the information passed down to the child instance. It must be in the same format as the information that was passed into the current instance from its parent.
• Identify when to stop
What is the condition that causes this iteration to not perform row operations?
Identify the upward propagation process
This is interesting for Gauss Elimination. There are essentially three substeps:
• identify what information the current instance gets back from its child, in the reference frame of the current instance (as opposed to what it is in the reference frame of the child)
• identify what information the parent of the current instance is expecting to get back from the current instance, again in the reference frame of the current instance
• create the latter information, probably using or including the former information

Write the Outline
You are not required to write an outline, but it is probably a good idea. If you come to me or the TA’s later with questions or code that imply that you don’t really get the process of what’s going on, we will probably request you to write an RPO.
Once you have decided how you are going to handle the concerns above, it is time to write your RPO. Remember that your RPO must include an accurate representation of all loops and branching.

Task #1
Write a recursive function to solve a system of linear algebraic equations using Gauss Elimination with partial pivoting. Your function will be passed a square [A] matrix and a corresponding (same number of rows) [b] column vector. Your function should return to its calling program the answer to the matrix equation [A][x] = [b].
Your function should also perform the minimum amount of work both a) in identifying the system to pass to its child, and b) in processing the answer it receives from its child to identify the answer it must pass back to its parent.

Some Hints for Your Script (LastNameFirstInit_Lab7.m)
a) To refer to the portion of matrix A from a13 to a45, the syntax is A(1:4, 3:5)
b) To refer to the entire 3rd column of matrix A, use A(:, 3)
c) The above syntax can be on the right hand side of an assignment statement to retrieve the values from the matrix, or on the left hand side to store values into the matrix.

Function Output
Your program will produce no output to the screen. It must return to its parent the solution to the matrix equation [A][x] = [b].

Code for Finding the Prime Factors of a Number Recursively
1 % We always start with our function header. We are passed
2 % in a single number.
3 function factors = recursive_factorize(prod)
4
5 % I usually start with the terminal instance. According to
6 % the algorithm we used in class, if the function receives a
7 % one (1) through the header, then it is the terminal
8 % instance, and it returns a null matrix.
9 if prod == 1
10 factors = []
11
12 % Note that the entire rest of this program is in the
13 % ‘else’ portion of this if-else statement. So if prod = 1,
14 % the null array is immediately returned to the parent
15
16 else
15 % The first factor we check for is 2.
16 fac = 2
17
18 % We keep going until we find a factor, so I’m going to
19 % use a while loop. To ensure we get into that while
20 % loop I’m going to use a gateway variable.
21 found = 0;
22 while ~found
23 if mod(prod,fac) == 0
22 % This is what we do if identify a “smaller
23 % system” to pass to our child
24 prod = prod / fac
25
26 % The function is recursive. This instance waits
27 % here for the child to respond.
28 factors = recursive_factorize(prod)
29
30 % This is what we do to convert our child’s
31 % response into the response we will pass back to
32 % our parent.
33 factors = [fac, factors]
34
35 % We need this to quit the while loop and
36 % actually pass the result back to our parent.
37 found = 1;
38
39 % if fac is not a factor of prod, we continue our
40 % search by incrementing fac and repeating the loop.
41 % How we increment fac depends on the value of fac
42 elseif fac = 2
43 fac = 3
44 else
45 fac = fac + 2
46 end %inner else-in
47 end %while
48 end %main else-if
49 end % function