In this blog, I would like to introduce the concepts that I believe are the most powerful in programming languages, and mastering them will give you solid programming thinking. I will explain them one by one with examples in Java and Python. After introducing the object-oriented concept in the first article, I will explain the recursion concept in this article.
1. Object-oriented
2. Recursion
3. Concurrency
4. Functional Programming and Lambda Expressions
5. Data Structure
6. Software Design Patterns
7. Annotations/Decorators
8. Machine Learning
1. What is Recursion?
Recursion is the characteristic of a process, algorithm, or function to call itself in its definition. It is a powerful technique to solve problems with similar structures. That means you break down the problem into chunks of similar sub-problems and apply the same solution to each of them iteratively until you reach the base case, which is solved immediately.
It’s a strong concept that a developer should master to write solid and short programs. It strengthens code reusability and allows you to think in an abstract and high-level way. It helps detect patterns by observing systems and extracting similar sub-problems.
Recursion is a powerful technique in tree traversal algorithms and graph data structures. It is also used in some search or sorting algorithms. However, recursion can lead to an infinite loop or out-of-memory issues if you don’t program it correctly.
A recursive function or algorithm usually follows the subsequent steps:
- Define the base case: This is the simplest form of the problem and is solved without recursion. It plays the role of stopping the recursion.
- Define the recursive case: This is the case where you break down the problem into small sub-problems of the same nature.
When implementing a recursive function, you should consider the following:
- Invoke the recursive function: You have to determine exactly where to reference the function or algorithm in its definition to solve the entire problem.
- Combine the result if necessary: Combine the results you get from each recursive call if solving the problem requires it.
Let’s explain recursion and the above steps with the help of a famous mathematical example, namely the factorial function:
factorial(n):
if n == 0:
return 1
else:
return n * factorial(n – 1)
Factorial is a function defined only for positive integers (i.e. n>=0). The base case in the factorial function is when ‘n’ is equal to 0. It is mathematically proven that the factorial of 0 is 1 and does not require any recursion for its calculation. Now let’s define the recursive case. We know that the factorial of ‘n’ is calculated using the formula:
n! = n * (n-1) * (n-2) * .. * 1 or simply n! = n * (n-1)!
In other words, the factorial of ‘n’ is the result of multiplying ‘n’ and the factorial of ‘(n-1)’. Thus, the cases ‘n’ and ‘(n-1)’ can be calculated similarly.
2. Example of Recursion in Java
Java supports recursion and provides the necessary built-in syntax to implement it. In this section, we will show how Java implements recursion using two examples.
2.1. Example 1
A small imperative code to implement the factorial function can look like this:
public static int factorial(int n) throws Exception {
if (n<0) throw new Exception("Factorial cannot be calculated for a negative number: " + n);
if (n==0) return 1;
return n*factorial(n-1);
}
If the argument ‘n’ of the function whose factorial we want to calculate is negative, we raise an exception with a message. If the number is equal to 0, the function returns 0, which stops the iteration. Otherwise, the function returns the expression ‘n*factorial(n-1)’, which consists of the number itself multiplied by the factorial of ‘(n-1)’. For a demo, you can call this function for the number 5 and -8:
public static void main(String[] args) {
try {
System.out.println("fact 5: " + factorial(5));
System.out.println("fact 6: " + factorial(-8));
} catch (Exception e) {
e.printStackTrace();
}
}
That will return the following result:
fact 5: 120
java.lang.Exception: Factorial cannot be calculated for a negative number: -8
at recursive.app.Factorial.factorial(Factorial.java:30)
at recursive.app.Factorial.main(Factorial.java:23)
2.2. Example 2
Let’s assume that each apprentice has completed a series of training courses. Each schooling has two dates, a start and an end. To do this, we create a ‘Schooling’ class as follows:
import java.time.LocalDate;
import java.util.Objects;
public class Schooling {
private Integer id;
private String name;
private Integer apprenticeId;
private LocalDate start;
private LocalDate end;
public Schooling(Integer id, String name, Integer apprenticeId, LocalDate start, LocalDate end) {
this.id = id;
this.name = name;
this.apprenticeId = apprenticeId;
this.start = start;
this.end = end;
}
public Integer getId() {
return id;
}
public String getName() {
return name;
}
public Integer getApprenticeId() {
return apprenticeId;
}
public LocalDate getStart() {
return start;
}
public LocalDate getEnd() {
return end;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Schooling schooling = (Schooling) o;
return Objects.equals(id, schooling.id)
&& Objects.equals(apprenticeId, schooling.apprenticeId);
}
@Override
public int hashCode() {
return Objects.hash(id, name, apprenticeId, start, end);
}
}
Let’s create some data:
public static List<Schooling> init() {
List<Schooling> detailedSchooling = new ArrayList<>();
detailedSchooling.add(new Schooling(100, "Java", 500,
LocalDate.parse("2023-08-14"), LocalDate.parse("2023-08-27")));
detailedSchooling.add(new Schooling(101, "Python", 500,
LocalDate.parse("2023-08-28"), LocalDate.parse("2023-09-17")));
detailedSchooling.add(new Schooling(102, "JS", 500,
LocalDate.parse("2023-09-18"), LocalDate.parse("2023-10-01")));
detailedSchooling.add(new Schooling(103, "Scrum", 500,
LocalDate.parse("2023-10-08"), LocalDate.parse("2023-10-22")));
detailedSchooling.add(new Schooling(100, "Java", 501,
LocalDate.parse("2023-08-14"), LocalDate.parse("2023-08-27")));
detailedSchooling.add(new Schooling(101, "Python", 500,
LocalDate.parse("2023-08-28"), LocalDate.parse("2023-09-17")));
return detailedSchooling;
}
We notice in these data that the apprentice with ‘id=500’ started new schooling after the end of another. We want to merge two courses into a single object when the last course succeeds the first. In other words, the start date of one instance occurs one day after the end date of another course. If we analyze the problem, we figure out that it is naturally recursive.
We take two objects from a list, compare them and when they can be merged, we delete them from this list to add instead the merged object to the list. Then, we repeat the same operation for the obtained list.
We cannot merge two instances of ‘schooling’ class and store the result in one. Additionally, only dates count for us, regardless of the type of school. So we create a new class with ‘apprentice id’, ‘start’, and ‘end’ as fields:
import java.time.LocalDate;
import java.util.Objects;
public class ApprenticeSchooling {
private Integer apprenticeId;
private LocalDate start;
private LocalDate end;
public ApprenticeSchooling(Integer apprenticeId, LocalDate start, LocalDate end) {
this.apprenticeId = apprenticeId;
this.start = start;
this.end = end;
}
public Integer getApprenticeId() {
return apprenticeId;
}
public LocalDate getStart() {
return start;
}
public LocalDate getEnd() {
return end;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
ApprenticeSchooling that = (ApprenticeSchooling) o;
return Objects.equals(apprenticeId, that.apprenticeId) && Objects.equals(start, that.start) && Objects.equals(end, that.end);
}
@Override
public int hashCode() {
return Objects.hash(apprenticeId, start, end);
}
}
public static void main(String[] args) {
List<Schooling> detailedSchooling = init();
List<ApprenticeSchooling> appSchooling = detailedSchooling.stream()
.map(s->new ApprenticeSchooling(s.getApprenticeId(), s.getStart(), s.getEnd()))
.collect(Collectors.toList());
List<ApprenticeSchooling> mergedSchooling =
mergeSchoolingByDate(appSchooling).stream()
.sorted(Comparator.comparing(ApprenticeSchooling::getApprenticeId)
.thenComparing(ApprenticeSchooling::getStart))
.collect(Collectors.toList());
for (ApprenticeSchooling s: mergedSchooling){
System.out.println(" Schooling: " + s.getApprenticeId() + " >> "
+ s.getStart() + " >> " + s.getEnd());
}
}
After creating some data and saving them in the list ‘detailedSchooling’, we convert them to instances of class ‘ApprenticeSchooling’ by using ‘map’ in the statement to retain only the properties we need: ‘apprentice Id’, ‘start’ and ‘end’:
List<ApprenticeSchooling> appSchooling = detailedSchooling.stream().map(s→
new ApprenticeSchooling(s.getApprenticeId(), s.getStart(), s.getEnd()))
.collect(Collectors.toList());
To merge the instances, we call the ‘mergeSchoolingByDate’ method, which we define as follows:
public static List<ApprenticeSchooling>
mergeSchoolingByDate(List<ApprenticeSchooling> appSchooling) {
for (ApprenticeSchooling a: appSchooling){
for (ApprenticeSchooling b: appSchooling){
ApprenticeSchooling ab = mergeSchooling(a, b);
if (ab!=null){
appSchooling = removechooling(appSchooling, a);
appSchooling = removechooling(appSchooling, b);
appSchooling.add(ab);
return mergeSchoolingByDate(appSchooling);
}
}
}
return appSchooling;
}
We take two instances from the list that contains all instances of the ‘ApprenticeSchooling’ class and then compare them individually. If we find a match, we remove these two instances from the list and add the result of their merge to the list. We call the function again with the updated list to repeat the same process until no more merge is found. Finally, when there is no merge possible, in the last statement we return the list.
3. Example of Recursion in Python
It’s easy to implement recursive functions in Python. Consider directory tree traversal, which is a naturally recursive problem. We want to list all the sub-folders and files in a folder. To do this, we import the ‘os’ module to define a function we name ‘get_directory_content’.
import os
def get_directory_content(direct, n):
for elem in os.listdir(direct):
elem_path = os.path.join(direct, elem)
if os.path.isfile(elem_path):
print(f'{n*ws}File: {elem_path}')
elif os.path.isdir(elem_path):
print(f'{n*ws}Directory: {elem_path}')
get_directory_content(elem_path, n+1)
ws = ' '
get_directory_content("C:\\", 0)
In the code for this function, we use the ‘listdir’ function in the ‘os’ module to retrieve all direct sub-directories and files inside the ‘direct’ directory. The second parameter ‘n’ is just a number that indicates which directory level we are at.
We iterate over the obtained list and get the full path for each ‘elem’ element in that list by joining the ‘direct’ directory to the element itself to get ‘elem_path’ the element’s absolute path (or the full name). Next, we check if the element is a file to display it.
We note that ‘ws’ is a global variable holding a whitespace. The expression {n*ws} prints ‘n’ spaces. That allows directory paths to be printed as a tree. If ‘elem_path’ is a directory, we print it out and then recursively call the function for that sub-directory with ‘n+1’ as a second parameter. At some point, we reach sub-folders that only contain files and the recursion ends.
No comments:
Post a Comment