DEV Community: dennis mwangi

How to Implement Recursion in Python

dennis mwangi — Thu, 16 Feb 2023 05:32:03 +0000

Recursion is a powerful technique in computer programming that involves breaking down a problem into smaller subproblems and solving them one by one. In this article, we'll explore recursion in Python and learn how to use it to solve complex problems efficiently.

What is Recursion?

Recursion is a method of solving problems that involves breaking down a complex problem into smaller subproblems and solving them one by one. The smaller subproblems are solved in the same way as the original problem, leading to an efficient solution.

For example, consider the problem of finding the factorial of a number. The factorial of a number n is the product of all positive integers less than or equal to n. For example, the factorial of 5 is 5 x 4 x 3 x 2 x 1 = 120.

The recursive solution to this problem would involve breaking down the problem into smaller subproblems, such as finding the factorial of n - 1. The solution to the subproblem can then be used to solve the original problem.

In Python, recursion is implemented using a function that calls itself. This function must have a base case, which is the condition that stops the recursion, and a recursive case, which is the condition that continues the recursion.

How to Implement Recursion in Python

In Python, recursion is implemented using a function that calls itself. The function must have a base case, which is the condition that stops the recursion, and a recursive case, which is the condition that continues the recursion.

For example, let's implement printing the elements of a list using recursion in Python:

def print_list(lst):
    if len(lst) == 0:
        return
    print(lst[0])
    print_list(lst[1:])

list = [1, 2, 3, 4, 5]
print_list(list)

In this example, we define a function print_list that takes a list lst as an argument. The function uses an if statement to check if the length of the list is 0. If the length is 0, the function returns and the recursion stops.

Otherwise, the function prints the first element of the list and calls itself again with the slice of the list excluding the first element (lst[1:]). This continues until the length of the list is 0, and the function returns.

The result of running this code would be the elements of the list [1, 2, 3, 4, 5] printed one by one.

Examples of Recursion in Python

Here are some examples of how recursion can be used to solve problems in Python:

Calculating the Sum of a List

The problem of calculating the sum of a list of numbers can be solved using recursion. The function can be written as follows:

 def sum_list(lst):
     if len(lst) == 1:
         return lst[0]
     else:
         return lst[0] + sum_list(lst[1:])

In this example, the base case is when the length of the list is equal to 1, in which case the function returns the first item in the list. The recursive case is when the length of the list is greater than 1, in which case the function returns the first item in the list plus the sum of the rest of the list.

Factorial function using recursion in Python

 def factorial(n):
     if n == 0:
         return 1
     else:
         return n * factorial(n-1)

In this example, the base case is n == 0, where the function returns 1 without making any further recursive calls. For all other values of n, the function returns n * factorial(n-1), where factorial(n-1) is the factorial of the next smaller number.

Another example of recursion is the Fibonacci sequence, where each number in the sequence is the sum of the two preceding numbers. The Fibonacci sequence can be represented as f(n) = f(n-1) + f(n-2), where f(0) = 0 and f(1) =Python

Fibonacci sequence using recursion in Python

  def fibonacci(n):
      if n == 0:
          return 0
      elif n == 1:
          return 1
      else:
          return fibonacci(n-1) + fibonacci(n-2)

In this example, the base cases are n == 0 and n == 1, where the function returns 0 and 1, respectively, without making any further recursive calls. For all other values of n, the function returns fibonacci(n-1) + fibonacci(n-2), where fibonacci(n-1) and fibonacci(n-2) are the values of the next two smaller numbers in the sequence.

Conclusion

Recursion is a powerful technique for solving complex problems more efficiently and elegantly. It is widely used in various programming paradigms and is an important tool for computer scientists and programmers. To successfully implement recursion in Python, it is important to understand the concept of base cases and to ensure that a base case is defined to stop the recursive calls

How To Implement Linked List in Python

dennis mwangi — Thu, 16 Feb 2023 05:27:24 +0000

This is a simple guide to understanding how to implement a linked list in python.

The goal of this article is to enhance your understanding on how singly linked list is implemented in python-simplified.

A linked list is a data structure in computer science that stores a sequence of elements, called nodes, in which each node contains a reference or pointer to the next node in the list. The list is made up of a series of nodes, each of which contains a piece of data and a reference to the next node in the sequence.

