Recursion is an immensely powerful tool for a programmer. Like many abstractions, it allows us see past the weeds of a problem and strive…