Lab 11

Tomorrow's lab will be about recursion. Part of the question would be selected from coding bat. You could click and think about the problems, and even practice directly in the online judge. Practice makes perfect, hopefully you could be well prepared for tomorrow's lab. Other details will be posted here at midnight. 

Please download the sample code and start working on them following the instructions. 

Solution has been uploaded. 

 Topic: Recursion

 There are 3 simple recursion problems for you to solve during the lab. Theoretically, any recursion problem

 could be converted into iterative fashion. Although some of these problem could be easily implement iteratively,

 to train yourself with the sense of recursion, you need to write the recursion version to get points in this lab.

 Each problem worth one point, you are free to decide which one you want to do first, though they are put in the 

 increasing order of difficulty (it is subjective). 

 1. Reverse array

 Design a function with exactly the signature and return type as below:

 // numbers[] : the array you need to reverse

 // leftIndex and rightIndex : the indexes of the element you want to swap

 void reverseArray (int numbers[], int leftIndex, int rightIndex)

 Example:

 Input: int array -->  1, 2, 3

 Output: int array --> 3, 2, 1

 2. Count how many times a key value is found in an array of numbers.

 Design a function with exactly the signature and return type as below:

 // numbers : the array you want to tranverse to count key

 // size : the range of the array you want to count. Given size, you want to traverse from 0 - (size-1) to count number of key

 // &count : count is pass by reference, so that you could modify count, do not need to return in the function. (You do not have to do in this way,

     of course you could return the count, but we make in this way on purpose, so that you could practice pass by reference)

 void count(int numbers[], int size, int key, int &count)

 3. Fibonacci number

 Fibonacci number wiki : https://en.wikipedia.org/wiki/Fibonacci_number

 Design a function with exactly the signature and return type as below:

 // index : the index of Fibonacci number sequence

 int fib(int index)

 Start from index 0, Fibonacci number are: 1, 1, 2, 3, 5, 8 ...

 So fib(0) = 1, fib(1) = 1, fib(2) = 2, fib(3) = 3, fib(4) = 5 ...

 And it has property that fib(n) = fib(n - 1) + fib(n - 2)

 Think about how do you design base case and general case.