Linked lists can be used to implement a variety of data structures, including stacks, queues, and associative arrays. They have several advantages over arrays, including efficient insertion and deletion operations, and the ability to easily grow or shrink the list as needed. However, they have some disadvantages as well, such as slower access time for individual elements and the need for more memory overhead to store the pointers.

There are several types of linked lists, including singly linked lists, doubly linked lists, and circular linked lists, each with its own characteristics and advantages.

How Linked List is Implemented in python

I believe the best approach to implementing a linked list in python is by using classes and objects. Here is an example:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

A node class is defined to represent each node in the linked list. This node has two attributes: data which stores the data for that node and the next which stores a reference to the next node.

Again I have another class called the Linkedlist class to represent the linked list itself. This has an attribute head that stores the reference of the first node.

kindly read the comments in the code for better understanding.

class Linkedlist:
    def __init__(self):
        self.head = None

    # this methods returns if the head is empty
    def isempty(self):
        return self.head is None

    # creating my first node
    def firstNode(self,data):
# I create an instance of the class Node(data)
        newNode = Node(data)
# Now I link the refrence of the newNode to head
        newNode.next = self.head
 # Assign head to point to newNode
        self.head = newNode

    def lastNode(self, data):
        newNode = Node(data)
# check to know if the refrence of head is empty
        if self.isempty():
# if the statement is true, then link the node to the head
            newNode.next = self.head
        else:
# otherwise create a newNode
            current = self.head
# current becomes a new instance of head
            while current is not None:
# cycle through when the condition is true
                current = current.next
# Now, i want current to point to a new address reference
            current.next = newNode
# Anytime the current variable points to a new reference, a new Node should be created.

Next, we will be looking at how to remove/pop the first node and then the last node

 def remove_firstNode(self, data):
 # check if head is empty and return Nothing
    if self.isempty():
        return None
    else:
        tmp = self.head
# tmp variable will hold the value of head
        self.head = self.head.next
# head should point to the next address so that we can pop or remove the immediate node
        return tmp

def remove_lastNode(self, data):
    if self.isempty():
        return None
    elif self.head.next is not None:
# check if head is pointing to an address
        tmp = self.head
        self.head = None
# self.head will become None and return the tmp.data value
        return tmp.data
    else:
        current = self.head
        while current.next.next is not None: 
# return true when the statement is valid
            current = current.next
        tmp = current.next
        current.next = None
        return tmp.data

That's it guys! and I hope this has enhanced your understanding of implementing a singly linked list in python. For any correction, kindly reach out to me or comment below.

Also, please do well to like and follow me here for more articles. Cheers!

Approach to testing and improving QA

dennis mwangi — Sun, 12 Feb 2023 13:25:25 +0000

1. Identify the goals of the QA system

It is important to have a clear understanding of what the QA system is intended to do and what types of questions it should be able to handle. This will help guide the development and testing of the system.

2. Develop a set of test cases

Create a diverse set of test cases that are representative of the types of questions that the QA system will encounter on the website. These test cases should cover a wide range of question types and complexity.

3. Implement the QA system

Once the test cases have been developed, implement the QA system on the website. This may involve integrating the system with the website's backend and frontend, as well as any other necessary components.

4. Evaluate the system

Use the test cases to evaluate the performance of the QA system. This can involve both human evaluation and automatic evaluation using metrics such as accuracy, speed, and the ability to handle a wide range of question types and complexity.

5. Identify and address any issues

If the system's performance does not meet the desired criteria, identify the areas that need improvement and take steps to address them. This may involve fine-tuning the model, adding additional training data, or modifying the system's architecture.

6. Continuously monitor and improve the system

To ensure that the QA system continues to perform well, it is important to regularly monitor its performance and make updates and improvements as needed. This can involve repeating the testing and improvement process on a regular basis.

When and How to use Classes?

dennis mwangi — Sat, 11 Feb 2023 06:15:54 +0000

Discussing classes in content of Pytubedata

When I started writing the initial version of Pytubedata, the primary goal in my mind was to structure the code in a way that would be easy to scale (extending functionalities) and maintain in later stages. How did I do it? Classes.

I, for a long time, didn't understand the real purpose of classes. However much I read about them, they were hard to grasp until I started using them. In this article, I will share my understanding of Classes with examples from Pytubedata.

