Technologia Informacyjna Temat 7: Rekurencja
Rekurencja polega na odwołaniu się do samego siebie, czyli (w przypadku programowania) wywołaniu funkcji lub procedury w swoim własnym wnętrzu.
Zastosowanie rekurencji pozwala w prosty i przejrzysty sposób przedstawić algorytm, ale przeważnie wiąże się ze zwiększonym zapotrzebowaniem na pamięć i wolniejszym wykonaniem.
Przykład rekurencji:
Function Silnia(n)
If n > 1 Then
Silnia = n * Silnia(n-1)
Else
Silnia = 1
End If
End Function
Przykład ten co poprzednio, ale napisany metodą tradycyjną:
Function Silnia(n)
Dim Wynik
Wynik = 1
For i=1 To n
Wynik = Wynik * i
Next i
Silnia = Wynik
End Function
Obliczmy złożoność obu algorytmów zarówno w aspekcie czasowym jak i pamięciowym.
Algorytm rekurencyjny:
Function Silnia(n)
If n > 1 Then
Silnia = n * Silnia(n-1)
Else
Silnia = 1
End If
End Function
Przy każdym wywołaniu
Algorytm rekurencyjny:
funkcji potrzeba jednej
komórki pamięci dla n
Function Silnia(n)
i jednej dla wyniku –
razem dwie komórki.
If n > 1 Then
Silnia = n * Silnia(n-1)
Else
Silnia = 1
End If
End Function
Przy każdym wywołaniu
Algorytm rekurencyjny:
funkcji potrzeba jednej
komórki pamięci dla n
Function Silnia(n)
i jednej dla wyniku –
razem dwie komórki.
If n > 1 Then
Silnia = n * Silnia(n-1)
Else
Przy każdym wywołaniu
Silnia = 1
funkcji dokonywane jest
End If
jedno porównanie, jedno
mnożenie, jedno
End Function
odejmowanie, jedno
przypisanie – razem
cztery operacje.
Jako że złożoność algorytmu jest zależna od rozmiaru wartości wejściowej n, więc złożoność trzeba wyrazić w funkcji właśnie tej wartości:
Złożoność pamięciowa:
Złożoność czasowa:
Jako że złożoność algorytmu jest zależna od rozmiaru wartości wejściowej n, więc złożoność trzeba wyrazić w funkcji właśnie tej wartości:
Złożoność pamięciowa:
2*n
Złożoność czasowa:
4*(n-1)+2
Algorytm z pętlą For:
Przy każdym wywołaniu
funkcji potrzeba jednej
komórki pamięci dla n,
Function Silnia(n)
jednej dla zmiennej
indeksowej, jednej dla
Dim Wynik
wyniku pośredniego
Wynik = 1
i jednej dla wyniku
For i=1 To n
końcowego – razem
cztery komórki.
Wynik = Wynik * i
Next i
Silnia = Wynik
End Function
Algorytm z pętlą For:
Przy każdym wywołaniu
funkcji potrzeba jednej
komórki pamięci dla n,
Function Silnia(n)
jednej dla zmiennej
indeksowej, jednej dla
Dim Wynik
wyniku pośredniego
Wynik = 1
i jednej dla wyniku
For i=1 To n
końcowego – razem
cztery komórki.
Wynik = Wynik * i
Next i
W każdym przebiegu pętli
Silnia = Wynik
mamy: przypisanie,
mnożenie i inkrementację,
End Function
oraz trzy przypisania poza
pętlą
Jako że złożoność algorytmu jest zależna od rozmiaru wartości wejściowej n, więc złożoność trzeba wyrazić w funkcji właśnie tej wartości:
Złożoność pamięciowa:
Złożoność czasowa:
Jako że złożoność algorytmu jest zależna od rozmiaru wartości wejściowej n, więc złożoność trzeba wyrazić w funkcji właśnie tej wartości:
Złożoność pamięciowa:
4
Złożoność czasowa:
3*n+3