**PART 1**

**Convert temperatures between Fahrenheit and Celsius ***(with functions)*

```
fn celsiustofarenheit(c: f64) -> f64 {
(c * 1.8) + 32.0
}
fn farenheittocelsius(f: f64) -> f64 {
(f - 32.0) * 5.0 / 9.0
}
fn main() {
let celsius1 = 37.0;
let celsius2 = 0.0;
let farenheit1 = 32.0;
let farenheit2 = 104.0;
// Celsius => Farenheit: (°C × 1.8) + 32 = °F
println!("{} C = {:.1} F", celsius1, celsiustofarenheit(celsius1)); // Prints 37 C = 98.6 F
println!("{} C = {:.1} F", celsius2, celsiustofarenheit(celsius2)); // Prints 0 C = 32.0 F
// Farenheit => Celsius: (°F − 32) × 5.0 / 9.0 = °C
println!("{} F = {:.1} C", farenheit1, farenheittocelsius(farenheit1)); // Prints 32 F = 0.0 C
println!("{} F = {:.1} C", farenheit2, farenheittocelsius(farenheit2)); // Prints 104 F = 40.0 C
}
```

*Output*

```
37 C = 98.6 F
0 C = 32.0 F
32 F = 0.0 C
104 F = 40.0 C
```

**Generate the nth Fibonacci number ***(with functions)*

I struggled a little bit with mutable values an how they would be passed as arguments, but made the user function as simple as possible, taking just 1 argument.

From the user facing `findfibonacci`

function, it initializes a result variable to zero and sends it to the `fibonacciround`

function, which is recursive - taking 3 sets of conditions.

The arguments taken in this function are abstracted away from the user, though the `findfibonacci`

function where `n_minus_1`

, `n_minus_2`

were equal to 0.

```
fn main() {
let n = 10; // This is our input
println!("The {}th Fibonacci number is {}", n, findfibonacci(n));
}
fn findfibonacci(n: i32) -> i32 {
let result: i32 = 0;
fibonacciround(n, 0, 0, result)
}
fn fibonacciround(n: i32, mut n_minus_1: i32, mut n_minus_2: i32, mut result: i32) -> i32 {
if n == 0 {
result
} else if n_minus_1 == 0 && n_minus_2 == 0 {
fibonacciround(n - 1, 1, 0, result)
} else {
result = n_minus_1 + n_minus_2;
n_minus_2 = n_minus_1;
n_minus_1 = result;
fibonacciround(n - 1, n_minus_1, n_minus_2, result)
}
}
```

*Output*

```
The 10th Fibonacci number is 55
```

**Print the lyrics to the Christmas carol “The Twelve Days of Christmas,” taking advantage of the repetition in the song ***(with functions)*

```
fn main() {
singsong();
}
fn singsong() {
let start = "On the ";
let start_2 = " day of Christmas\nMy true love gave to me";
let end = "And a partridge in a pear tree.";
let mut day: &str;
let song: [&str; 6] = ["A partridge in a pear tree.", "Two turtle doves,", "Three French hens,", "Four calling birds,", "Five golden rings,", "Six geese a-laying,"];
for gift in 1..=6 {
match gift {
1 => { day = "First"; }
2 => { day = "Second"; }
3 => { day = "Third"; }
4 => { day = "Fourth"; }
5 => { day = "Fifth"; }
_ => { day = "Sixth"; }
}
println!("{}{}{}", start, day, start_2);
if gift == 1 {
println!("{}", song[0]);
} else {
let mut j = gift;
loop {
if j == 1 {
break;
}
println!("{}", song[j - 1]);
j = j - 1;
}
println!("{}", end);
}
println!()
}
```

*Output*

```
On the First day of Christmas
My true love gave to me
A partridge in a pear tree.
On the Second day of Christmas
My true love gave to me
Two turtle doves,
And a partridge in a pear tree.
On the Third day of Christmas
My true love gave to me
Three French hens,
Two turtle doves,
And a partridge in a pear tree.
On the Fourth day of Christmas
My true love gave to me
Four calling birds,
Three French hens,
Two turtle doves,
And a partridge in a pear tree.
On the Fifth day of Christmas
My true love gave to me
Five golden rings,
Four calling birds,
Three French hens,
Two turtle doves,
And a partridge in a pear tree.
On the Sixth day of Christmas
My true love gave to me
Six geese a-laying,
Five golden rings,
Four calling birds,
Three French hens,
Two turtle doves,
And a partridge in a pear tree.
```

**PART 2**

**Are function calls stored on the Stack or on the Heap? Why is one more beneficial than the other?**

Function calls are **stored on the stack**, which makes them particularly quick and efficient.

There is significant benefits to having function calls being stored locally on the stack as it allows the machine to process functions as fast as possible.

If functions were stored in the heap, they would be available at all times throughout the programs lifecycle, where it may potentially be used very infrequently. Doing this would chew through unnecessary memory and slow the program down significantly.

As functions are placed on and off the stack, the machine can pop the function and all of its arguments onto the stack only when it’s needed, and then take it off the stack once it has been used, de-allocating the memory it was using.

The result is a much less resource intensive program, which will typically run faster.

**What is Memoization and how does it help executing recursion faster?**

Memoization is the process of eliminating some repetitive task by storing the results of the task in cache the first time the action is performed, and storing it in cache. Then when you need to perform task again, instead of re-doing the work, you can simply pull from the cache where the result was previously stored.

These repetitive tasks occur regularly in recursive functions - where the same task is performed many times with the same input. If we were to utilize memoization, we could rewrite the function to store the result from the first iteration, and then pull in subsequent rounds - IF it is logical and safe to do so.

When retrieving the 6th Fibonacci number using a recursive function, the 2nd Fibonacci number is called 5 times… This could be memoized, and the work wouldn’t have to …

Whilst memoization is great in performance respects, it *can add* a decent amount of complexity to what could be a simple function, so memoization should mainly be used when there are many repetitive iterations, or if speed is absolutely vital.

**What is Tail recursion (Tail Call Optimization) and how does it help executing recursion faster?**

Tail recursion exists in recursive functions where the *last* thing that is called is the recursive function itself. This generally means that the function will begin with a qualifier where if the iteration *does not* meet a condition, the recursion will break - and the tail recursion will not be called.

Tail recursion is **good practice**, as it can be optimized by the compiler.

For non tail-recursive functions, the stack depth will typically increase more, as the information from the previous iteration has not yet been fully popped off the stack, and continues to take resources for following iterations. The resources consumed will increase (at least) linearly until all iterations are completed and taken off the stack.

For tail-recursive functions, the recursive call is the last statement, therefore there are no more resources needing to be maintained by the function, and the entirety of this iteration can be popped off the stack before entering the next iteration.