4

我在一本 C++ 书中找到了一个练习，上面写着“编写一个函数来计算一个数字在数组中出现的次数。”。一切都很好，程序正在运行。但练习也表明该函数应该是递归的。

如何使递归函数像这样工作？

#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;
}
4

7 回答 7

5

使用这个count功能：

int count(int number, int array[], int length) {
    if (length == 0) return 0;
    return (number == *array) + count(number, array+1, length-1);
}
于 2013-08-31T07:26:39.683 回答
3

代替您现在拥有的循环和计数器， return 0 + recursive_stepor 1 + recursive_step， whererecursive_step是对count(...)您增加数组指针和减少的地方的调用length。您的基本情况是何时length == 0，此时您才返回0。

理解递归的一个好方法是逐步研究计算是如何进行的。在您的示例中，您将执行以下操作：

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)

做return count(..., acc+1)or return count(..., acc+0)。一些编译器然后能够进行尾调用优化，将其转换为编译代码中的循环。与常规递归相比，这可以节省内存。

于 2013-08-31T07:24:40.140 回答
2

像这样尝试怎么样： -

int count(int num, int* arr, int length) {
    if (!length)
        return 0;
    int c = count(num, arr+1, length-1);
    return arr[0] == num? c + 1: c;
}

int main(void) {
int arr[10] = {3,4,1,2,4,5,6,5,4,5};

std::cout << count(2, arr, 10);

return 0;
}
于 2013-08-31T07:24:33.567 回答
1

这就是你要做的（我不会向你展示任何代码以避免破坏你的练习）。

首先，请记住，为了递归，您的函数需要调用自身。接下来，考虑这两点：

  • 当length参数为零时，返回值count(...)必须为零
  • 当length参数不为零时，考虑count(...)forarray + 1和的返回值length-1；让我们称之为prior。当前的返回值count(...)将等于prior+1if array[0]is equal tonumber或 to priorwhen array[0]is not equal to number。

当您根据此描述编写代码时，请注意您if在递归函数的开头是如何使用的。这if会将您的代码拆分为基本案例 ( length == 0) 和递归步骤（根据递归调用计算结果）。这是递归函数的常见结构：每次编写递归代码时都必须重现此结构。

于 2013-08-31T07:27:34.720 回答
1 
#include <iostream>

void count(int number, int array[], int length, int &occurence)
{
    if (*array == number) ++occurence;  

    if (length == 1)
        return;
    else    
        count(number, array+1, length-1, occurence);
}

int main()
{
    int numbers[10] = {3,4,1,2,4,5,6,5,4,5};
    int number_to_search = 5;
    int occurence = 0;
    count(number_to_search, numbers, 10,occurence);
    std::cout << number_to_search << " appears "
              << occurence
              << " times in the array.";
}
于 2013-08-31T08:15:59.543 回答
0 
 #include <iostream>
 #include <ctime>
 #include <cstdlib>
 using namespace std;
 int i, j,n,c=0, k=0;
 int a[1000], b[1000];
 class Array {


    public:
        void input ()
        {
            cout<<"Enter how many values: ";
            cin>>n;
        }

        void arraySeries ()
        {
            cout<<"Array elements: ";
            srand(time(0));
            for (i=0; i<n; i++)
            {
                a[i]=rand()%100+1;
                cout<<a[i]<<" ";

            }
            cout<<endl<<endl;
            cout<<"Odd elements of array: ";
            for (i=0; i<n; i++)
            {   
                if(a[i]%2==1)
                {
                    b[i]=a[i];
                    k++;
                    cout<<b[i]<<" ";
                }

            }
        }
        // i want to find out how many times an odd number is found in b[i]
        // but i am not being able to do so. SOMEONE PLEASE HELP!!
        void OddSearch ()
        {
            cout<<endl<<endl;
            for (int k=1;k<100;k++)
            {
                c=0;
                for (i=0;i<n; i++)
                {

                    if (b[i]==k)
                    {
                        c++;
                    }
                    cout<<b[i]<<"occurs"<<c<<"times"<<endl;
                }
            }
        }
 };

 int main ()
 {
    Array obj;
    obj.input();
    obj.arraySeries();
    obj.OddSearch();

    return 0;
 }
于 2016-03-16T16:47:30.740 回答
0 
#include <stdio.h>

int count(int number,int array[],int size){
   int counter=0;
   if(size == 0) return 0;
   if(array[0] == number){
      counter++;
      return counter+count(number,array+1,size-1);
   }    
   return count(number,array+1,size-1);    
 }

int main() {
 
  int array[] = {1,2,2,4,4,8,7,3,4};
  int size = sizeof(array)/sizeof(int);

  printf("%d",count(2,array,size));

  return 0;    
}
于 2021-06-17T08:00:23.720 回答