[Algorytmy] Wartość rekurencji dla argumentu

[Teano]

Rozważmy następujący algorytm rekurencyjny:

Kod: Zaznacz cały

ZROB-TO-SAM(n)
if n < 1
then return 0
else return ZROB-TO-SAM(n-2)*(n+1)

Jaką wartość zwróci instrukcja ZROB-TO-SAM(12)? Odpowiedź uzasadnić.

Uwaga: wszystkie zmienne są liczbami całkowitymi.

Bardzo proszę o pomoc

[bartek118]

No to zapiszmy dosłownie tę rekurencję:
\(\displaystyle{ f(n) = 0}\) dla \(\displaystyle{ n < 1}\) oraz \(\displaystyle{ f(n)=(n+1)f(n-2)}\).
No i teraz - jeśli \(\displaystyle{ n}\) jest parzyste, to schodząc ciągle o \(\displaystyle{ 2}\) dotrzemy do takiego momentu:
\(\displaystyle{ f(n) = \mbox{coś} \cdot f(2) =3 \mbox{coś} \cdot f(0) = 0}\).
Jeśli \(\displaystyle{ n}\) jest nieparzyste, to
\(\displaystyle{ f(n) = \mbox{coś} \cdot f(1) = 2 \mbox{coś} \cdot f(-1) = 0}\).

Ostatecznie \(\displaystyle{ f(n) = 0}\) dla wszystkich \(\displaystyle{ n \n \mathbb{Z}}\).