These past few weeks, in my limited spare time, I’ve been working on a basic algorithm to teach myself about basic recursion. The problem at hand is as follows:
Given the matrix of infinitely many fractions of the form (positive integer) / (positive integer) , count the number of fractions preceding the fraction entered by a user. If a duplicate fraction is found, such as (2/2) , (6/8) , etc. , it is not to add to the count of preceding fractions. Finally, this program must be done with recursion.
Having never worked with recursion before, I did my research and grasped a basic understanding of the core concepts. I started designing my algorithm. To begin, I created a visual matrix and simplified the specifications of iteration through the matrix: (1/1) -> (1/2) -> (2/1) -> (3/1) -> (2/2) -> (1/3) -> (1/4) and soforth. I figured out the iteration sequence relatively quickly. It’s a simple problem of even versus odd and testing whether or not the numerator or denominator are 1.
The next issue was testing whether a fraction was a duplicate or not, without referencing memory. To accomplish this, I figured out an algorithm I later found out to be the Greatest Common Factor algorithm and implemented it so that, given any numerator and denominator, it could return a boolean value depending on if the fraction was able to be reduced.
Having the bulk of the code taken care of, I moved onto the recursive method. Here, it was a simple case of induction: a base case that would break the recursion, and if the base case was not met, the function would call itself, initializing the iteration and adding to the count, assuming the fraction was not a duplicate.
Finally having polished my code to my satisfaction and after running a few debug tests with far too many print lines, I tested my code on a medium scale with the goal fraction set to (25/26) and to my disappointment received the “maximum recursion depth exceeded while calling a Python object” error. After reading up on the issue a bit, I discovered that Python is not meant for tail recursive problems. Even though the algorithm was functional, the language did not support efficient tail recursive functionality.
With that step out of the way, I think I’m going to read up on some recursive-friendly languages and try implementing my code in another one.
In all, it was an interesting challenge for sure. I dove head-first into issues I’d never encountered before and, even though I’m not quite finished yet, I can say that I am definitely on the right track.