数字在数组中出现的次数 [英] Number of times number appears in an array
问题描述
我在C ++书中找到一个练习:写一个函数来计算一个数字在数组中出现的次数。一切都很好,程序是工作。但是该练习还表示函数应该是递归的。
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;
}
推荐答案
你现在,返回 0 + recursive_step
或 1 + recursive_step
,其中 recursive_step
是对 count(...)
的调用,其中增加了数组指针并减少了 length
。 length == 0
,此时您只需返回 0
。
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
如果您允许更改函数说明,你也可以做一些酷的称为尾递归。而不是 return 1 + count(...)
,添加累积的数量,直到计数器计数: int count(int number,int array [],int length,int acc)
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)
)或 return count(...,acc + 0)
。一些编译器然后能够进行尾调用优化,将其转换为编译代码中的循环。与常规递归相比,这可以节省内存。
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.
这篇关于数字在数组中出现的次数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!