/******************************************************************************
 *  Compilation:  javac Recursion.java
 *  Execution:    java Recursion n
 *
 *  Some recursive functions for you to trace through.
 *
 *  % java Recursion 0
 *  0
 *
 *
 *
 *  % java Recursion 1
 *  0 1
 *  1 1
 *
 *  1 1
 *
 *  % java Recursion 5
 *  2 0 1 4 3 5
 *  5 3 1 1 3 2 2 5
 *  3 2 5 2 4 3 2
 *  2 2 5 3 1 1 3 5
 *
 ******************************************************************************/

public class Recursion {

    public static void mystery1(int a, int b) {
        if (a <= b) {
            int m = (a + b) / 2;
            StdOut.print(m + " ");
            mystery1(a, m-1);
            mystery1(m+1, b);
        }
    }

    public static void mystery2(int n) {
        if (n > 0) {
            StdOut.print(n + " ");
            mystery2(n-2);
            mystery2(n-3);
            StdOut.print(n + " ");
        }
    }

    public static void mystery3(int n) {
        if (n == 0 || n == 1) return;
        mystery3(n-2);
        StdOut.print(n + " ");
        mystery3(n-1);
    }

    public static String mystery4(int n) {
        if (n <= 0) return "";
        return mystery4(n-3) + n + " " + mystery4(n-2) + n + " ";
    }



    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        mystery1(0, n);
        StdOut.println();
        mystery2(n);
        StdOut.println();
        mystery3(n);
        StdOut.println();
        StdOut.println(mystery4(n));

    }

}