Rekurencyjne znajdywanie wartosci najwiekszej w tablicy

Witam,

Chodzi mi o napisanie funkcji, ktora rekurencyjnie wyznacza najwieksza wartosc w tablicy i indeks jej towarzyszacy. Na razie mam cos takiego:

void find_max(int tab[], int n, int length) {

	if (n == length) {
		max = tab[n-1];
		key = n-1;
	}

	if (n == 0) {
		printf("Najwieksza liczba to %d, a jej indeks to %d.\n", max, key);
	}

	else {

		if (max<tab[n]) {
			max = tab[n];
			key = n;
		}

		find_max(tab-1, n-1, length);
	}

}

Ale... Po pierwsze nie zwraca dobrego indeksu (wartość zwracana jest dobra), a po drugie pobiera aż 3 parametry - na pewno da się to zrobić z dwoma. Pytanie - jak?

Szczerze mówiąc to do działania funkcji potrzebujesz 5 parametrow, ale 2 masz w zmiennych globalnych. Wychodzisz poza zakres tablicy, bo elsujesz tylko n==0 a n==length nie.

Edit:

musisz zmienic całkiem funkcję

int max=0,key=0;

void find_max(int tab[], int n) {       
        if (n>0)
        {
             find_max(tab,n-1);
        }
        if (max<tab[n-1]) {
               max = tab[n-1];
               key = n-1;
        }
}
 

No na 4 tez sie da. Jesli chcesz to robic bez zmiennych globalnych to takie cus sie zda.

void find_max(int *tab, int length, int max,int index)
{
    if(length==2)
    {
        cout << "Najwieksza liczba jest " << max << " o indeksie " << index;
    }
    else if(length>2)
    {
        if(max<tab[length-2])
        {
            index=length-2;
            max=tab[length-2];
            find_max(tab,length-1,max,index);
        }
        else if(max>=tab[length-2])
        {
            find_max(tab,length-1,max,index);
        }
    }
}

Musimy miec licznik do poruszania po tablicy, index i max ktore chcesz "zwrocic" no i sama tablice.

Ja bym to zrobił zupełnie inaczej. Żeby znać wartość i pozycję wystarczy Ci wskaźnik do największego elementu. Dodatkowo zgodnie z popularną konwencją taka funkcja może pobierać wskaźnik do początku tablicy i do końca (jednego elementu za ostatnim), np. int* maks_el(int start, int koniec).

Wtedy zwracasz start, jeżeli tablica jest jednoelementowa, null lub wskaźnik do końca gdy tablica jest pusta (tak na wszelki wypadek) oraz w ostatnim wypadku wskaźnik do większej wartości między pierwszym elementem tablicy a maksymalnym elementem reszty (czyli elementem wskazywanym przez maks_el(start+1,end)).

Bez zmiennych globalnych, bez ekstra parametrów, funkcja poprawna również dla tablic zerowej długości, bez chamskiego wyświetlania wyniku z wnętrza funkcji:

int find_max(int *tab, int length)
{
	length--;

	if (length > 0) {
		int max = find_max(tab, length);
		if (tab[max] > tab[length]) return max;
	}

	return length;
}

// (...)
int max = find_max(tab, length);
printf("Najwieksza liczba to %d, a jej indeks to %d.\n", tab[max], max);

@up:
Wada jest taka, że to nie jest rekurencja ogonowa i łatwo o przepełnienie stosu tutaj, bo kompilator nie zoptymalizuje ci tego do pętli. Ale to tylko dygresja :)

Update:
Wersja z rekurencją ogonową w Javie, chociaż HotSpot nie rozwija rekurencji ogonowej (a więc bez dodatkowego przetworzenia kodu/ bajtkodu nie ma sensu używanie rekurencji ogonowej pod HotSpotem):

public class Main {

    private void run() {
        System.out.println(greatestElementIndex(new int[]{2, 3, 4, 5, 6, 7}));
        System.out.println(greatestElementIndex(new int[]{7, 6, 5, 4, 3, 2}));
        System.out.println(greatestElementIndex(new int[]{2, 3, 4, 4, 3, 2}));
        System.out.println(greatestElementIndex(new int[]{2, 3, 2, 4, 1, 3}));
        System.out.println(greatestElementIndex(new int[]{1, 0, 0, 0, 0, 0}));
        System.out.println(greatestElementIndex(new int[]{}));
        System.out.println(greatestElementIndex(new int[]{0}));
    }

