C++ funckja programowanie

Question

Cześć, nie wiem gdzie mam błąd z funkcją rekurencyjną.

Wzór:
a0=0

a1=1

A(2n)=a(2n-1)+a(2n-2)

A(2n+1)=a(2n)-a(2n-1)

EDIT: Funkcja zwraca wartość n-tego wyrazu ciągu

 

#include <iostream>

using namespace std;

int fun(int n)
{
    if ( n == 0 ) return 0;
    if ( n == 1 ) return 1;
    if(n%2==0) return  fun(2*n-1)+fun(2*n-2);
    if(n%2!=0) return  fun(2*n)-fun(2*n-1);

}

int main(){

    cout<<fun(5);
    return 0;
}

 

Answer 1

Wg mnie w Twoim kodzie do zmiany są dwa ostatnie warunki tzn. są to wzory na to jak zachować się dla liczby parzystej większej od zera oraz liczby nieparzystej większej od 1, bo w przeciwnym wypadku nie mają sensu...

a0 = 0	Jeśli przekazujemy 0 (a0) to zwracamy 0
a1 = 1	Jeśli przekazujemy 1 (a1) to zwracamy 1
a2n = a2n-1+ a2n-2	Dla parzystej (2n) zwracamy ciąg dla parzystej (2n) pomniejszonej o 1 + ciąg dla parzystej  (2n) pomniejszonej o 2
a2n+1 = a2n - a2n-1	Dla nieparzystej (2n+1) zwracamy ciąg dla nieparzystej (2n+1) pomniejszonej o 1 - ciąg nieparzystej (2n+1) pomniejszonej o 2

W rezultacie:

#include <iostream>
using namespace std;

int ciag(int n) {
    if ( n == 0 ) return 0;
    if ( n == 1 ) return 1;
    if (n % 2 == 0) return ciag(n - 1) + ciag(n - 2);
    if (n % 2 != 0) return ciag(n-1) - ciag(n - 2);
}

int main() {
    for(int i = 0; i < 20; i++)
        cout << i << "-ty wyraz: " << ciag(i) << endl;
    return 0;
}

Tym samym na wyjściu:

0-y wyraz: 0
1-y wyraz: 1
2-y wyraz: 1
3-y wyraz: 0
4-y wyraz: 1
5-y wyraz: 1
6-y wyraz: 2
7-y wyraz: 1
8-y wyraz: 3
9-y wyraz: 2
10-y wyraz: 5
11-y wyraz: 3
12-y wyraz: 8
13-y wyraz: 5
14-y wyraz: 13
15-y wyraz: 8
16-y wyraz: 21
17-y wyraz: 13
18-y wyraz: 34
19-y wyraz: 21