Metody Programowania - Lista 2

Zadanie 1

Program fibo2.c ilustruje mechaniczne eliminowanie rekursji przy pomocy stosu.

zmodyfikować program fibo2.c tak by podawał zużycie stosu, tzn. jaka była maksymalna wartość wskaźnika stosu
uprościć program fibo2.c usuwając zbędne operacje na stosie, ograniczyć też zużycie stosu

Zadanie 2

Wzorując się na programie fibo2.c przekształcić następujące rekursywne procedury na iteracyjne (ze stosem):

naiwną silnię

silnię z akumulatorem:

int 
asilnia(int n, a)
{
    if (n < 2) {
        return a;
    } else {
        return asilnia(n - 1, n*a);
}

int 
silnia(int n)
{
    return asilnia(n, 1);
}

rekursywną funkcję obliczającą współczynnik dwumianowy
rekursywne rozwiązanie zadania o ośmiu hetmanach (w tym zadaniu trzeba znaleźć wszystkie ustwienia hetmanów na szachownicy 8x8 takie że żadne dwa hetmany wzajenie się nie szachują).

Zadanie 3

Napisać naiwną rekursywną wersję procedury obliczania długości listy. Mechanicznie wyeliminać z nie rekursję (wprowadzając stos). Potem zmienić rekursywną definicję tak by mechaniczna eliminacja rekursji dała wersję iteracyjną nie używającą stosu.

Zadanie 4

Mając daną funkcję rekursywną chcemy wypisać jej drzewo wywołań. Np dla funkcji obliczającej liczby Fibonacciego:

fib(5) = 8
    fib(4) = 5
        fib(3) = 3
            fib(2) = 2
                fib(1) = 1
                fib(0) = 1
            fib(1) = 1
        fib(2) = 2
            fib(1) = 1
            fib(0) = 1
    fib(3) = 3
        fib(2) = 2
            fib(1) = 1
            fib(0) = 1
        fib(1) = 1

Tzn. każde wywołanie ma być w odzielnej linii, podając argumenty i wynik. Poniżej mają być wywołania rekursywne, z wcięciami pokazującymi poziom rekursji: wszystkie wywołania są wciętę o cztery spacje w stosunku do funkcji wywołującej. Jak przekształcić daną funkcję, tak by wypisać to drzewo. Przy tym chcemy mało zmienić funkcję, ale też chcemy uniknąć wielokrotnego wywoływania danej funkcji.

Wskazówka: zapamiętać argumenty i wyniki na stosie, samo drzewo wypisać w oddzielnej pętli.