# Lab 4: Fibonacci Sequence

## Overview

You will write a program to calculate the Fibonacci Sequence of a number using pointers.

### Fibonacci Sequence

The Fibonacci Sequence is a pattern that is found in the real world. Search Google Images for more pictures!

The Fibonacci number sequence starts with

```0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
```

You can calculate the next number in sequence by adding the two previous numbers, starting with 0 and 1

```        0
1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
. . .
```
 n = 0 1 2 3 4 5 6 7 8 9 10 11 x n = 0 1 1 2 3 5 8 13 21 34 55 89

Resources

### Pointers in C

C uses pointers to pass the address of a location in memory. Directly modifying the contents of memory has some benefits.

#### Modifying Values by Reference

C passes values to functions by default, not a pointer. These values are assigned a new a location in memory.

```#include <stdio.h>

int my_func(int, int);

int main(void) {

int x = 5;
int y = 6;

int result = my_func(x, y);

// These values are still x = 5 and y =6.
printf("x = %d; y = %d\n", x, y);
printf("result = %d \n", result);

return 0;
}

int my_func(int x, int y)
{
// int x and int y are values limited to this function only
x = 9;
y = 11;

return x + y;
}
```
Output
```x = 5; y = 6
result = 20
```

However, you can pass the pointer to a function to change the value of the original memory location.

```int my_func(int *, int *);

int main(void) {

int x = 5;
int y = 6;

int result = my_func(&x, &y);

// These values have changed! x = 9 and y = 11.
printf("x = %d; y = %d\n", x, y);
printf("result = %d \n", result);

return 0;
}

int my_func(int *x, int *y)
{
// int x and int y are pointers to memory locations.
// Modifying x and y change the values of the caller
*x = 9;
*y = 11;

return *x + *y;
}
```
Output
```x = 9; y = 11
result = 20
```

Passing arguments by reference allows you to return multiple variables from a function by modifying the contents of the original pointer.

#### Arrays

Another use of pointers is for arrays and strings because C does not an array or string type. Instead, the variable declaration is the address of the first value in the array. The `[]` syntax is just another way to work with arrays. Consider these three examples.

```// These three declarations are the same
char string1="Some text";
char string2={'S','o','m','e',' ','t','e','x','t','\0'};
char *string3 = "Some text";

// Print the char arrays directly
printf("%s \n", string1);
printf("%s \n", string2);
printf("%s \n", string3);
printf("\n");

// Print each char of each array using [] syntax
for (int i = 0; i < 10; i++)
{
printf("%d   \t", string1[i]);
printf("%d   \t", string2[i]);
printf("%d   \n", string3[i]);
}

printf("\n");

// Print each char of each array using the memory offset
for (int i = 0; i < 10; i++)
{
char char1 = *(string1 + i);
char char2 = *(string2 + i);
char char3 = *(string3 + i);
printf("%d   \t", char1);
printf("%d   \t", char2);
printf("%d   \n", char3);
}
```
Output
```Some text
Some text
Some text

83     83     83
111    111    111
109    109    109
101    101    101
32     32     32
116    116    116
101    101    101
120    120    120
116    116    116
0      0      0

83     83     83
111    111    111
109    109    109
101    101    101
32     32     32
116    116    116
101    101    101
120    120    120
116    116    116
0      0      0
```

Resource:

## Task 1: Calculate the Fibonacci Sequence

1. Open up ide.judge0.com VSC and GCC. Use the Complete C Template.

2. Calculate the Fibonacci number up to the 10th sequence.

 n = 0 1 2 3 4 5 6 7 8 9 10 11 x n = 0 1 1 2 3 5 8 13 21 34 55 89

## Task 2: Create a Function with Pointers

You saw that your algorithm has three variables: `previous`, `next`, and `swap`

Now, you will do all of the work in a function called `calc_fibonacci()`. Here is the program flow:

1. In `main()`, you will call function `calc_fibonacci()` and pass variables `previous` and `next`, starting with 0 and 1.

2. You will perform the calculation in `calc_fibonacci()`.

3. `calc_fibonacci()` will return the next number in the Fibonacci sequence.

4. You will print that number in `main()`.

5. Repeat `n` times.

You might wonder how you can keep track of the previous number if `calc_fibonacci()` only returns `next`. The answer is to use a pointer! The function returns the next value in the sequence and updates the previous value in memory.

1. Create a function using this prototype

```/**
* Calculates the next Fibonacci number
* unsigned int next:        The next number in the Fibonacci sequence
* unsigned int *previous:   The pointer to the previous number in the Fibonacci sequence
* return value:             The next number in the Fibonacci sequence (next + previous)
*/
unsigned int calc_fibonacci(unsigned int, unsigned int*);
```
2. Start with this code in `main()`.

```int count = 10;

unsigned int previous = 0;
unsigned int next = 1;

printf("%u ", previous);

for (int i = 0; i < count; i++)
{
printf("%u ", next);

// Only modify the following line
// call function with prototype: unsigned int calc_fibonacci(unsigned int, unsigned int *)
}
```
3. Calculate the value in `calc_fibonacci()`

4. Print the value in `main()`.

5. Continue n times.

## Task 3: Implement Command line Args

1. Pass a user provided value into `fibonacci.exe` using command line args.

2. Print this message if there are no args:

```Usage: fibonacci [integer]
```
3. Determine the largest input number for your C data type (int, long, long long, etc.)

4. Print an error message if the user tries to input too big of a number.

## Solution File

See the the solution file if need help.

Lab 4 Solution