For this assignment you will write two recursive functions, one to calculate a factorial, and another to find the maximum value in an array.
Note that in C it is generally more efficient to perform calculations using loops instead of using recursion. We are using recursion here to practice recursive problem solving, not to implement practical efficient solutions.
This project already contains two recursive functions, one to calculate the nth triangle number and another to calculate the sum of the values in an array. These functions are implemented in recursive_functions.c, their prototypes are in recursive_functions.h, and there is code in main.c to test them. A provided Makefile produces the executable recursion when running make.
Try building the project and running recursion to see the existing behavior. The triangle_number() function is tested with the numbers 0 through 10 and an array of size 5 is filled with random values to test array_sum(). When you implement the two additional functions, there are lines to uncomment to test them as well.
factorial()There is already a prototype for this function in recursive_functions.h:
unsigned int factorial(unsigned int n);Implement this function in recursive_functions.c, and uncomment the line in main.c that tests it so you can try it out.
The factorial of a positive integer \(n\), or \(n!\), is the product of the integers 1 through \(n\). For example:
\(4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24\)
Since \(0!\) is defined to have the value 1, we can define a factorial recursively like so:
\[n! = \begin{cases} 1 & \text{if } n = 0 \\ n \cdot (n - 1)! & \text{otherwise} \end{cases}\]
Note that this is very similar to the recursive definition of the nth triangle number \(T_n\):
\[T_n = \begin{cases} 0 & \text{if } n = 0 \\ n + T_{n-1} & \text{otherwise} \end{cases}\]
Thus the implementation of factorial() is going to be very similar to the implementation of triangle_number().
array_max()There is already a prototype for this function in recursive_functions.h:
int array_max(int *array, size_t size);Implement this function in recursive_functions.c, and uncomment the line in main.c that tests it so you can try it out.
The recursive strategy for array_max() is similar to that of array_sum(). In array_sum() we illustrate that the sum of the values in an array with more than one element can be calculated by adding one of the values to the sum of the rest of the values. The most straightforward way to do this recursively with a C array is to add the last value in the array to the sum of the rest of the values in the array:
return array[size - 1] + array_sum(array, size - 1);array[size - 1] is the last element in the array, and by passing size - 1 as the array’s size in the recursive call, the recursive call will only consider the first size - 1 values when computing the smaller sum.
You can use a similar strategy in the recursive array_max(). If there is only one value in the array, then the max is that value (this is the base case). Otherwise, compare the last value in the array to the max of the rest of the array (recursively), and return the larger value. Since you may need to use the result of the recursive call twice (once in the comparison and perhaps once in a return statement) it is a good idea to store the result of the recursive call to array_max() in a variable to avoid calling the function recursively twice.
Push your submission to git-keeper. For full credit the tests must pass and you must not use any loops in recursive_functions.c.