10.3: Using Array as Input of a Recursive Function

Example

Write a recursive function that receives an array of integers and returns the largest number in the array the function receives.

Step 1: Write the header of this function:

Step 2: Code the function with the base case: when length=1.

If the length=1, that means the array the function receives has only one element which is aArray[0] and the number in this element is the largest number, so function should return it.

Step 3: Recursion

If the array the function receives has more than one elements, then the function will keep the last one by using the statement in line 9: int a =aArray[length-1]; and pass the rest of the numbers in the array to the next function (like pass the rest of boxes to the next sibling). Since all the functions will do exact the same thing:

• keep the last number in the array it receives and pass the rest of the numbers in the array to the next function
• receives the solution from the next function and compare with the number it keeps and return the largest

Therefore, all the functions will poses the same code, they are the same function: getLargest(). The statement in line 10: "int b = getLargest(aArray, length-1);" passes the rest of the numbers in the array to the function getLargest()

The statement in Line 10 also receives the return value from the next function call and put it into the variable b

Line 11 - Line 14: compare the return value received from the next function call with the number the function kept and return the larger value which is the largest number in the array.

How many function calls does this process made? It depends on the number of elements in the array. For example, if the original array has 5 numbers, then find the largest number in the array will use five function calls or use the same function five times (just like finding the box that has the most candies among five candy boxes needs five siblings). Beginning from the second function, each function call will receive one less items from the array and keep one of them and pass the rest of the items to the next function and wait for result that comes back from the next function call. After receive the result, compare and then returns the larger one.

The return value of first function is the solution of the original problem.

We can test run this function with following program:

Let's try to use this recursive technique to solve another problem.

Example

Write a recursive function that receives an array of integers and returns the sum of the numbers in the array the function receives.

Step 1: Step 1: Write the header of this function:

Step 2: Code the function with the base case: when length=1.

If the length=1, that means the array the function receives has only one element which is aArray[0] and the number in this element is the sum of the array, so function should return it.

Step 3: Recursion

If the array the function receives has more than one elements, then the function will keep the last one by using the statement in line 9: int a =aArray[length-1]; and pass the rest of the numbers in the array to the next function. Since all the functions will do exact the same thing:

• keep the last number in the array it receives and pass the rest of the numbers in the array to the next function
• receives the solution from the next function which is the sum of the rest of the numbers in the array it passed to the next function and return the sum of the number it kept and the number it received from the next function

Therefore, all the functions will poses the same code, they are the same function: getSum(). The statement in line 10: "int b = getSum(aArray, length-1);" passes the rest of the numbers in the array to the function getSum()

The statement in line 10 also receives the solution from the next function and put it into the variable b

Line 11: returns the sum of the number the function kept and the number the received from line 9 which is the sum of the rest of the numbers it passed to the next function.

How many functions does this process use? It depends on the number of elements in the array. For example, if the original array has 5 numbers, then find the sum of the numbers in the array will use five functions or use the same function five times (just like finding the box that has the most candies among five candy boxes needs five siblings, this time, instead of finding the box that has the most candies, we find the total number of candies in all five boxes). Beginning from the second function, each function will receive one less items from the array and keep one of them and pass the rest of the items to the next function and wait for result that comes back from the next function. After receive the result, add the number the function kept and return the sum

The return value of first function is the solution of the original problem.

We can test run this function with following program:

Example

Write a recursive function that receives a positive integer n and returns the sum of all the integers from 1 to n. For example, if the function receives an integer 5, then the function will return 15

If we use above "recursive thinking", the recursive function can be easily coded. When the function receives an integer n, we can consider the function receives a sequence of integers from 1, 2, 3, ..., n. The function will keep the last number in the sequence and pass the rest of numbers to the next function. The wait for the next function to return the solution, which is going be the sum of the numbers from 1 to n-1. Then the function add the it kept, which is n, and return the sum which will be sum of all the numbers in the sequence. Of course, the next won't actually do the entire calculation, it will also kept the last number in the sequence and pass the rest of numbers in the sequence to its next function. The only function that won't pass the sequence is the last function because the sequence the this function receives has only one number. This function simply return it.

If the number the function receives is 1, then the sum of the integer from 1 to 1 is 1. Thus the function returns 1

If the n is greater than 1, then the function keeps the last number which is n and put it in the variable a in line 9 and passes the rest of the numbers to the next function in line 10. Once the function get the result from the next function, put it in the variable b.

The function return the sum of the number it kept and the result from the next function in line 11.

---