Question

THIS IS ALL ON PYTHON

Recursion Practice

Recall from lecture that a recursive function is one that calls on itself. Recursive functions have two parts, the base case which stops the recursion and the recursive step where the function calls upon itself.

When designing recursive algorithms, your goal for each step should be to work towards the base case. More abstractly, each recursive call decreases the size of the problem, working ever closer to some trivial case with a defined solution.

uppercount(s)

Write a recursive function uppercount(s) that counts a number of uppercase letters in the input string. Do not use loops or built-in Python string functions (the only string functions you can use are slicing and indexing).

>>>> n = uppercount("Hello, World")
print(n)
2

Add comments to your code to point out the base case and the recursive case.

clean_string(s)

From the standpoint of Python, words like ”world” and ”world!” as different words. So if we wrote an automatic English-to-Spanish translator that replaced ”world” with ”mundo”, ”world” would have been replaced and ”world!” wouln’t. I.e. we notice that before we can write a program for automatic translation, we need to find a way to ignore punctuation in a string. Write a recursive function clean_string(s) that would remove all symbols that are not uppercase or lowercase letters or space from s and return the ”clean” string.

Do not use loops.

>>>> CS = clean_string("Hello, world") print(CS)
Hello world

Add comments to your code to point out the base case and the recursive case.

clean_list(lst1, lst2)

Using a similar idea to the one you employed in clean string(s) function, write a recursive function clean_list(l1, l2) that takes two lists as input and returns a list of elements from lst1 that are not present in lst2.

Do not use loops.

>>>> unique = clean_list([1,2,3,4,5,6,7], [2,4,6]) print(unique)
[1,3,5,7]

Add comments to your code to point out the base case and the recursive case.

Recursions vs. Iteration

As we discussed, recursion is a very powerful problem-solving technique. In fact, any computation can be expressed recursively. However, recursion doesn’t always lead to efficient solution, as you will now see. A classic example of recursion is the definition of Fibonacci number.

Wikipedia has a good article about it: Fibonacci Number. (Remember to check the part that talks about Fibonacci numbers in nature).

A Fibonacci number is defined as follows:

F(0) = 0
F(1) = 1
F(n) = F(n−1) + F(n−2) for n > 1.

Recursive Fibonacci

Write a recursive function F(n) that returns n-th Fibonacci number. In comments, mark the base case and recursive step.

Iterative Fibonacci

Write an iterative function (using iteration, i.e. loop(s)) f(n) that returns n-th Fibonacci number.

Answer 1

'''
Python version : 3.6
Python program to define recursive functions
'''

def uppercount(s):
   """
   Recurisve function that counts a number of uppercase letters in the input string.
   """
   # recursive step: number of characters in s > 0
   if len(s) > 0:
  
       # first character is uppercase, return 1 + number of uppercase characters in substring from index 1 to end
       if(s[0] >= 'A' and s[0] <= 'Z'):
           return 1 + uppercount(s[1:])
       else: # first character is not uppercase, return number of uppercase characters in substring from index 1 to end
           return uppercount(s[1:])
  
   else: # base step: empty string
       return 0
      
def clean_string(s):
   """
   Recurisve function that would remove all symbols that are not uppercase or lowercase
   letters or space from s and return the 'clean' string.
   """
   # recursive step: number of characters in s > 0
   if len(s) > 0:
       # first character is letter or space, return the first character + string obtained
       # by calling clean_string with substring from index 1 to end
       if((s[0] >= 'a' and s[0] <= 'z') or (s[0] >= 'A' and s[0] <= 'Z') or s[0] == ' '):
           return s[0] + clean_string(s[1:])
       else:
           # first character is not a letter or space, return the string obtained
           # by calling clean_string with substring from index 1 to end
           return clean_string(s[1:])
  
   else: # base step: empty string
       return ""

def clean_list(lst1, lst2):
   """
   Recurisve function that takes two lists as input and
   returns a list of elements from lst1 that are not present in lst2.
   """
   # recursive step: number of elements in lst1 > 0
   if len(lst1) > 0:
       # if first element of lst1 is not in lst2, return list containing first element of lst1 and
       # list returned by calling clean_list with sublist from index 1 to end and lst2
       if lst1[0] not in lst2:
           return lst1[0:1] + clean_list(lst1[1:], lst2)
       else:
           # if first element of lst1 is in lst2, return list returned by
           # calling clean_list with sublist from index 1 to end and lst2
           return clean_list(lst1[1:],lst2)
  
   else: # base step: empty list1
       return []
      
def fibonacci(n):
   """
   Recurisve function that returns n-th Fibonacci number
   """
   # base step: n <= 1 i.e n is 0 or 1, return n
   if n <= 1:
       return n
   else: # recursive step: n > 1 return sum of n-1 and n-2 fibonacci numbers
       return fibonacci(n-1) + fibonacci(n-2)
              
def f(n):
   """
   Iterative function that returns nth fibonacci number
   """
   # n<=1, return n
   if n <= 1:
       return n
   else: # n > 1
       # set f1 to 0 and f2 to 1 i.e first 2 fibonacci numbers
       f1 = 0
       f2 = 1
       c = 2 # set counter c to 2 (number of fibonacci numbers generated)
      
       # loop that continues until nth fibonacci number has been generated
       while c <= n:
           f3 = f1 + f2 # set f3 to f1+f2
           f1 = f2 # set f1 to f2
           f2 = f3 # set f2 ti f3
           c += 1 # increment c by 1
          
       # after loop nth fibonacci is in f2 and f3  
       return f3  
              
# test the functions              
print("uppercount(\"Hello, World\"):", uppercount("Hello, World"))      
print("clean_string(\"Hello, World\"):", clean_string("Hello, World"))
print("clean_list([1,2,3,4,5,6,7], [2,4,6]):",clean_list([1,2,3,4,5,6,7], [2,4,6]))
print("fibonacci(8):", fibonacci(8))
print("f(8):",f(8))

#end of program

Code Screenshot:

Output: