Here are my notes for the week 2’s lecture of Functional Programming Principles in Scala on Coursera.

1. Functions and Data

1.1 Classes

In Scala, a class ia defined like this:

class Rational(x: Int, y: Int) {
  def numer = x
  def denom = y
}

This definition introduces two entities:

• A new type, named Rational .
• A constructor Rational to create elements of this type.

  More →

Here are my notes for the week 2’s lecture of Functional Programming Principles in Scala on Coursera.

4. Example: Finding Fixed Points

4.1 Finding a fixed point of a function

A number x is called a fixed point of a function f if

For some functions f we can locate the fixed points by starting with an initial estimate and then by applying f in a repetitive way.

until the value does not vary anymore (or the change is sufficiently small).

More →

Here are my notes for the week 2’s lecture of Functional Programming Principles in Scala on Coursera.

1. Recursion and Tail Recursion

1.1 Examples of Recursion

/* Euclid's Algorithm */ 
def gcd(a: Int, b: Int): Int = 
  if (b == 0) a else gcd(b, a % b)

gcd(14, 21) is evaluated as follows:

gcd(14, 21)
--> if (21 == 0) 14 else gcd(21, 14 % 21)
--> if (false) 14 else gcd(21, 14 % 21)
--> gcd(21, 14 % 21)
--> gcd(21, 14)
--> if (14 == 0) 21 else gcd(14, 21 % 14)
-->> gcd(14, 7)
-->> gcd(7, 0)
--> if (0 == 0) 7 else gcd(0, 7 % 0)
--> 7

Another example:

def factorial(n: Int): Int = 
  if (n == 0) 1 else n * factorial(n - 1)

factorial(4) is evaluated as follows:

factorial(4)
--> if (4 == 0) 1 else 4 * factorial(4 - 1)
-->> 4 * factorial(3)
-->> 4 * (3 * factorial(2))
-->> 4 * (3 * (2 * factorial(1)))
-->> 4 * (3 * (2 * (1 * factorial(0)))) 
-->> 4 * (3 * (2 * (1 * 1)))

1.2 Tail Recursion

Implementation Consideration:

If a function calls itself as its last action, the function’s stack frame can be reused. This is called tail recursion.

Tail recursive functions are iterative processes.

In general, if the last action of a function consists of calling a function (which may be the same), one stack frame would be sufficient for both functions. Such calls are called tail-calls.

More →