### examples of recursion

def f1(n):
  return f1(n+1)
#
#print f1(1)

def f2(n):
  if n>0:
    print n
    f2(n-1)
#def f2

#f2(10)


def fact(n):
  if n<2: return 1
  else: return n*fact(n-1)
#
#print fact(5)
# The second worst example of recursion EVER
#print fact(1000)

def factorial(n):
  ax = 1
  while n>2:
    ax = ax *n
    n  = n-1
  return ax
#

def g(n):
  if n<2: return 0
  else: return 1 + g(n/2)
#

#print g(1024)
#print g(392412347137832974)

### The absolute worst example of recursion EVER!!!

def fib(n):
  if n<3: return 1
  else: return fib(n-1) + fib(n-2)
#

import sys
n = int(sys.argv[1])
#print fib(n)

def fib2(n):
  a,b = 1,1
  while n>2:
    a,b = b,a+b
    n -= 1
  #
  return b
# fib2
#print fib2(n)

def permutations(s): # return array of permutations of string s
  if (len(s)<2): return [s] # base case
  AX = []  # to be returned
  # separate first char of s from rest
  first = s[0]
  rest = s[1:]
  PR = permutations(rest)
  for perm in PR:  # ["bc", "cb"]  if s is "abc"
    i = 0
    while i<=len(perm):
      # insert first into position i of perm:
      newperm = perm[:i] + first + perm[i:]
      AX.append(newperm)
      i +=1
    # while
  #for
  return AX
#permutations

#print permutations("abcdefghijklmnop")
#print factorial(16)


# sorting an array
def sinsert(x,A): # insert x into sorted array A:
  i = 0
  while i<len(A) and x>A[i]:
    i = i+1
  #
  A.insert(i,x)
#sinsert

def insertionsort(A):
  B = []
  for x in A:
    sinsert(x,B)
  return B
#insertionsort

#print insertionsort([7,2,3,5,1,9,8])


### mergesort
def merge(SA,SB):  # merge two sorted lists into one sorted list
  i,j = 0,0  # indexes SA,SB
  S = []  # sorted list to be returned
  while i<len(SA) and j<len(SB):
    if SA[i]<SB[j]:
      S.append(SA[i])
      i += 1
    else:
      S.append(SB[j])
      j += 1
  #
  # add the rest
  while i<len(SA):
    S.append(SA[i])
    i += 1
  while j<len(SB):
    S.append(SB[j])
    j += 1
  return S
#merge
def mergesort(A):
  if len(A)<2: return A  # base case
  mid = len(A)/2
  left = A[:mid]
  right = A[mid:]
  SA = mergesort(left)
  SB = mergesort(right)
  S = merge(SA,SB)
  return S
#mergesort

#print mergesort([7,2,3,5,1,9,8])

n =10
if len(sys.argv)>1: n = int(sys.argv[1])  # size of array to sort

# create two copies of a randomly generated array
A = [0]*n
B = [0]*n

from random import random,randint

while n>0:
  A[n-1] = random()*10000
  B[n-1] = A[n-1]  # make copy to test two sorting procedures
  n -= 1
#while

#print "before sort:",A

A = mergesort(A)
#B = insertionsort(B)

#print A
#print B