Recursion Notes

Recursion notes

Divide conquer glue

ALWAYS USE BASE CASE

def sum(list: List[Int]): Int = {
	if(list.isEmpty) { 0 }
	else { list.head + sum(list.tail) }
}

list(2,4,6,8,10)
2 (list.head)    DIVIDE    (4,6,8,10) (list.head)
                 CONQUER    sum(list.tail) (28)
     GLUE
     (+)

list.head + sum(list.tail)

30

=====

def length(list: List[Int]): Int = {

}

list(2,4,6,8,10)

2  DIVIDE  (4,6,8,10)
   CONQ    (4)  length(list.tail)
   GLUE
1 + 4     1 + length(list.tail)

======

def max(list: List[Int]): Int = {

}

list(2,4,6,6,8,3)

2 DIVIDE (4,6,6,8,3)
  CONQ   (8) max(list.tail)
  GLUE
2 > 10    list.head > max(list.tail)
8

=======================
-----------------------
=======================

Maps-- key value pairs

"a set is a set is a set"

val s = Set(1,3,5)
this is an immutable set

s(3)-- s contains 3

s + 7: adds 7 to set

===

val myMap = Map("Cat" -> 3, "dog" -> 5)
myMap("dog")
myMap.contains("fox")

===

there are also Options

myMap.get("Cat") => Option[Int] = Some(3)

myMap.getOrElse("fox",0)