Data Structures in C++ with Kristoffer Hebert

Kristoffer Hebert
Sep 1, 2018 · 3 min read

Recursion as a form of repetition

What is Recursion

Two ways to loop over a number of items is to use recursion or iteration. In C++ it is achieved via Recursive functions or traditional For loops. Computer Scientist Nell B. Dales describes recursion as “.. a function that calls itself” (Dell 400). Two types of recursive functions are direct and indirect. Recursive functions have advantages and disadvantages over iterative functions. As a result of this, recursion is not optimal solution for solving some every problem. Recursion is optimal for problems that can be split up into smaller problems, problems with unknown length, or when CPU or memory is not a constraint. Additionally, in functional languages like Haskell, iteration is only achieved through recursion.

Iterative vs Recursive Function

What are some types of Recursion

The two types of recursion are direct and indirect. Direct recursion occurs “When a function directly calls itself” (Dale 400). For example, if function xyz calls function xyz, that is direct recursion. When programming, factorial functions commonly use direct recursion to generate fractals. Indirect recursion occurs “When a chain of two or more function calls returns to the function that originated the chain” (Dale 400). If function xyz calls function zyx, and then function zyx indirectly calls xyz. Indirect recursion is used to solve splittable problems like a binary tree search. Direct and Indirect recursion has many advantages when solving algorithmic problems.

What are advantages and disadvantages of Recursive functions?

There are many advantages and disadvantages of solving problems using recursion. One advantage is that it makes code easy to understand. Writing code that solves problems with looped iterations can be verbose and hard to wrap your head around. Recursion reduces to the solution to one function that calls itself repeatedly and the loop when it needs to. One disadvantage is that recursive code, in most cases, is not as resource efficient with memory and CPU usage as normal loop code. Another disadvantage is the opportunity for infinite loops, which can be hard to debug when they happen during an edge case. Knowing the advantages and disadvantages of recursion help you understand when to use it.

When should Recursion be used?

Recursion is best used when solving a problem that has dynamic length or the length is unknown. For example, traversing a linked list or searching a binary tree for a value. Another time to use recursion, is when memory and CPU efficiency is not a factor. Recursive code is succinct and this contributes to developer happiness. Finally, Recursion can be used to to write synchronous code in asynchronous programming languages.

I used recursion to solve a resource issue, when I was writing code in Node.js. Node.js is a asynchronous, meaning it does not wait for the previous line of code to resolve before moving to the next line of code. The problem I had was migrating a large collection of articles, and downloading associated media files, from MYSQL to MongoDB. Node.js was executing all migration requests at the same and exhausting all CPU resources and crashing the process. My solution using recursion function that was using a list of requests that would synchronously processed one at a time. When the database and media files finished downloading, the function would call itself with the next item in the list. If no items existed, it would simply return nothing and end the recursive loop. The process took longer, but I was assured that all items would be processed correctly without exhausting all computing resources.

References

Dale, Nell B. C Plus Data Structures ; Third Edition. Jones and Bartlett Learning, 2003.

Kristoffer Hebert

Written by

I am working toward a simpler, more meaningful world. kristofferhebert.com

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade