User Tools

Site Tools


notes:discrete:fall2023:projects:mor0

MOR0

Matrix

A matrix is simply data stored within a grid. It can be thought of as a multi-dimensional array, or “an array of arrays”. For example, a 2D array may also be referred to as a matrix (a table of rows and columns). And the initialization would look something like this

int matrix[2][3] = { { 1, 7 }, { 2, 9, 6 } };

When accessing data within a matrix imagine the matrix as a coordinate grid, and the numbers you give the matrix is the coordinate point of that data within the matrix.

Like arrays, Matrices are fixed in size. You allocate the memory for it when created and it cannot be changed.

In theory, a matrix can have as many dimensions as you want. As many times as you can nest an array in an array, a matrix of that many dimensions can be created. Because that's all a matrix is, at least this type of matrix, an array of arrays to the nth degree.

Recursion

The concept of recursion is actually simple but implementing it is more challenging than you might think. Recursion works by creating a function that calls itself until it hits a base case to end/breakout of the recursion function. Along with the base case, it has another case that slowly leads to the base case.

A simple implementation of this can be seen with a function that gets the factorial value given a certain number.

Here is what that function looks like:

// Factorial function using recursion
int factorial(int n)
{
    // Base case for when the number given is 0
    if (n == 0)
    {
        return 1;
    }
 
    // Takes the given value and multiplies it by the previous factorial value
    else
    {
        // Function calls itself (calls n-1) until it reaches the base case (0)
        return n * factorial(n - 1);
    }
}

As you can see the function starts with the base case and then actually implements the logic for the function. Let's give n a value of 3. First, we are going to check if n is 0 and when it fails that check it will return 3*factorial(2), and then it will evaluate when n is 2. This pattern will continue until it evaluates n being 0. Now that the function has not been called again it returns 1 because n is 0. Now factorial(1) can complete its return, then factorial(2), and finally factorial(3). The result of factorial(3) is 6.

Properties of Recursion

Recursion can cause issues when not handled properly. The easiest way for this to happen is to cause a stack overflow.

A stack overflow occurs when a recursive function is never properly broken and repeats indefinitely until memory (the stack) is used up. This happens when the base case condition check is faulty or nonexistent.

Why Use Recursion Instead of a Loop?

There are several differences between loops and recursion. A couple of them being:

  • Loop uses repetition to go over sequential data, while recursion uses a selection structure.
  • Loops are less memory and processor intensive than recursive functions.

Recursion does have its advantages over loops though.

  • The code is easier to understand and is generally shorter.
  • Recursion can solve some problems that normal loops can not.
notes/discrete/fall2023/projects/mor0.txt · Last modified: 2023/11/16 01:24 by cfoster8