Podaj algorytm rekurencyjny.

[h0bbit]

Podaj rekurencyjny algorytm wyznaczający:

(a) \(\displaystyle{ k^{n}}\), gdzie \(\displaystyle{ k}\) i \(\displaystyle{ n}\) są pewnymi dodatnimi liczbami naturalnymi,
(b) sumę elementów ciągu \(\displaystyle{ n}\) liczb naturalnych, zapisanego w tablicy \(\displaystyle{ A[1..n]}\).

Narysuj drzewo wywołań rekurencyjnych rozważanego algorytmu. Wytypuj operację dominujacą
w owym algorytmie i przedstaw równanie rekurencyjne opisujące liczbę jej wykonań. Zaproponuj
rozwiązanie równania.

[adek05]

a) Policz\(\displaystyle{ k^{n-1}}\) i pomnóż przez k.
b) \(\displaystyle{ A[1...n] = A[1...n-1] + A[n]}\)

[matshadow]

1. Algorytm szybkiego potęgowania

[Dedemonn]

a) Policz\(\displaystyle{ k^{n-1}}\) i pomnóż przez k.

Brak końca rekurencji.

[adek05]

Dedemonn, przedstawiłem tylko ideę, a nie pełne równanie rekurencyjne, które opisuje algorytm.
W pełni będzie tak:
\(\displaystyle{ \begin{cases}k^{n} = k^{n-1} * k \quad n>1\\k^{n} = k \quad n= 1\end{cases}}\)