Ćwiczenia 3: Rekurencja ogonowa

Rozwiązania poniższych zadań to proste procedury operujące na liczbach całkowitych.
Ich rozwiązanie wymaga zastosowania rekurencji ogonowej.
Dla każdej procedury rekurencyjnej podaj jej specyfikację, tj. warunek wstępny i końcowy,
oraz uzasadnij jej poprawność.
Poprawność procedur rekurencyjnych można pokazać przez indukcję.
Nie zapomnij o uzasadnieniu własności stopu.

1. Potęgowanie liczb całkowitych (z akumulatorem).
   
   Rozwiązania
2. [Bentley]
   Dana jest funkcja \(f: \{1, 2, \dots, n\} \to {\cal Z}\).
   Należy znaleźć takie \(1 \le a \le b \le n\), że suma \(\sum_{i=a}^b f(i)\) jest największa.
   Napisz taką procedurę p, że \(\mathtt{p}\ f\ n = b - a + 1\) (dla \(a\) i \(b\) jak wyżej).
   
   Rozwiązania
3. Napisz procedurę \(\mathtt{zera\_silni} : \mathtt{int} \to \mathtt{int}\), która dla danej dodatniej liczby całkowitej \(n\) obliczy ile zer znajduje się na końcu zapisu dziesiętnego liczby \(n!\).
   
   Rozwiązania
4. Dana jest funkcja nierosnąca \(f: \mathtt{int} \to \mathtt{int}\), taka, że \(f(x+1) \ge f(x) - 1\).
   Napisz procedurę, która znajduje punkt stały tej funkcji, tzn. taką liczbę \(x\), że \(f(x) = x\)
   (lub jeśli punkt stały nie istnieje, to taką liczbę \(x\), że \(f(x-1) \ge x\) oraz \(f(x) \le x\)).
   
   Rozwiązania
5. Dana jest różnowartościowa funkcja \(f: \mathtt{int} \to \mathtt{int}\).
   Napisz procedurę maksima, która dla danych liczb \(l\) i \(p\) (\(l \le p\)) obliczy ile lokalnych maksimów ma funkcja \(f\) w przedziale \([l, p]\).
6. Przypomnij sobie rozwiązania zadań z poprzednich ćwiczeń.
   Jeśli rozwiązałeś je nie stosując rekurencji ogonowej, to czy potrafisz je rozwiązać (lepiej) stosując ją?