Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# Recitation Session 1
We will work on tail recursion in this session.
## Exercise 1: Factorial
Recall the factorial function that you saw in class
```scala
def factorial(n: Int): Int = if (n <= 0) 1 else n * factorial(n - 1)
```
Define a tail recursive version of it
```scala
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.
```scala
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?
```scala
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
```
```scala
def fibonacci(n: Int): Int = ???
```