class Reverse 
{
	/**
	 * Algoritmen virker meget simpelt ved at vi hele
	 * tiden splitter vores streng op på midten, indtil
	 * vi når en streng på længde 2 eller under. Alle
	 * de dele vi får, samles derefter i omvendt rækkefølge,
	 * hvorved vi opnår at stregen bliver reversed.
	 */
	private static String recursiveReverse(String s) {
		if (s.length() > 2) {
			int split = s.length()/2;
			String left = recursiveReverse(s.substring(0,split));
			String right = recursiveReverse(s.substring(split));
			return right.concat(left);
		} else if (s.length() == 2) {
			return s.substring(1).concat(s.substring(0,1));
		} else {
			return s;
		}
	}

	/**
	 * Algoritmen kørt på strengen "Lars":
	 *
	 * Lars  =>  ars L  =>  rs aL  =>  s raL  =>  sraL
	 * ----^     ---^       --^        -^
	 * 
	 * Algoritmen virker ved at vi hele tiden flytter det
	 * foreste tegn i stregen frem til en markør (length).
	 * Denne markør starter med at pege på slutningen af
	 * stregen (s.length()) og tælles derefter ned indtil
	 * den når nul, hvorefter vi er færdige.
	 */
	private static String linearReverse(String s) {
		for (int length = s.length(); length > 0; length--) {
			s = s.substring(1,length) // andet tegn op til length markøren
			     .concat(s.substring(0,1)) // første tegn
			     .concat(s.substring(length)); // resten af stregen
		}
		return s;
	}
}