Define the requirements
Before writing any piece of code, we should first explicitly define its functionalities and its limitations. What it will do and what it will not do, both are important. This was what I wanted Pytubedata to do-

Make an API call to public endpoints of YouTube Data API and return the response.

To make those requests it needs 4 things- base URL, endpoint, API key, and parameters.

Class and its Members
A class, as I would define it, is a blueprint that primarily holds data and functions, also called members of the class, together.

The base URL and API key are used in all requests, so it makes sense to keep them together. Creating the first class api that would hold this data together.

class api:
    def __init__(self, key):
        self.base_url = "https://youtube.com/api/v3"
        self.key = key

The init function here is a constructor. A class is a blueprint, and a blueprint is a general model to create something. You can create multiple entities using that blueprint. A constructor's job is to assign values to variables whenever a new entity is created using that class. (more on entities below)

Now left the endpoint and parameters. An API can have many endpoints and each endpoint will have different parameters. So let's create a separate class for each endpoint and store the endpoint and the parameters together.

def Channel:
    def __init__(self):
        self.endpoint = "/channels"

    def get_channel(self, id, max_results):
        params = {
            "channelId": id,
            "part": snippet,
            "maxResults": max_results
        }

        return params

Since some parameters take the user's input so we can create a function to assign the value to those parameters.

Put it all together
Now we need to define a function that will make the API calls. Since the api class holds the key and base_url for the API call, we will define a function in the same class. (Note: now the class is holding data and function that use that data together)

import requests

class api:
    def __init__(self, key):
        # data members
        self.base_url = "https://youtube.com/api/v3"
        self.key = key

    # method to make API call
    def request(self, channel_id, max_results):
        requests.request(
            method="GET",
            url=self.base_url
            params= # how do I put params here?
        )

Having all the data structured now we are ready to make an API call. But wait, how are we gonna put all this data together? Remember entities from the constructor discussion?

Those entities are called objects. Objects are essentially copies of a class and we can make as many as you want of them. So when we want to make an API call to the channel endpoint we can just create the object of Channel class.

    def request(self, channel_id, max_results):
        c = Channel(channel_id) # creating object of Channel Class
        requests.request(
            method="GET",
            url=self.base_url
            params=c.get_channel(
                        id=channel_id, 
                        max_results=max_results
                    )
            )

Now the main code

key = "123"
client = api(key=key)

client.request(channel_id="123", max_results=10)

Encapsulation
Encapsulation is what makes a class special.

It extends the holding functionality of the class with the ability to restrict access of data members and functions to the outside world using access modifiers. A motivation for this concept; someone using this code can modify the value of key or base_url by accessing them using objects which can break the code.

key = "123"
client = api(key=key)

client.key = "867" # value of key changed

There exist 3 access modifiers:

Public

Public is the default access modifier and, as the name suggests, anyone can access the public members of a class using the object
Protected

Protected members can be accessed only within the class and its child classes (You will learn about these in Inheritance)
Private

Private members cannot be accessed anywhere outside the class
To prevent malicious coders from breaking our code, in our case manipulating variables like endpoint, base_url, and api_key we can make these variables Private.

In Python, there doesn't exist the concept of access modifiers. But there is a hack to mimic the same behavior using underscore (_).

You can add two underscores before a variable, which will tell Python that those members are private and not to be given access outside the class.

import requests

class api:
    def __init__(self, key):
        # data members
        self.__base_url = "https://youtube.com/api/v3"
        self.__key = key

    # method to make API call
    def request(self, channel_id, max_results):
        requests.request(
            method="GET",
            url=self.base_url
            params= # how do I put params here?
        )

key = "123"
client = api(key=key)

client.__key = "abc"

Now this will give an error since __key is a private variable and cannot be accessed outside the class.

One shortcoming of using private variables is that now the user won't even be able to peek at the values of the private variables, which can be an issue sometimes. For eg, here one might wanna look at the value of __key and if it is assigned the right value. We can just define a Public function, that will return the value of __key , within the class.

def get_key(self):
    return self.__key

Now that you have understood encapsulation, I would like to redefine the class definition-

A class is a blueprint that primarily encapsulates data and functions, also called members of the class, together.

Let's summarize the concepts we have covered in this article-

Classes

Constructors

Objects

Encapsulation

This is the most basic functionality of classes. From here, a lot more has been added to classes but that's for another blog. Until then, check out getter and setter in Python.