Do your work in your Odin 2020/9/ folder.

Write a recursive Fibonacci function.
Write a recursive binary search function.

We will do these in zoom class together.

Name your program: fibfind.cpp

Use your recursive Fibonacci function to fill an array with fibonacci numbers.

Prompt the user to guess at a fibonacci number.

Use a recursive binary search function to search for the number.

Indicate if it was found or not.
Display how many comparisons were necessary to find the answer.

Requirements:

  1. Dynamically allocate an array with a size of at least 100.

  2. Number of Fibonacci numbers stored should be over 40.
     This means n should be greater than 40.
     n should not go above 45.

  3. Start at the 2nd Fibonacci number when populating your array.
     Do not add duplicate values to your array.

  4. Output of your program must be neat and clear for the user.
     The user should know what they are looking at.
     The user should know how to work the program because of your output.

Do this challenge please.

1. Write a program named pairs.cpp.

2. In your program, a pair of numbers is defined as two of the same values
   side-by-side in an array.

3. Your program will use a recursive function to count how many "pairs"
   an array has.

4. For example, the array { 1, 2, 3, 3, 4, 5, 6, 6, 7, 8 } has 2 pairs.
                                  ----        ----

5. A good model program to start might be binsearch.cpp,
   because it has an array and a function call already.

6. Your program can fill the array with random values, if you like.
   Keep the array small, and display it to the user.

Recommended:
   a. Fill the array with random 1-digit numbers.
   b. The prototype of your recursive function can be:
      int pairs(int *arr, int start, int end);


program output should look like this...

Lab-9 find pairs in an array.
                             
Array size? 20
Array is this: 7 8 4 7 5 1 1 1 1 1 3 0 8 4 7 7 3 8 1 0 

This array has 5 pairs.




Lab-9 find pairs in an array.
                             
Array size? 20
Array is this: 2 7 4 4 7 8 5 5 2 3 7 8 6 5 0 3 5 5 2 1 

This array has 3 pairs.




Lab-9 find pairs in an array.
                             
Array size? 12
Array is this: 8 1 3 6 5 0 6 0 2 4 7 0 

This array has 0 pairs.



Optional...
Indicate the pairs as shown below 

Lab-9 find pairs in an array.
                             
Array size? 22
Array is this: 4 4 2 5 4 5 1 8 1 5 6 0 7 6 6 1 1 7 8 6 6 4 
               ---                       --- ---     ---   
This array has 4 pairs.


this will earn extra points.


How to approach this program...

   1. Send the array with start and ending index to your recursive function.

   2. If the first value is the same as the second value,
         that is a pair!
         return 1 plus how ever may other pairs there are.
         
         Since the first array value cannot be part of another pair,
         start at the second character to look for more pairs.

         Your recursive call will return how many pairs in the
         rest of the array.

   3. If the first value is NOT the same as the second value,
         return 0 plus how ever may other pairs there are.
         similar to above.

   Note: underlining the pairs above was iteratively, not recursively.

Do this challenge please.

1. Write a program named halves.cpp.

2. Ask the user to enter a word.

3. Call a recursive function that receives the word as an argument.
   You may also send start and end as arguments.

4. The function will divide the word in-half to form 2 new words.

5. The function will send each half back through the recursive function
   to be divided again.

6. When a new word is just 1-character in length, display the character
   and return. Your recursive function may use cout for displaying output.

Recommended:
   a. Your recursive function prototype might look like this:
      void halves(char *str, int start, int end);


program output should look like this...

Lab-9 divide a word in half recursively.
                            
Enter a word: bakersfield
b a k e r s f i e l d 




Below is a detailed output of the function. It shows each word being
passed to the function is divided in-half, until it is just 1-character.
Then it is displayed.


Lab-9 divide a word in half recursively.
(detailed output)

Enter a word: bakersfield
"bakers"-"field"
"bak"-"ers"
"ba"-"k"
"b"-"a"
b a k "er"-"s"
"e"-"r"
e r s "fie"-"ld"
"fi"-"e"
"f"-"i"
f i e "l"-"d"
l d 


If you can attain the output above, it will show me you understand recursion
and a "divide and conquer" algorithm very well.


How to approach this program...

   1. send to your recursive function:
      a character array
      the starting index
      the ending index

   2. if the array has a length of 1-character, print it and return.

   3. if the array is longer than 1-character...

      find the middle index of the array
      send the first half of the array recursively to your fucntion
      send the second half of the array recursively to your fucntion

   Every divided part of the array will eventually shrink until it
   is just 1-character. All characters will eventually be printed.
   The function will end.