Q11 /20 There is a staircase of n steps and you are on the bottom of the staircase, on the...

There is a staircase of n steps and you are on the bottom of the staircase, on the 0-th step. You can go up any of 1, 2, or 3 steps at a time. Let us consider the problem of counting the number of step-taking patterns that will put you on exactly the n-th step from the bottom.

For instance, if there are n = 4 steps, there are 7 patterns as follows. Each number is the number of steps you take at one time.

• 1, 1, 1, 1.
• 2, 1, 1.
• 1, 2, 1.
• 1, 1, 2.
• 2, 2.
• 1, 3.
• 3, 1.

For this problem, you implemented a function solve as follows.
Note that all the variables are multiple precision integers.

function rec(i):
  if i == 0:
    return 1
  else:
    ans = 0
    if i >= 1:
      ans += rec(i-1)
    if i >= 2:
      ans += rec(i-2)
    if i >= 3:
      ans += rec(i-3)
    return ans

function solve(n):
  return rec(n)

However, the program is too slow and it does not return the answer for n = 1000 even if you wait a whole day. You want to speed up the program so that it returns the answer in one second even if n is in the range between 1000 and 10000.

Which one of the following correctly states the reason the function is too slow and the solution to fix the slowness?