    public int greatestElementIndex(int[] array) {
        return greatestElementIndex(array, 0, -1, Integer.MIN_VALUE);
    }

    private int greatestElementIndex(int[] array, int index,
            int greatestIndex, int greatestValue) {
        if (index == array.length) {
            return greatestIndex;
        } else if (array[index] >= greatestValue) {
            return greatestElementIndex(array, index + 1, index, array[index]);
        } else {
            return greatestElementIndex(array, index + 1, greatestIndex, greatestValue);
        }
    }

    public static void main(String[] args) {
        new Main().run();
    }
}

PS:
Wg mnie ten kod jest dużo łatwiejszy do wytłumaczenia dla nowicjusza.

To ja może nieco filozoficznie, ale po co tutaj ta rekurencja? Takie miałeś [błąd ortograficzny] zadanie?
Z tego co widze (choć może czegoś nie załapałem), we wszystkich przykładach i tak wszystkie wartości z tablicy są kolejno porównywane do wartośći obecnie maksymalnej i jeśli jest mniejsza to wartości maksymalnej przypisywana jest nowa wartość, ewentualnie indeks wartości maksymalnej. Nie prościej zrobić to w pętli? Bardziej czynatelne, oczywiste, mniej zmiennych i kąbinowania, a i szybkość kodu sądze, że jest na odpowiednim poziomie.
Wiem, że są funkcje wykorzytujace rekurencje które na różne sposoby przyspieszają takie wyszukiwanie, ale te sposoby które tu widze chyba czegoś takiego nie robią.

Takie było pewnie zadanie albo autor jest po prostu zainteresowany.

Jako ciekawostkę podam, że rekurencja ogonowa może na niektórych kompilatorach być szybsza niż pętla :P

Tak jest np na ideone.com: http://ideone.com/hXoeo - G++ 4.3.4
Na G++ 4.5.1 już jest wyrównane: http://ideone.com/AK6ds

Natomiast na moim systemie (G++ 4.6.1) wyniki są takie:

3745596 3870000
3745596 700000
3745596 530000

A więc na moim systemie i wersji G++ pętla wygrywa.

Update:
Można skorzystać jeszcze z domyślnych parametrów. Wtedy kod dla mojej funkcji będzie wyglądał tak:

int wibowit(int *a, int l, int i = 0, int gi = -1, int gv = INT_MIN) {
    if (i == l)
        return gi;
    else if (a[i] < gv)
        return wibowit(a, l, i + 1, gi, gv);
    else
        return wibowit(a, l, i + 1, i, a[i]);
}

Wibowit napisał(a)

Jako ciekawostkę podam, że rekurencja ogonowa może na niektórych kompilatorach być szybsza niż pętla :P
Jeżeli już to nieznacznie. Bo przecież w rekurencji ogonowej chodzi o to aby kompilator z automatu zamienił ją na pętlę ;)

Chyba jednak nie zawsze na pętlę. Na pewno rekurencja ogonowa jest zamieniana na goto do pierwszej instrukcji w metodzie, a używanie goto jest powszechnie źle widziane :P Tak więc rekurencja ogonowa zachowuje (lub tylko nieznacznie odbiega) wydajność goto, nie zmniejsza czytelności i można dzięki niej uniknąć goto/ nadmiaru flag/ itp powodujących krytykę obserwatorów.

Pętla for też jest tak jakby zamieniana na goto (z końca skaczemy do początku). Tak więc powyższy wypowiedź jest totalnie bez sensu ;)

No właśnie. Skaczemy z końca na początek. A nie z dowolnego miejsca.

Z dowolnego. Przykład:

for (;;) {
   akcja1();
   if (warunek) {
      akcja2();
   }
}

daje mniej więcej coś takiego:

początek:
   akcja1();
   if (!warunek) goto poczatek;
   akcja2();
   goto poczatek;

//EDIT
A tak najlepiej to sobie podglądnij czasem wygenerowany kod w assemblerze. Kompilatory są naprawdę sprytne.

No to przerób mi taki kod na pętle i ify:

