Skip to content

Instantly share code, notes, and snippets.

@RobAWilkinson

RobAWilkinson/readme.md

Last active August 29, 2015 14:16
Show Gist options
  • Save RobAWilkinson/2efb91ffb51ab6b44e63 to your computer and use it in GitHub Desktop.
Save RobAWilkinson/2efb91ffb51ab6b44e63 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
readme.md

#Binary Search Trees/Recursion

###Learning Objectives

  • Binary Search Tree Theory
  • Creating a Binary Search Tree
  • Recursion definition
  • Sweet, sweet, Recursion

What is A binary Search tree.

Binary search trees are just a way to structure your data to allow for easy binary searching.

Its the same theory as yesterday, we want to be able to halve our results on each step.

Creating a Binary search tree in code

Lets create a class BinarySearchTree

class BinarySearchTree
  def initialize(n)
    self.value =n
  end
  self.right = nil
  self.left = nil
end

So this lets us create a binary search tree of one element, what would the function look like to add an element to our binary tree?

def add(n)
  
end

Whats the first thing we have to do?

We compare n with value and if its greater add it as right if less add it as left

def add(n)
  while(true)
    if n > self.value then
      if self.right === null then
        self.right = BinarySearchTree.new(n)
        break
      else then
        self = self.right
    else if n < self.value then
      if self.right === null then
        self.left = BinarySearchTree.new(n)
      else then
        self = self.left
    else then
      break
  end while
end

And how would we write the code to see if our tree contains an element?

def contains(query)
  found = false
  while(!found && self) do
    if query < self.value then
      self = self.left
    else if query > self.value do
      self = self.right
    else
      found = true
  end while
  found
end

###Recursion What is recursion?
Recursion breaks a big problem down into smaller problems and uses their solutions to solve it. It often requires an insight which allows the problem to be reduced to a series of simpler ones.

##Why is Recursion Important?

  • Many problems are naturally recursive. They are easier to think about recursively than iteratively. So, they lend themselves to recursive solutions.

  • It is often easier to solve a problem recursively and translate it to iterative code only if a faster algorithm is needed.

  • Recursive functions are a new way of thinking about solving problems.

  • Recursion is a popular topic for coding questions.

Real-world cases:

  • Traversing the file system

  • Core methods such as Array#flatten

###Example: Fibonacci Sequence

The Fibonacci Sequence is a good example of a problem easier to think about recursively than iteratively. It is a number sequence, where a given number is the sum of the two numbers which precede it. For example, given that F(1) = F(2) = 1:

F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

###Exercise

Without using recursion, write a function that computes the nth Fibonacci number.

	def fibo(n)
		seq = [1, 1]

		(2...n).each do
			seq.push(seq[-1] + seq[-2])
		end

		seq.last
	end

What is the Big O complexity of this function?

Should be O(n) right. This algorithm also uses O(n) space (for an array of n elements)

	def fibo(n)
		nums = [1, 1]

		(2...n).each do
			nums = nums[1], nums[0] + nums[1]
		end

		nums.last
	end

This is the exact same implementation but it uses constant space O(1)

###recursive Solution With recursion we can do the same thing in O(2**n) and O(n) space

	def fibo(n)
		return 1 if n < 3				# Base case
		return fibo(n-1) + fibo(n-2)	# Inductive case
	end

##Recursion

To write a recursive function, determine the base cases and the recursive case:

  • Base cases are the conditions in which the program produces a trivial result.
  • Recursive cases are conditions when the function references itself. Often, these will decrease a variable or a variable's length which eventually leads to the base case.

##Challenge Write a function that returns a count of the elements in an array

##Example: Factorial

We are used to thinking about the factorial as follows:

  • Factorial: F(n) = 1 * 2 * ... * n

This lends itself to the following iterative solution, with O(n) time and O(1) space. (Note we could have used reduce, but that hides the loop which determines complexity!)

def factorial(n)
	total = 1
	(2..n).each { |num| total *= num }
	total
end

There is a second way of thinking about a factorial. We notice that any number's factorial is the factorial of the preceding number times the current number:

  • Factorial: F(n) = n * F(n - 1)

