Schemat Hornera – wersja rekurencyjna

Zapiszmy, krok po kroku, algorytm schematu Hornera w wersji rekurencyjnejrekurencjarekurencyjnej.

Krok 1.

Zapiszmy nagłówek naszej funkcji:

int hornerRekurencyjnie(int wspolczynniki[],int stopienWielomianu, int x)

Składa się on z następujących elementów:

• typu zwracanych wartości przez funkcję – w tym przypadku może to być zarówno int, float, jak i double,

• nazwy funkcji hornerRekurencyjnie,

• argumentów funkcji zapisanych w okrągłych nawiasach.

Pierwszym z argumentów jest tablica wspolczynniki zawierająca wszystkie współczynniki znajdujące się przy kolejnych potęgach naszego wielomianu. Kolejnym argumentem jest stopienWielomianu. Jest to zmienna, w której przechowywana jest największa potęga naszego wielomianu. Ostatnim argumentem jest zmienna x. Jest to argument, dla którego będziemy obliczali wartość wielomianu.

Krok 2.

Kolejnym krokiem jest ustalenie warunku przerwania rekurencji. Tym warunkiem będzie to, czy zmienna stopienWielomianu jest równa 0.

if(stopienWielomianu == 0)

Krok 3.

Jeśli warunek zapisany w kroku 2 jest spełniony, zwracamy współczynnik z indeksem zero – jest to wyraz wolny naszego wielomianu.

return wspolczynniki[0];

Krok 4.

Jeśli nasz warunek nie jest spełniony, zwracamy argument, dla którego obliczamy wartość wielomianu pomnożoną przez wartość, jaką zwróci nam wywołana rekurencyjnie funkcja hornerRekurencyjnie() z argumentami wspolczynniki, stopienWielomianu - 1, x oraz dodanym współczynnikiem zapisanym pod indeksem stopienWielomianu.

return x * hornerRekurencyjnie(wspolczynniki,stopienWielomianu ‑ 1,x) + wspolczynniki[stopienWielomianu];

Algorytm obliczający wartość wielomianu zapisany w wersji rekurencyjnej zaimplementowany w języku C++ wygląda następująco:

int hornerRekurencyjnie(int wspolczynniki[],int stopienWielomianu, int x)
{

    if(stopienWielomianu == 0)
    	return wspolczynniki[0];
    else
        return x * hornerRekurencyjnie(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu];
}

Sprawdźmy jego działanie dla przykładowych danych. Przetestujemy działanie programu dla następującego wielomianu:

$W\left(x\right) = x^2 + 3x - 6$

oraz $x = 2$.

#include<iostream>
using namespace std;

int hornerRekurencyjnie(int wspolczynniki[],int stopienWielomianu, int x)
{

    if(stopienWielomianu == 0)
    	return wspolczynniki[0];
    else
        return x * hornerRekurencyjnie(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu];
}

int main()
{
    int wspolczynniki[] = {1, 3, -6};
    int stopienWielomianu = 2;
    int x = 2;
    cout << hornerRekurencyjnie(wspolczynniki, stopienWielomianu, x);
    
    return 0;
}

Program na wyjściu daje liczbę 4, co jest poprawnym wynikiem.