Today we’ll look at an useful technique in programming called “recursion” to help solve algorithmic problems.
Recursion refers to a function calling itself within its own definition, typically with different input values.
It generates a recursion like a loop and stop until its condition is no longer fulfilled.
Let's look at an example:
class Solution(object):
def combineLists(self, a, b):
if a and b:
if a.val > b.val:
a, b = b, a
a.next = self.combineLists(a.next, b)
return a or b
▲ The code snippet here is trying to combine two sorted linked lists.
class Solution(object):▲ class Solution() defines a class called Solution which inherits the functionalities from the base class object.
def combineLists(self, a, b):▲ def combineLists() defines a function named combineLists() with 3 parameters: self, a, b.
self is the reference to the instance of class Solution, you can call it what ever you like but self is usually the convention.
It allows you to call combineLists() inside class Solution itself, which will be explained in details later.
a and b are the input data required by combineLists(), which is sorted linked lists 1 and 2.
if a and b:▲ The if condition checks if both lists a and b are non-empty.
If either one of the lists a or b is empty, it'll skip the code under the if condition and directly return the non-empty list.
If both lists a and b are empty, it also skips the code under if condition and directly return non-empty list "".
if a.val > b.val:
a, b = b, a▲ If lists a and b are not empty, there'll be another if condition checks if the value of the current nodes in list a is larger than b's.
If the condition is true, it executes the line "a, b = b, a" to exchange the value of the current nodes in list a and b.
It makes sure the smaller value is always be a node and in front of the larger value to sort the list.
a.next = self.combineLists(a.next, b)▲ Then is the most critical part of the code where the recursion takes place.
self.combineLists() means the class Solution calls the function combineLists() in itself.
This time it sets the input value be a.next and b, so that every time it'll compare the value of current node of a and b and sort them.
After that it'll assign the 2 sorted nodes into a.next at each recursion until either of the lists is empty.
Note that the input value is a.next instead of a because list a is used to store the merged sorted list in this program, thus the input value will be the next a node.
return a or b▲ After either of the lists is empty, it finally returns linked list a or b.
It'll usually return a if the inputed lists a and b are not empty at the start of the program.
▼ You can test the program using this example input and see the expected outcome:
Input: a = [1,2,4], b = [1,3,4]
Output: [1,1,2,3,4,4]Well done on finishing this tutorial!
Remember, the key to progress lies in continuous practice, as it is through repetition that you will witness remarkable improvement.
See you in Python (2)!
© 2023 Harmony Pang. All rights reserved.
Comments