By Matthys September 2, 2020 In Uncategorized

Recursive Functions

What is Recursive Functions?

As defined on techterms.com, a recursive function that calls itself during its execution.

The theory of recursive functions was developed by the 20th-century Norwegian Thoralf Albert Skolem, with the first noticeable implementation in computer science being developed by Allan Turing in his definition of computational reduction with his described “Degrees of Insolvability” forming the first computational hierarchies.

These hierarchies represent the different iterations we can today identify in our recursive functions.

When should we use Recursive Functions?

Hierarchies, Networks, or Graphs
Multiple Related Decisions
Explicit Recursive Relationships

I believe that recursive functions are an implementation of functions that is avoided because of an under appreciation of its capabilities and because the unexperienced programmer may find the logic behind the correct implementation quite daunting.

I also believe that with more exposure to the topic of recursive functions the more confidence programmers may have to use it.

Pros and Cons

Pros
  • Recursion can reduce time complexity. When implemented correctly.
  • Recursion adds clarity and (can) reduce the time needed to write and debug code.
  • Recursion is better at tree traversal.
Cons
  • Recursion uses more memory.
  • Recursion can be slow. If not implemented correctly.

My Experiment

For this experiment I decided to compare the processing speed of two sorting methods.
The first being a sorting method based on recursion with best practices.
And the second being the basic iterative method known as bubble sort.

Lists of various lengths containing randomized integers is generated and then passed into the two methods on turn, with a timer starting on the method execution and stopping once the values is returned in order.

Recursive Sort

Bubble Sort

As shown the iterative sort out preforms the Recursive up to 100 data points. But from there the Recursive leads, and increases the lead exponentially.

Conclusion

With higher exposure to recursion as developer, I believe, we can develop faster programs, improve our logical reasoning capability and provide higher quality end products. As proven in the experiment above

Recursive Functions (Recursion) dates to the very beginning of the modern computer.
And while newer, more popular, and widely taught methods is commonly used, recursion is still a highly effective tool, outperforming many of the newer methods, if implemented correctly.
Recursion is best used in navigating tree like structures and computations that uses hierarchies.

“The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

– Niklaus Wirth, Algorithms + Data Structures = Programs, 1976

References