Recursion Examples http://codingbat.com/prob/p158888

Recursion.py

#Factorial Recursive Function

def factorial(n):
    if n>1:
        return n * factorial(n-1)
    else:
        return 1
        
#Fibonnaci Function
l = []
def fibonacci(n):
    if n == 1 or n==0:
        return n
    else:
       g =  fibonacci(n-1) + fibonacci(n-2)
       l.append(g)
       return g
print set(l)    

#Bunny Ears
#We have a number of bunnies and each bunny has two big floppy ears. 
#We want to compute the total number of ears across all the bunnies recursively (without loops or multiplication). 

def bunny_count(n):
    if  n==0:
        return 0
    else:
        return  2+bunny_count(n-1)
#We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3, ..) have the normal 2 ears. 
#The even bunnies (2, 4, ..) we'll say have 3 ears, because they each have a raised foot. 
#Recursively return the number of "ears" in the bunny line 1, 2, ... n (without loops or multiplication). 
        
def bun_even_odd(n):
    if n==0:
        return 0
    if n%2 == 0:
        return 2+bun_even_odd(n-1)
    else:
        return 3+bun_even_odd(n-1)

#Iterative
def bunny_iter(n):
    count = 0
    for i in range(1,n+1):
        if i%2==0:
            count+=2
        else:
            count+=3
    return count
    
#Sum Of Blocks in a rows, That form a triangle.
#We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, 
#and so on.Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given 
#number of rows. 
def triangle_count(n):
    if n==0:
        return 0
    else:
        return n+triangle_count(n-1)
        
#Sum of Digits
#Given a non-negative int n, return the sum of its digits recursively (no loops). 
#Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), 
#while divide (/) by 10 removes the rightmost digit (126 / 10 is 12). 

def sum_digits(n):
    if n == 0:
        return 0
    else:
        return n%10 + sum_digits(int(n/10))
        
#Iterative
def iter_sum_digits(n):
    count = 0
    while(1):
        if n==0:
            break
        else:
            count += n%10
            n = int(n/10)
    return count
    

#Given a non-negative int n, return the count of the occurrences of 7 as a digit, 
#so for example 717 yields 2. (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), 
#while divide (/) by 10 removes the rightmost digit (126 / 10 is 12). 

def count_instance(e,n):
    if n==0:
        return 0
    if n%10==e:
        return 1+count_instance(e,n/10)
    return count_instance(e,n/10)
    
#Iterative
def count_instance_iter(e,n):
    count = 0
    while(1):
        if n==0:
            break
        elif n%10==e:
            count +=1
        n = n/10
    return count

#Given a non-negative int n, compute recursively (no loops) the count of the occurrences of 8 as a digit, 
#except that an 8 with another 8 immediately to its left counts double, so 8818 yields 4. Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), 
#while divide (/) by 10 removes the rightmost digit (126 / 10 is 12). 
def count_success(n):
    if n==0:
        return 0
    if n%100==88:
        return 2+count_success(n/10)
    if n%10 == 8:
        return 1+count_success(n/10)
    return count_success(n/10)    

#Iterative    
def count_success_iter(n):
    count = 0
    while(1):
        if n==0:
            break
        if n%100 == 88:
            count +=2
        elif n%10 == 8:
            count+=1
        n=n/10
    return count

#Power of a value to a given element
#Given base and n that are both 1 or more, compute recursively (no loops) the value of base to the n power,
#so powerN(3, 2) is 9 (3 squared). 

def power_of_elem(v,n):
    if n==0:
        return 1
    if n==1:
        return v
    else:
        return v * power_of_elem(v,n-1)