Week 6: Recursion, Big-Oh Notation, Queue Applications

---
## Recursion

### Factorial example

---
```c++
#include <iostream>
int factorial( int n )
{
    if( n <= 1 )
        return 1;
    else
        return n * factorial( n - 1 );
}

int main()
{
    std::cout << "5!=" << factorial( 5 );
    return 0;
}
```

---
```python
factorial(5) 
   factorial(4) 
      factorial(3) 
         factorial(2) 
            factorial(1) 
               return 1 
            return 2*1 = 2 
         return 3*2 = 6 
      return 4*6 = 24 
   return 5*24 = 120
```

---
<img src="/gallery/fact5rec/8.svg" style="width:100%;" />

---
<img src="/gallery/fact5rec/7.svg" style="width:100%;" />

---
<img src="/gallery/fact5rec/6.svg" style="width:100%;" />

---
<img src="/gallery/fact5rec/5.svg" style="width:100%;" />

---
<img src="/gallery/fact5rec/4.svg" style="width:100%;" />

---
<img src="/gallery/fact5rec/3.svg" style="width:100%;" />

---
<img src="/gallery/fact5rec/2.svg" style="width:100%;" />

---
<img src="/gallery/fact5rec/1.svg" style="width:100%;" />

---
### How recursion work in stack memory

[{Demo: How Recursive Factorial Work in Memory}](https://www.cs.usfca.edu/~galles/visualization/RecFact.html)

---
### Recursion is not Function Overloading

--
The following is not recursion

```c++
struct Rectangle
{
    double a = 0;
    double b = 0;
};

double area( double a , double b )
{
    return a * b;
}

double area( Rectangle rect )
{
    return area( rect.a , rect.b ); // This is not recursion.
}
```

---
However, the following calling `area` is recursive, it calls itself

```c++
struct Rectangle
{
    double a = 0;
    double b = 0;
};

double area( Rectangle rect )
{
    return area( rect ); // This is a recursion. Very pointless and buggy function!
}
```

* infinite recurions, 
* until .red[stack memory overflow] happens, 
* and finally the program crashes.
* pointless function.
--
* **Add to your glossary**: *[Stack Memory Overflow](https://en.wikipedia.org/wiki/Stack_overflow)*

---
### **Exercise**: Power Function

--
Implement a function `power` that uses recursion to compute the power of the input number.

---
### Recursion is very important technique

--
* Tree data structure.
--
* Divide and conquer & dynamic programming algorithms.
--
* Elegant functions with less codes.

---
## Big-Oh Notation

--
### What is an Algorithm

--
> According to Donald Knuth, the word *algorithm* is derived from the name “al-Khowârizmı̂,” a ninth-century Persian mathematician.

--
#### In programming,

--
* *algorithm* is a function with clever logic. 
--
* However, it is a very general term. 
--
* The `meanArray` function is an *algorithm 
--
* Similary, `varianceArray`, `minArray`, `maxArray`, `factorial`, and `power`.

--
We are concerned about the function running time w.r.t input size `n`.

---
### How to measure an algorithm performance

#### Constant Performance

--
```c++
int sqaure( int x )
{
    int y = x * x; // T1(n) = 1
    return y; // T2(n) = 1
}
```

--
$$ T(n) = T1 + T2 = 2 $$

--
$$ O( T(n) ) = O(2) = O(1) $$

--
**constant execution time**.

---
#### Constant Performance

```c++
bool isEmpty( CharacterStackLL &stack )
{
    return stack.front == nullptr; // T(n) = 1
}
```

--
$$ T(n) = 1 $$

--
$$ O( T(n) ) = O(1) $$

--
*Related terms: Performance, complexity, growth function*

---
#### Linear Performance

--
```c++
void printLL( Node* front )
{
    Node *current = front; // T1(n) = 1

while( current != nullptr ) // T2(n) = n * ( T3 + T4 )
    {
        std::cout << current->data; // T3(n) = 1
        current = current->next; // T4(n) = 1
    }
}
```
--
$$  T(n) = T1 + T2 = 1 + n ( T3 + T4 ) = 1 + 2n $$

--
$$ O(T(n)) = O( 1 + 2n ) = O(n) $$

--
* linear in execution time.

---

---
* How to approximately estimate the function running time for $n=1000000$, i.e linked-list of **1-million** element
* **Givens**:

* The function has complexity of $ O(n) $.
    * The function executed in *2 melliseconds* when $n=2000$.