Hi, the solution is given in python but you can follow the same logic and apply it for any programing language (see explanation).
Answer:
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 parameter
- We 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 condition
- If 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, ...)
