znajdź element w środku stosu

Rekurencja nigdy nie jest jedynym sposobem;)

Jednakże, rekurencja zapewnia dodatkowy stos (tj. parametry funkcji i zmienne lokalne) i wydaje się, że potrzebujesz dodatkowej pamięci do przechowywania przejeżdżanych elementów, w takim przypadku wygląda na to, że rekurencja może być jedynym sposobem, biorąc pod uwagę to ograniczenie.

Oto jedno rozwiązanie: weź dwa wskazówki, jeden z nich posuwaj się dwa kroki na raz (szybko), drugi tylko jeden krok na raz (wolno). Jeśli szybki osiągnie dno, zwróć powolny wskaźnik, który wskazuje na środkowy indeks. Nie wymaga rekurencji.

int * slow = stack;
int * fast = stack;
while(1) {
    if(STACK_BOTTOM(fast)) return slow;
    fast--;
    if(STACK_BOTTOM(fast)) return slow;
    slow--;
    fast--;
}

Rekurencja wydaje się być jedynym sposobem. Jeśli spróbujesz użyć koncepcji szybkiego i wolnego wskaźnika podczas wyświetlania, będziesz musiał gdzieś przechowywać wartości, co narusza wymóg braku dodatkowej struktury danych.

To pytanie jest oznaczone c, więc dla języka programowania c zgadzam się, że rekurencja jest jedynym sposobem. Jeśli jednak obsługiwane są funkcje anonimowe pierwszej klasy, można je rozwiązać bez rekursji. Niektóre pseudo kod (używając składni lambda Haskella):

n = 0
f = \x -> 0        # constant function that always returns 0

while (not stack_empty) do
    x = pop
    n = n+1
    f = \a -> if (a == n) then x else f(a)

middle = f(n/2)    # middle of stack

# stack is empty, rebuilt it up to middle if required 
for x in (n .. n/2) do push(f(x))

UWAGA: podczas pętli while nie ma (rekurencyjnego) wywołania f. f(a) w gałęzi else służy tylko do konstruowania nowego (!) funkcji, która jest wywoływana ponownie f.

Zakłada się, że stos ma 3 elementy 10, 20, 30 (od dołu do góry) to w zasadzie konstruuje lambda

(\a -> if a==1
       then 30
       else (\b -> if b==2
                   then 20
                   else (\c -> if c==3
                                  then 10
                                  else (\d -> 0)(c)
                        )
                        (b)
            )
            (a)
)

Lub nieco bardziej czytelny

f(x) = if x==1 then 30 else (if x==2 then 20 else (if x==3 then 10 else 0)) 

"... Nie używaj żadnej dodatkowej struktury danych. ..."

Wtedy zadanie jest nierozwiązywalne, ponieważ potrzebujesz miejsca, w którym można przechowywać wyskakujące dane. Do rekurencji potrzebny jest inny stos, który jest również strukturą danych. Nie ma sensu zabraniać jakiejkolwiek struktury danych i zezwalać na rekurencję.