Using Recursion and a Python Class

00:00 Using Recursion and a Python Class. Your first approach to generating the Fibonacci sequence will use a Python class and recursion. An advantage of using a class over the memoized recursive function you saw earlier is that a class keeps state and behavior together within the same object.

00:20 This is known as encapsulation. In the function example, cache is a completely separate object, so you don’t have control over it. On-screen, you can see the code that implements a class-based solution.

00:36 Line 3 defines the Fibonacci class. Line 4 defines the class initializer, .__init__(). It’s a special method that you can use to initialize your class instances.

00:48 Special methods are sometimes referred to as dunder methods, short for double-underscore (__) methods. Line 5 creates the .cache instance attribute, which means that whenever you create a Fibonacci object, there will be a cache for it.

01:02 This attribute initially contains the first numbers in the Fibonacci sequence. Line 7 defines another special method, .__call__(). This method turns the instances of Fibonacci into callable objects. Lines 9 to 12 validate the value of n by using a conditional statement.

01:22 If n is not a positive integer, then the method raises a ValueError.

01:38 Line 15 defines a conditional statement to check the Fibonacci numbers that were already calculated and are present in the cache. If the number index n is already in the cache, then line 16 returns it.

01:53 Otherwise, line 19 computes the number, and line 20 appends it to the cache so you don’t have to compute it again. Finally, line 22 returns the requested Fibonacci number.

02:11 To try this code, go ahead and save it into fibonacci_class.py. Then run this code in your interactive shell in the same directory. Here you create and then call an instance of that Fibonacci class named fibonacci_of.

02:32 The first call uses 5 as an argument and returns 5, which is the sixth Fibonacci number because you’re using zero-based indices.

02:48 This implementation of the Fibonacci sequence algorithm is quite efficient. Once you have an instance of the class, the .cache attribute holds the already-computed numbers from call to call.

03:00 In the next section of the course, you’ll take a deeper dive to visualize what happens when calling this recursive algorithm to get a better understanding of recursion and how memoization makes the algorithm more efficient.