int dziwna(int a, int b, int c, int d) {
    if (a + b < c)
        if (a == 0)
            return b;
        else if (a - b >= 0)
            return dziwna(a - b, a, c, d);
        else
            return dziwna(b, a, c, d);
    else {
        if (a == 0)
            return c;
        else if (c - d > a)
            return dziwna(c - d, a, c, d);
        else
            return dziwna(d, c, a, b);
    }
}

Jest tu tylko i wyłącznie rekurencja ogonowa, więc GCC powinien to zoptymalizować do goto, ale nie chce mi się tego sprawdzać.

//EDIT
A tak najlepiej to sobie podglądnij czasem wygenerowany kod w assemblerze. Kompilatory są naprawdę sprytne.

Przeglądałem już milion razy. Swoją przygodę z programowaniem zacząłem w ogóle od win32asm, zajmowałem się też łamaniem zabezpieczeń w programach, więc mało co jest mnie w stanie zadziwić w tej kwestii.

Wibowit napisał(a)

No to przerób mi taki kod na pętle i ify:
Ale po co? Przecież teza to "pętla jest równie szybka jak rekurencja ogonowa". Nie widzę związku.

Zresztą chcesz, to masz :) :

int dziwna(int a, int b, int c, int d) {
    for (;;) {
        if (a + b < c) {
            if (a == 0) {
                return b;
            } else if (a - b >= 0) {
                a -= b;
                b += a;
            } else {
                swap(a, b);
            }
        } else {
            if (a == 0) {
                return c;
            } else if (c - d > a) {
                b = a;
                a = c - d;
            } else {
                int tmp = a;
                a = d;
                d = b;
                b = c;
                c = tmp;
            }
        }
    }
}

// EDIT
usunąłem zbędne "continue"

No i widać od razu co jest bardziej czytelne :] Zresztą różnica nie jest jeszcze wielka, mogłem dodać trochę pętli do środka.

Z tą czytelnością chodzi mi przede wszystkim o to, że zamiast bawić się w te wszystkie niezmienniki pętli korzysta się z jednych i tych samych wymagań co do danej (rekurencyjnej) funkcji.

Ale my przecież mówimy o wydajności nie o czytelności.
Jeśli chodzi o czytelność to racja, rekurencja ogonowa może być bardziej czytelna. Ale nie bardziej wydajna.

No to już zależy od przeprowadzonych optymalizacji podczas kompilacji. Podałem przecież przykłady na poprzedniej stronie.

Generalnie różnicy w wydajności nie powinno być żadnej, ale optymalizacje w GCC są mocno niestabilne (np gdy testowałem quicksorty własnej roboty, to w niektórych wariacjach dodanie liczników np porównań poprawiało wydajność (!!!), co jest mocno nieintuicyjne).

Powtórzę jeszcze raz. Różnica w wydajności będzie nieznaczna z racji takiej, że rekurencja ogonowa to automatyczna zamiana rekurencji na iterację, czyli to samo co w przypadku pętli, też iteracja.

Kompilator może sobie to wszytko inaczej zoptymalizować ale generalnie otrzymamy bardzo podobny kod wynikowy.

Nie rozumiem już do czego pijesz i po co się powtarzasz.

Piję do tego, że twierdzenie

Wibowit napisał(a)

Na pewno rekurencja ogonowa jest zamieniana na goto do pierwszej instrukcji w metodzie, a używanie goto jest powszechnie źle widziane :P Tak więc rekurencja ogonowa zachowuje (lub tylko nieznacznie odbiega) wydajność goto
ma się tak samo do rekurencji ogonowej jak i do pętli.

adf88 napisał(a)

Pętla for też jest tak jakby zamieniana na goto (z końca skaczemy do początku). Tak więc powyższy wypowiedź jest totalnie bez sensu ;)

Gdzie ten brak sensu w takim razie? Sam się zgodziłeś, że rekurencja ogonowa może być dużo czytelniejsza od wydziwianych pętli.

Pisałeś o rekurencji ogonowej jako dającej się lepiej zoptymalizować niż pętlę, gdyż można "użyć goto". W tym jest brak sensu gdyż w przypadki pętli równie dobrze można "użyć goto".

Napisałem, że niektóre kompilatory lepiej sobie radzą z optymalizacją rekurencji ogonowej niż pętli i to w dodatku napisałem jako ciekawostkę, a nie coś na czym można polegać. Czytaj ze zrozumieniem.