Рекурсия и фишки

выдает 1 2 -1 3 -3 -2 -1 4 1 2 -1

вместо 1 2 -1 3 -3 -2 -1 4 1 2

А почему вы считаете, что 3 -3 правильно? Ведь вы ставите фишку, а потом сразу её убираете.. какой в этом смысл? Зачем тогда было её туда ставить?

Я написал для самотренировки рекурсию с одним параметром и у меня вышло следующее

1 2 -1 3 -2 4 2 1

UPD По просьбе трудящихся привожу свой код. Надеюсь, вы простите меня, что я написал на Java, так как мне было сподручнее. Исправить обратно на C будет совсем просто.

package cg;
import java.io.BufferedReader;
import java.io.InputStreamReader;
/**
 * @author Sergey Mashkov
 */
public class Main {
    private void processCell(int cell, int N) {
        if (cell <= N) {
            printCell(cell);
            if (cell < N) {
                if (cell > 1) {
                    printNegateCell(cell - 1);
                }
                processCell(cell + 1, N);
            }
        }
    }
    private void processCells(int N) {
        if (N > 0) {
            processCell(1, N);
            processCells(N - 2);
        }
    }
    private void printNegateCell(int cell) {
        System.out.print('-');
        printCell(cell);
    }
    private void printCell(int cell) {
        System.out.print(cell);
        System.out.print(' ');
    }
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine().trim());
        new Main().processCells(N);
        System.out.println();
    }
}

Объяснение простое. Сначала мы пытаемся захватить самую правую клетку. Для этого мы берём текущую, затем берём следующую, а потом снимаем текущую. Но снимаем только если мы не захватили последнюю (если мы захватили последнюю, то это значит, что клетка за ней тоже захвачена, а раз так, то у нас захвачено две последних клетки и снимать клетку не имеет смысла). Далее, начинаем всё по новой начиная с первой клетки до тех двух последних, которые были захвачены на предыдущей итерации. И так повторяем проходы слева направо отщипывая от линейки по две концевые до тех пор, пока всё не будет заполнено. Очевидно, сложность будет N / 2 проходов, каждый проход ~2n шагов.. n уменьшается каждый раз на два.. арифметическая прогрессия получается.. вам не составит труда оценить, что для N=10 будет точно меньше 10000. Да и эксперимент подтвердит ;)