Базовый случай рекурсивной функции для последовательности Фибоначчи - PullRequest
Новая
       9

Базовый случай рекурсивной функции для последовательности Фибоначчи

0 голосов
/ 23 апреля 2020

Я пытаюсь написать функцию void fib(int arr[], int n), которая бы заполняла массив числами Фибоначчи до индекса n.

Я пытался найти базовые случаи и выбрал их: 

void fib(int arr[], int num){

    int arrLength = num + 1;

    if(num<0){
        return;
    }else if(num == 0){
        arr[num] = 1;
    }else if(num == 1){
        arr[num-1] = 1;
        arr[num] = 1;
    }    
}

Но, как вы можете видеть, я не нашел сам рекурсивный метод.

Вот пример вывода, например, для вызова fib (arr, 5) : 

0 1 2 3 4 5
1 1 2 3 5 8

My main функция для тестирования: 

int main(){ 

    int n = 10, i;
    int arr[n+1];

    fib(arr, n);

    for(i=0;i<=10;i++){
        printf("%i ", arr[i]);
    }

    return 0;
}

Есть ли любой другой способ сделать базовые случаи более "изящными"? Кроме того, я был бы очень признателен за подсказки, с помощью которых я мог бы заполнить массив числами, начиная с 2, с рекурсивной опцией.

Ответы [ 2 ]

1 голос
/ 23 апреля 2020

Ваш вопрос требует рекурсии, но программа, которую вы пишете, просто использует функцию, по этой причине я пишу очень простой c код для вашего лучшего понимания, вы можете улучшить это после понимания потока и функциональности или задать новый вопрос с какой-то работой. Ниже приведен рабочий код, протестированный на Turbo C, я делюсь полным тестовым кодом. 

#include <stdio.h>
#include<conio.h>
#define MAX 100

void fib(int *arr, int num, int a, int b, int term){

    if(term == 0 && term <= num){
        arr[term] = 1;
        term++;
        fib(arr,num,a,b,term);
    }else if(term ==1 && term <= num){
        arr[term] = 1;
        term++;
        fib(arr,num,a,b,term);
    }else if(term <= num){
        arr[term] = a+b;
        term++;
        fib(arr,num,b,a+b,term);
    }
}

void main()
{
   int firstTerm = 1;//First term of fibbo series
   int secondTerm = 1;//Second term of fibbo series
   int tracker = 0; // Tracker to track how much term we printed
   int i;//To run loop here to check array after recursive function
   int ar[MAX],n=5;// n is number of term we want to print
   clrscr();
   fib(ar,n,firstTerm,secondTerm,tracker);//recursive function call

   // below is printing array to check 
   for(i=0;i<=n;i++){
    printf("%d\t",ar[i]);
   }
   getch();
}

Одна вещь, которую я должен предложить, - если n равно 5, то вы просто получаете 1 1 2 3 5 , В коде я сделал по вашему требованию, поэтому здесь будет напечатано 1 1 2 3 5 8

0 голосов
/ 24 апреля 2020

Я бы сказал, что «элегантное» решение должно быть простым l oop, без какой-либо рекурсии, но давайте посмотрим, как это можно сделать менее эффективным и более подверженным ошибкам способом. 

// I'll assume that the function signature can't be changed
void fib(int arr[], int num)
{
    // In the general case, use the well known recurrence relation.
    if ( num > 1 )
    {
        // Use recursion here to calculate the previous elements of the array.
        fib(arr, /* ... */);
        //       ^^^^^^^^^  Can you figure out what index should be passed here?

        // Then, calculate the element at index num using the recurrence relation.
        arr[num] = arr[num - 1] + arr[num - 2];
        //             ^^^^^^^        ^^^^^^^ Note the indices.
        //                                    Are those values alredy known?
    }
    // When num is 0 or 1, we can't use the general formula. Can you tell why?
    else if ( num >= 0 )
    {
        fib(arr, /* ... */);
        //       ^^^^^^^^^   Same as before.
        arr[num] = 1;
    }
    // If num is less than 0, it just do nothing.
}
...