### Recursion in python

### SOME BASICS:

def g(n):
    return n+1

print map(g,[1,2,3])
print map(lambda x: x*x, [1,2,3,4])

A= [2,4,6,8,10]
print A[1:3]

### short circuit booleans:
x = 2
y = 2-x  # y is zero

y!=0 and (x/y != 1)
##  (x/y != 1) and y!=0   ### NOT THE SAME:

### Similarly with OR: second case evaled only if first is true

### explain runtime stack. ###########################

##############################

### Technical definition of recursion: a function that calls itself
### (directly or indirectly).

### Hard because requires an abstract, declarative style of thinking as
### opposed to imperitive/operational.

### Misconceptions about recursion abound: people tend to make wrong
### generalizations about recursion based on seeing just a few examples.


### Closest thing you've seen: inductive proofs.


## Simplest example of recursion:

def f0():
    print "hello world"
    f0()
#

### A little bit more interesting:

def f(n):
    print "hello world " + str(n)
    if (n>0): f(n-1)
##

f(20)

#### But why use that if a while loop is more efficient?  Indeed for this
##   example, recursion is probably not the right usage.

#### More intersting examples of recursion:

def fact(n):
    if n<2: return 1
    else: return n*fact(n-1)
#
print fact(7)

## Proof fact(n) returns n! where: n! = n* (n-1)!
## base case: for n<1: 1 = 1!, 0!
## inductive hypothesis: assume that fact(n-1) returns (n-1)!, then
## fact(n) returns n*fact(n-1) = n*(n-1)!

### reversing a string

def reverse(s):
    n = len(s)
    if n==0: return s
    else: return reverse(s[1:n]) + s[0]
#
print reverse("abcd")

### proof: rev of empty string is empty.
### hypothesis: ASSUME reverse(s[1:n]) reverses rest of string
### what do I need to do to reverse it?


### count number of occurrences of x in A:
def count(x,A):
    n = len(A)
    if n<1: return 0
    else:
        if A[0]==x: return 1+count(x,A[1:n])
        else: return count(x,A[1:n])
### how to think about this: both imperatively and DECLARATIVELY.  SHOW
### stack.

###############
def gcd(a,b):
    if a==0: return b
    else: return gcd(b%a,a)
###
print gcd(12,8)


#### binary search

def search(x,A,min,max):
    if min>max: return False
    else: 
        i = (min+max)/2
        return A[i]==x or (x<A[i] and search(x,A,min,i-1)) or search(x,A,i+1,max)
### search

## for comparison, non-recursive binary search:
def bsearch(x,A):
    ax = False
    min,max = 0,len(A)-1
    while min<=max ans not(ax):
        i = (min+max)/2
        if A[i]==x: ax=True
        if x<A[i]: max = i-1
        if x>A[i]: min = i+1
    # while
    return ax
###



##### fibonacci:

def fib1(n):
    a,b = 0,1
    while n>0:
        a,b = b,a+b
        n -= 1
    # while
    return b
###

def fib2(n,a=1,b=1):
    if n<1: return b
    else: return fib(n-1,b,a+b)
###

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

###
F = [1,1]
def fib4(n):
    if len(F)>n: return F[n]
    if n<1: return 1
    else:
       answer = fib4(n-2) + fib4(n-1)
       F.append(answer)
       return answer
#fib4
print fib4(100)



############ generating list of all possible permutations of a string.
############ assume no duplicates.  (easy modification)

# A.replace("x","")   ## removes x from string, non-destructively

def perms(S):
    if len(S)<1: return [S]
    P = []
    for c in S:
        T = S.replace(c,"")
        PT = perms(T)
        P = P + map(lambda x: c+x, PT)
    return P
# perms

print perms("abcd")