I found an exercise in a C++ book that says "Write a function that will count the number of times a number appears in an array.". Everything is fine, the program is working. But the exercise also says that the function should be recursive.
How can I make a recursive function working like this?
#include <iostream>
int count(int number, int array[], int length)
{
int counter = 0;
for(int i = 0; i < length; i++)
if(array[i] == number)
counter++;
return counter;
}
int main()
{
int numbers[10] = {3,4,1,2,4,5,6,5,4,5};
int number_to_search = 5;
std::cout << number_to_search << " appears "
<< count(number_to_search, numbers, 10)
<< " times in the array.";
return 0;
}
Use this count
function:
int count(int number, int array[], int length) {
if (length == 0) return 0;
return (number == *array) + count(number, array+1, length-1);
}
Instead of the loop and counter you have now, return 0 + recursive_step
or 1 + recursive_step
, where recursive_step
is a call to count(...)
where you have increased the array pointer and decreased length
. Your base case is when length == 0
, at which point you just return 0
.
A nice way of understanding recursion is to study how the calculation is carried out, step by step. In your example you will do something like this:
count(5, {3,4,1,2,4,5,6,5,4,5})
0+count(5, {4,1,2,4,5,6,5,4,5})
0+0+count(5, {1,2,4,5,6,5,4,5})
0+0+0+count(5, {2,4,5,6,5,4,5})
0+0+0+0+count(5, {4,5,6,5,4,5})
0+0+0+0+0+count(5, {5,6,5,4,5})
0+0+0+0+0+1+count(5, {6,5,4,5})
0+0+0+0+0+1+0+count(5, {5,4,5})
0+0+0+0+0+1+0+1+count(5, {4,5})
0+0+0+0+0+1+0+1+0+count(5, {5})
0+0+0+0+0+1+0+1+0+1+count(5,{})
0+0+0+0+0+1+0+1+0+1+0 <---The last 0 is the base case
3
If you are allowed to change the function specification, you can do also something cool called tail recursion. Instead of return 1 + count(...)
, add the accumulated number so far as a paremeter to count: int count(int number, int array[], int length, int acc)
And do return count(..., acc+1)
or return count(..., acc+0)
. Some compilers are then able to do tail call optimization , transforming it into a loop in the compiled code. This saves memory compared to a regular recursion.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With