CSC 203 Final: Recursion, Searching, Sorting

Recursion

a function that calls itself from within. It helps to visualize a complex problem into repeatable basic steps.

Base condition (base case)

the condition that tells a recursive function when to stop executing and return a value.

Divide and conquer

breaking a large problem into smaller subproblems that are easier to solve one at a time.

Factorial

the sum of multiplying integers from n down to 1. n is represented as n!

6 would be 6 x 5 x 4 x 3 x 2 x 1 = 720

What happens when you recursively find a factorial?

Create a function called factorial that has an input of n. We want to find the factorial of n.

• First, create a base case for this function. We want to multiply n by every number from n-1 all the way down to 1. So our base case is if n <= 1: return 1

• For the most part, this line (base case) is going to be skipped until we get to 1. But until we get to 1, we need to multiply every number on our way down to 1. 

• We will need to return our current number else: n * factorial(n-1).

• The function keeps calling itself and reducing n by 1 since factorial(n-1) would be unknown initially.

• Nothing is calculated until the base case is reached.

• Once n == 1, the function starts returning values back up the call stack.

• Each return multiplies the current number by the result from the previous call until n! is reached.

Recursion: factorial function

def f(n):

    if n <= 1:

        return 1

    else:

        return n * f(n - 1)

Fibonacci sequence

Begins with 0 and 1. Thereafter, each term is the sum of the previous two terms.

• 0, 1, 1, 2, 3, 5, 8, 13, 21

0 + 1 = 1

0, 1 + 1 = 2

0, 1, 1 + 2 = 3

0, 1, 1, 2 + 3 = 5

0, 1, 1, 2, 3 + 5 = 8

0, 1, 1, 2, 3, 5 + 8 = 13

0, 1, 1, 2, 3, 5, 8 + 13 = 21

The Fibonacci sequence may be defined recursively as follows:

• fibonacci(0) is defined to be 0

• fibonacci(1) is defined to be 1

• fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2)

There are two base cases for the fibonacci calculation:

• fibonacci(0) is 0, and

• fibonacci(1) is 1

What happens when you recursively find a fibonacci sequence?

Tests base cases: If n == 0 or n == 1: return n because fibonacci(0) is 0 and fibonacci(1) is 1

else:

• Fibonacci is defined as current number = previous number + the one before that. If you want the nth Fibonacci number: n - 1 gives you the previous Fibonacci number and n - 2 gives you the one before the previous. Add them up

Recursion: fibonacci function

def f(n):

    if n==0 or n==1: #or if n in (0,1)

        return n

    else:

        return f(n-1) + f(n-2)

Linear search

Searches each element in an array sequentially.

Start from the leftmost element and one by one compares the search key with each element of the array.

• If the search key matches with an element, return its index.

• If there are duplicate values in the array, the linear search returns the index of the first element that matches the search key.

• If the search key doesn't match with any of the elements, return -1.

enumerate()

adds a counter to each item in a list or any other iterable, and returns a list of tuples containing the index position and the element for each element of the iterable. 

• It turns the iterable into something we can loop through using indexes, where each item comes with its number (starting from 0 by default). 

x = ('apple', 'banana', 'cherry')

y = enumerate(x)

print(list(y))

[(0, 'apple'), (1, 'banana'), (2, 'cherry')]

Linear search function

def f(data, search_key):

    for index, value in enumerate(data):

        if value == search_key:

            return index

    return -1

Search key

the value being searched for in a list or array.

Sentinel value

a special value (such as -1) returned when a search key is not found.

Selection sort

In ascending order: its first iteration selects the lowest value in the array and swaps it with the first element. The second iteration selects the second-lowest value (which is in the unsorted portion to the right of the sorted portion) and swaps it with the second element. The algorithm continues until the numbers are in increasing order

Selection sort function

def selection_sort(data) :

    for index1 in range(len(data) - 1):

smallest = index1 # first index of remaining array

for index2 in range(index1 + 1, len(data)) :

    if data[index2] < data[smallest]:

        smallest = index2

data[smallest], data[index1] = data[index1], data[smallest]

print_ pass(data, index1 + 1, smallest)

Insertion sort

In ascending order: if you’re given an array

1. Work left to right

2. Examine each item and compare it to items on its left

3. Insert the item in the correct position in the array

The array will form sorted and unsorted portions.

Insertion sort function

def insertion_sort(data):

    #loop over len(data) - 1 elements

    for next in range(1, len(data)):

insert = data[next] # value to insert

move_item = next # location to place element

    #search for place to put current element

    while move_item › 0 and data [move_item - 1] > insert:

        #shift element right one slot

        data [move_item] = data [move_item - 1]

         move_item -= 1

    data[move_item] = insert # place inserted element

    print_pass(data, next, move_item) #output pass of algorithm

Sorted portion

the part of the array that is already sorted.

Unsorted portion

the part of the array that has not yet been sorted.