# William M. Farmer
# recursion.py
# 3 April 2012


# reverse reverses a value of any sequence type.

def reverse(seq):
    if not seq:                           # seq is empty
        return seq
    else:                                 # seq has at least one member
        n = len(seq)
        return reverse(seq[1:n]) + seq[0:1]

# reverse with illuminating print statements.

def reverse(seq):
    print "reverse", str(seq)
    if not seq:  
        print seq                         # seq is empty
        return seq
    else:                                 # seq has at least one member
        n = len(seq)
        seq1 = reverse(seq[1:n])
        print str(seq1), "+", str(seq[0:1]), "=", str(seq1 + seq[0:1])
        return seq1 + seq[0:1]

# sumRec implements the big sigma notation.
#
# m,n are integers.
# f is function from integers to integers.
#
# sum returns f(m) + f(m + 1) + ... + f(n) if m <= n and 
# returns 0 if m > n.

def sumRec(m, n, f):
    if m > n:
        return 0
    else:
        return sumRec(m, n - 1, f) + f(n)

# superSumRec is a generalization of sum.
#
# add is function that acts like addition on a some set S of values.
# zero is in S and is the additive identity with respect to add.
# m,n are integers.
# f is function from integers to S.
#
# superSum returns f(m) add f(m + 1) add ... add f(n) if m <= n and 
# returns zero if m > n.
#
# Technical note: (S,add,zero) must be a monoid.

def superSumRec(add, zero, m, n, f):
    if m > n:
        return zero
    else:
        return add(superSumRec(add, zero, m, n - 1, f), f(n))

# Let a leaf be a value that is not a list.  Given a list x as input,
# countLeaves counts the number of leaves in the list x, plus the
# number of leaves in the members y_1,...y_m of x that are lists, plus
# the number of leaves in the members z_1,...,z_n of y_1,...y_m that
# are lists, etc.

def countLeaves(x):
  c = 0
  if not(isinstance(x,list)):
    c = c + 1
  elif x == []:
    c = c + 0
  else:
    c = countLeaves(x[0]) + countLeaves(x[1:])
  return c

# If

x = [1,[2,3,[4,5,6],[7,[8]]],[9],10]
y = [1,[2,[3,[4,[5,[6,[7,[8,[9,[10,[11,[12,[13]]]]]]]]]]]]]
z = [[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]

# then the following evaluate to True:

countLeaves(x) == 10
countLeaves(y) == 13
countLeaves(z) == 0

