Algorytm zapisany w sposób rekurencyjny

W kolejnych krokach zaprezentujemy algorytm obliczania schematu Hornera zapisany metodą rekurencyjnąrekurencjametodą rekurencyjną.

Definicja rekurencyjna tego algorytmu:

• aIndeks dolny 00 = wspolczynniki[0]

• aIndeks dolny nn = x * aIndeks dolny n‑1n‑1 + wspolczynniki[n] dla n>0

Krok 1

Wczytaj dane w taki sposób, jak w algorytmie iteracyjnym.

Krok 2

Wywołaj funkcję Horner(), podając jako argumenty: wspolczynniki, stopienWielomianu, x.

funkcja Horner(wspolczynniki[], stopienWielomianu, x)

Krok 3

W funkcji Horner() sprawdź, czy stopienWielomianu jest równy zero.

funkcja Horner(wspolczynniki[], stopienWielomianu, x)
	jeżeli stopienWielomianu == 0 wykonaj:

Krok 4

Jeśli tak jest, zwróć wspolczynniki[0]. Jest to przypadek bazowyprzypadek bazowy w rekurencjiprzypadek bazowy w naszej funkcji rekurencyjnej.

funkcja Horner(wspolczynniki[], stopienWielomianu, x)
	jeżeli stopienWielomianu == 0:
    	zwróć wspolczynniki[0]

Krok 5

Jeśli tak nie jest, zwróć:

x * Horner(wspolczynniki,stopienWielomianu-1,x) + wspolczynniki[stopienWielomianu]

Oto gotowa funkcja:

wypisz "Podaj stopień wczytywanego wielomianu: "
stopienWielomianu = wprowadź liczbę całkowitą
dla i = 0,1,2... stopienWielomianu wykonuj:
	wypisz "Podaj "
    wypisz i
    wypisz " współczynnik"
    wspolczynniki[i] = wczytaj liczbę
Wyswietl "Podaj argument, dla którego chcesz obliczyć wartość wielomianu:"
x = wczytaj liczbę
wynik = Horner(wspolczynniki, stopienWielomianu, x)
wypisz "Wynik = "
wypisz x

funkcja Horner(wspolczynniki[], stopienWielomianu, x)
	jeżeli stopienWielomianu == 0 wykonaj
    	zwróć wspolczynniki[0]
    w przeciwnym razie wykonaj:
    	zwróć x * Horner(wspolczynniki,stopienWielomianu ‑ 1,x) + wspolczynniki[stopienWielomianu]

Przykładowe wykonanie algorytmu rekurencyjnego

Oblicz wartość wielomianu, wykorzystując schemat Hornera:

dla argumentu x = 4.

Dane po wczytaniu:

stopienWielomianu = 4 
x = 4 
wspolczynniki = {1, 2, 0, 1, -15}

Współczynnik zapisany pod indeksem 2 ma wartość zero, ponieważ w naszym wielomianie nie ma zapisanego xIndeks górny 2².

Krok 1

Wywołaj funkcję Horner(wspolczynniki, stopienWielomianu, x).

Krok 2

Sprawdź, czy stopienWielomianu jest równy 0.

Krok 3

W tym przypadku tak nie jest, zwróć:

x * Horner(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu]

Krok 4

Sprawdź, czy stopienWielomianu jest równy 0.

Krok 5

W tym przypadku tak nie jest, ponieważ stopienWielomianu = 3. Zwróć:

x * Horner(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu]

Krok 6

Sprawdź, czy stopienWielomianu jest równy 0.

Krok 7

W tym przypadku tak nie jest, ponieważ stopienWielomianu = 2. Zwróć:

x * Horner(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu]

Krok 8

Sprawdź, czy stopienWielomianu jest równy 0.

Krok 9

W tym przypadku tak nie jest, ponieważ stopienWielomianu = 1. Zwróć:

x * Horner(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu]

Krok 10

Sprawdź, czy stopienWielomianu jest równy 0.

Krok 11

W tym przypadku tak jest. Zwróć wspolczynniki[0] równe 1.

Krok 12

Powróć do kroku 9.

x = 4

Funkcja Horner(wspolczynniki,stopienWielomianu - 1,x) zwróciła wartość wspolczynniki[0], co jest równe 1. Natomiast wspolczynniki[stopienWielomianu] jest równe 2.

Zatem:

Krok 13

Powróć do kroku 7.

x = 4

Funkcja Horner(wspolczynniki,stopienWielomianu - 1,x) zwróciła wartość obliczoną w kroku 12., co jest równe 6. Natomiast wspolczynniki[stopienWielomianu] jest równe 0.

Zatem:

Krok 14

Powróć do kroku 5.

x = 4

Funkcja Horner(wspolczynniki, stopienWielomianu - 1, x) zwróciła wartość obliczoną w kroku 13., co jest równe 24. Natomiast wspolczynniki[stopienWielomianu] jest równe 1.

Zatem:

Krok 15

Powróć do kroku 3.

x = 4

Funkcja Horner(wspolczynniki,stopienWielomianu - 1,x) zwróciła wartość obliczoną w kroku 13., co jest równe 97. Natomiast wspolczynniki[stopienWielomianu] jest równe -15.