python count of the recursive calls to function-CodePudding

The amount of recursive calls to the following function need to be counted:

def fb(n, d):
    if n in d:
        return d[n]
    else:
        ans = fb(n-1, d)   fb(n-2, d)
        d[n] = ans
        return ans
d = {1:1, 2:2}
print(fb(8, d))
print(d)

Now i understand the function, and what essentially happens, i just cant wrap my brain around counting the amount of recursions manually(by hand). I can count the recursions with code or jsut by looking at 'd' but im unable to understand why there are only 13 recursive calls in the end.

The following happens in my mind: ans makes 2 recursive calls (n = 7 and n = 6) each of these two make two more calls etc etc till all these calls end with an n of 2 or 1.

But if i look at the code, and just print the n on every time the function is run i get the following output:

def fb(n, d):
    if n in d:
        return d[n]
    else:
        print(n)
        ans = fb(n-1, d)   fb(n-2, d)
        d[n] = ans
        return ans
d = {1:1, 2:2}
print(fb(8, d))

Output:

Now i know the answer is 13, 2 calls to the function (2 * 6) on each number the last call which returns the ans. But my question is, how is this internally working, and how can i replicate this thought process in my head.

Thank you for your time.

CodePudding user response：

This might help you to understand it:

def fb(n, d, indent):
    if n in d:
        print(indent, n, "old")
        return d[n]
    else:
        print(indent, n, "new")
        indent2 = indent   "  "
        ans = fb(n-1, d, indent2)   fb(n-2, d, indent2)
        d[n] = ans
        return ans
d = {1:1, 2:2}
print(fb(8, d, ""))

I augmented the function in two different ways: (1) I show all calls, whether the value is old or new, and (2) I indent based on the call depth. The results are:

 8 new
   7 new
     6 new
       5 new
         4 new
           3 new
             2 old
             1 old
           2 old
         3 old
       4 old
     5 old
   6 old
34

As you can see, it starts with a chain of recursive calls with n-1, getting new values until it reaches 2. At that point, it's an old value, so it returns immediately.

The caller then makes a recursive call with n-2 (i.e. 1). This is the first time the n-2 call has been executed. And of course, it too is an old value so it returns immediately. The caller then adds the two, stores the result (for 3), and returns. This is the first time a new case has returned.

It then just repeats, but now all of the n-2 calls are old calls. When it reaches the top level, it adds the results for 7 and 6 to obtain the value for 8, and returns to the top-level caller, giving a result of 34.

CodePudding user response：

The following happens in my mind: ans makes 2 recursive calls (n = 7 and n = 6) each of these two make two more calls etc etc till all these calls end with an n of 2 or 1.

You need to be more strict about your logic here. First of all ans is a variable. So saying "ans makes 2 recursive calls" is nonsense. Also, the line with the recursive calls is inside the else block of an if statement, so you need to evaluate the condition of the if to determine whether or not a recursive call even happens.

So let's analyze this more thoroughly for fib(7). Since 7 is not a key in the dictionary, we make a recursive call to fib(6). This in turn calls fib(5) and so on until we get to fib(2). Let's represent each recursive call with indentation:

fib(7)
  fib(6)
    fib(5)
      fib(4)
        fib(3)
          fib(2)

Now we get to a point where the if condition is True because the dictionary has 2 as a key. So and fib(2) returns 2. Let's note that with ->

fib(7)
  fib(6)
    fib(5)
      fib(4)
        fib(3)
          fib(2) -> 2

Now fib(3) calls fib(n - 2) which is fib(1). And fib(1) returns 1. We just add this with the appropriate level of indentation:

fib(7)
  fib(6)
    fib(5)
      fib(4)
        fib(3)
          fib(2) -> 2
          fib(1) -> 1

Now fib(3) adds the result of 2 1 to the dictionary and returns:

fib(7)
  fib(6)
    fib(5)
      fib(4)
        fib(3) -> 3
          fib(2) -> 2
          fib(1) -> 1

Now we are at the fib(4) level, which calls fib(2) and which returns 2:

fib(7)
  fib(6)
    fib(5)
      fib(4)
        fib(3) -> 3
          fib(2) -> 2
          fib(1) -> 1
         fib(2) -> 2

And now fib(4) returns 3 2:

fib(7)
  fib(6)
    fib(5)
      fib(4) -> 5
        fib(3) -> 3
          fib(2) -> 2
          fib(1) -> 1
         fib(2) -> 2

Now we are back at the fib(5) call which calls fib(n - 2) or fib(3):

fib(7)
  fib(6)
    fib(5)
      fib(4) -> 5
        fib(3) -> 3
          fib(2) -> 2
          fib(1) -> 1
         fib(2) -> 2
       fib(3)

But we already called fib(3) and stored its value in the dictionary. So this returns immediately without any additional recursive calls:

fib(7)
  fib(6)
    fib(5)
      fib(4) -> 5
        fib(3) -> 3
          fib(2) -> 2
          fib(1) -> 1
         fib(2) -> 2
       fib(3) -> 3

And now fib(5) returns 5 3:

fib(7)
  fib(6)
    fib(5) -> 8
      fib(4) -> 5
        fib(3) -> 3
          fib(2) -> 2
          fib(1) -> 1
         fib(2) -> 2
       fib(3) -> 3

Now we are back at fib(6) which calls fib(4). Again, we have already calculated this and its result is returned immediately:

fib(7)
  fib(6)
    fib(5) -> 8
      fib(4) -> 5
        fib(3) -> 3
          fib(2) -> 2
          fib(1) -> 1
         fib(2) -> 2
       fib(3) -> 3
    fib(4) -> 5

Now fib(6) returns 5 8:

fib(7)
  fib(6) -> 13
    fib(5) -> 8
      fib(4) -> 5
        fib(3) -> 3
          fib(2) -> 2
          fib(1) -> 1
         fib(2) -> 2
       fib(3) -> 3
    fib(4) -> 5

And we are back at fib(7) which calls fib(5) next. Again, we have already calculated this value and stored it, so we return immediately:

fib(7)
  fib(6) -> 13
    fib(5) -> 8
      fib(4) -> 5
        fib(3) -> 3
          fib(2) -> 2
          fib(1) -> 1
         fib(2) -> 2
       fib(3) -> 3
    fib(4) -> 5
  fib(5) -> 8

And finally fib(7) returns 13 8 or 21.

As you can see there are 11 recursive calls for fib(7). I let you do the rest of the analysis for fib(8).

CodePudding user response：

Here are the calls, in a tree shape (only the value of n is shown, with calls where n is already in d in parenthesis):

First the left side of the tree if traveled, then you get up the right side. Hoping it helps you see it more clearly (I know it DOES for me!).