Skip to content

Question 27

Given the following recursive function:

1
2
3
4
5
6
7
def pascal(r, c):
    print((r, c))
    if r < c:
        return 0
    if r <= 1 or c <= 1:
        return 1
    return pascal(r-1, c) + pascal(r-1, c-1)

How many lines will be printed out for pascal(5,2)?

Solution 
# For pascal(5,2):
=> 1 print statement + pascal(4, 2) + pascal(4, 1)
=> 1 print statement + (1 print statement + pascal(3, 2) + pascal(3, 1)) + (1 print statement + return 1)
=> 3 print statements + 1 return + pascal(3, 2) + pascal(3, 1)
=> 3 print statements + 1 return + (1 print statement + pascal(2, 2) + pascal(2, 1)) + (1 print statement + return 1)
=> 5 print statements + 2 returns + pascal(2, 2) + pascal(2, 1)
=> 5 print statements + 2 returns + (1 print statement + pascal(1, 2) + pascal(1, 1)) + (1 print statement + return 1)
=> 7 print statements + 3 returns + pascal(1, 2) + pascal(1, 1)
=> 7 print statements + 3 returns + (1 print statement + return 0) + (1 print statement + return 1)
=> 9 print statements + 5 returns

I think the question phrasing here may be a little confusing - find the number of lines that are printed when simply invoking pascal(5,2) and not print(pasccal(5,2)). This means that anything returned from pascal() will not be printed out, hence we can ignore the returned value and focus on the number of times the print((r,c)) statement was reached when recursively calling pascal().

Answer

9 lines