This mental model of factorial lends itself to a recursive solution:

  • Base case: 0! = 1, 1! = 1.
  • Recursive case: F(n) = n * F(n - 1)

Given the above, the factorial function written recursively is:

def factorial(n)
	return 1 if n < 2
	return n * factorial(n-1)
end

This has O(n) time and O(n) space (the latter due to the stack).

###Exercise

Determine the sum of numbers from 1 to n.

Iterative: The sum of the numbers up to n is: sum_up_to(n) = 1 + 2 + ... + n-1 + n

Recursive: sum_up_to(n) = n + sum_up_to(n-1), and sum_up_to(0) = 0

# Returns the sum of 0 up to n
def sum_up_to(n)
end

Challenge: Can this possibly be done in O(1) time and O(1) space?

Answer: Yes! Use the formula sum_up_to(n) = n(n + 1)/2 = 1 + 2 + ... + n-1 + n.

##Example: Flattening an Array

Suppose we want to flatten the elements of an array of items or arrays ... of items or arrays ... of items or arrays ... ad infinitum.

For instance: [1, 2, [5, 8, [1, 2, 3, [10, 12]], [13, 15]]]

Becomes: [1, 2, 5, 8, 1, 2, 3, 10, 12, 13, 15]

(This is the Ruby function Array#flatten.)

  • Our function flatten is passed an element which is either an array or not an array. Let's break this into our familiar base case vs inductive case:

    Base: Element elem not an array, then we concatenate [elem].

    Inductive: Element elem is an array, then for each element we concatenate the array flatten elem.

Here is one recursive implementation:

def flatten(arr)
	return [arr] unless arr.is_a?(Array)

	flat_list = []
	arr.each do |elem|
		flat_list.concat(flatten elem)
	end

	flat_list
end

Challenge: Can this possibly be done iteratively?

Answer: Yes. A stack can be used to simulate recursive calls! (See the Array#flatten Ruby source).

###Binary Searching

Do you remember the BInary search function that we created yesterday? Its much easier and simpler to write recursively!

we create a function that takes 4 inputs, an array, the number we're looking for, a minimum index, and a maximum index.

func binary_search(array, query, min, max)

Lets expand this out

  function binary_search(array, query, min = 0, max = length(array)) do
    if min > max then 
      return nil

    middle = round((max-min)/2 + min)

    if query = array[middle] then
      return middle
    elsif query > array[middle] then
      binary_search(array, query, middle +1, max)
    else if query < array[middle] then
      binary_search(array, query, min, middle -1)
    
    return nil
  end function

Additional Practice

  • Exercise One

      # Return a string with spaces inbetween each letter.
  # space_out('Testing'.chars) => 'T e s t i n g'
  def space_out(chars, imin = 0)
  end

    Solution:

      def space_out(chars, imin = 0)
  	return chars[imin] if imin == chars.length-1

  	return chars[imin] + ' ' + space_out(chars, imin+1)
  end

  • Exercise Two

      # Print the contents of an array in reverse, element by element
  def print_reverse(arr, imax = a.legnth-1)
  end

    Solution:

      def print_reverse(arr, imax = arr.length-1)
  	return if imax < 0			# BASE

  	print arr[imax]

  	print_reverse arr, imax-1	# INDUCTIVE
  end

  • Exercise Three

      # Find the minimum element in an array
  #    e.g. min [6, 3, 10] => 3.
  def min(a)
  end

    Solution:

      def min(arr, imax = arr.length-1)
  	# BASE
  	return nil if imax < 0			# Empty array
  	return arr[imax] if imax == 0	# One-element array

  	# INDUCTIVE - note [3, 2].min => 2 (Array#min)
  	return [arr[imax], min(arr, imax-1)].min
  end

##Addendum

Given the above exercises, you may wonder:

  1. Why is there always a "hidden parameter" to keep track of the count? Why can't we just pass in a smaller array each call?
Passing in the same array only passes a reference to the array, which does not use additional space. 
If a new array is created upon each recursive call, we could easily increase the space requirements from O(n) to O(n^2).
  1. The above three examples could easily have been written using for loops. They also all share that the recursive step is a single returned line. Is this a general pattern?
Yes! This is called tail recusion.
It is often used by compilers to speed up recusively written functions.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment