Recursion is a concept not a data structure or an algorithm but a way we solve a problem.
It is just a way of breaking down a problem into sub problem and each of those problems is broken into more and more sub problem until we reach the base case.
To understand recursion lets imagine we want to count the number of male children in an extended family. In a single family(Super family) there could be other families i.e children of the family have their own children
Recursion enables us to perform the same method that calculates the number of male children in a family on the children’s family
Let us see how it works
- Define a class to represent a Child with properties, sex and family
- Define a Class to represent Family with list of children as property
- Write your method as follows;
- Check if there are no longer children in the family return 0 . This implies we have gone through all the children in family. This represents the base case.
- Declare a variable to hold the number of male children in the families
- Loop through all the children in the family and check which of the child is a male child, then increment counter by one
- Check if the child has his/her own family then call the method on the family
To use our method, define a list of children in a super family. Then define a list of children for one of the child in the super family.
Please note that every recursion must have a base case i.e the stopping point, otherwise the method will continue to call itself, like an infinite loop. in our above example the base is reached when we have a family without any children, in this case the children is null.
In conclusion, understanding how recursion works is a vital step towards understanding algorithms, become a better problem solver and ultimately a better programmer.