Write a recursive function to compute Jeanie's total number of ancestors if we go back n generations. Specically, (num-ancestors n) should return: 2 + 4 + 8 + · · · + an Use your function in part (a) as a helper function in the denition of (num-ancestors

Hi, the solution is given in python but you can follow the same logic and apply it for any programing language (see explanation).

def num_ancestors(n, number_of_ancestors=2):

   if n == 0:

       return(0)

   elif n == 1:

       return(number_of_ancestors)

   else:    

       return(num_ancestors(n-1, number_of_ancestors+2**n))

Explanation:

We define a function call 'num_ancestors' that receive the number of generation 'n'; the other parameter (number_of_ancestors) can be ignored for now, it's purpose is initialization only and it shouldn't be pass as an input parameterWe check if the number of generation is zero, if True we return zero We check if the number of generations is one, If True we return the number of ancestors, this is common in recursion and this 'if' statement is called the test conditionIf n is not one we apply recursion by calling the function again and decreasing the number of generations to be checked (at the end n must be one to finish the program), here we also modify the number of ancestors taking the previously stored value and adding two to the power of the number of generations (this is because of the nature of the sequence 2, 4, 8, ...)