recitation-session-1.md

Recitation Session 1

We will work on tail recursion in this session.

Exercise 1: Factorial

Recall the factorial function that you saw in class

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

Define a tail recursive version of it

def factorial(n: Int): Int = fact(n, 1)
@tailrec
def fact(n: Int, acc: Int): Int = ???

What would be the advantage of making fact an inner function to factorial?

Exercise 2: Sum of elements on a list

Define a function that takes a list of integers and sums them. You can use the functions head, tail, and isEmpty on lists, as you have seen for your homework.

def sumList(ls: List[Int]): Int = ???

Convert your definition into a tail-recursive one.

Exercise 3: Fast exponentiation

Fast exponentiation is a technique to optimize the exponentiation of numbers:

b²ⁿ = (b²)ⁿ = (bⁿ)²
b²ⁿ⁺¹ = b * b²ⁿ

Define a function that implements this fast exponentiation. Can you define a tail recursive version as well?

def fastExp(base: Int, exp: Int): Int = ???

Exercise 4: Tail recursive Fibonacci

Define a function that computes the nth Fibonacci number. Can you define a tail recursive version as well? The Fibonacci recurrence is given as follows:

fib(n) = 1 | n = 0, 1
fib(n) = fib(n - 1) + fib(n - 2) | otherwise

def fibonacci(n: Int): Int = ???