# Lab 5 Notes

# Introduction to Recursion

# Note from math class

# 5! == (5 * 4 * 3 * 2 * 1) == 120

# How could we write this function in code?

# int factorial(int n) {

# if (n <= 1) {

# return 1;

# }

# else {

# return n * factorial(n - 1);

# }

# }

# Or a cooler way.

# int factorial(int n) {

# return (n <= 1) ? 1 : n * factorial(n - 1);

# }

# So what is the computer actually doing here?

# //1) 5 * factorial(5 - 1)

# //2) 4 * factorial(4 - 1)

# //3) 3 * factorial(3 - 1)

# //4) 2 * factorial(2 - 1)

# //5) return 1

# //So now we have the first difnitive answer

# //to return from a function call

# //So it goes back down the list with acutal results

# //6) return 2 * 1

# //7) return 3 * 2

# //8) return 4 * 6

# //9) return 5 * 24

# //So we finally return (5 * 24)

# //Wich gives us the answer 120

# Binary Search and Recursion

# What is Binary Search?

# Say we have a list of SORTED numbers to search through like so.

# {1, 3, 4, 5, 8, 10, 12}

# And we wanted to find the number 3.

# /*

# Find the middle of the array

# Check if the desired number is equal, less,

# or greater then the middle number

# If it's equal we are done return the middle index.

# But it's not it is less than '5'

# So we now know its in this section of the array

# {1, 3, 4}

# So we call the function again within our function

# but limit the high and low indecies to 0 and the middle - 1

# Now of course the middle number is 3 which is what we wanted!

# */