Recursion Explained in One Minute

Check out all articles in Technical Article Structure on Medium

The recursion discussed in this article is Tail Recursive or Linear Recursion, which could be written in iteration. This article covers:

• What is Recursion in Programming
• Tradeoffs of Recursion
• Implementation Steps
• Reference

What Is Recursion

Recursion is a function that keeps calling itself with a smaller input until a base case is met

• Base case is when the function stops calling itself
• Recursive case is when the function calls itself with a smaller input

When comparing to iteration, recursion delivers the same outcome but in a more elegant and simple implementation. However, iteration might have better performance in terms of speed.

Tradeoffs of Recursion

Pros

• Bridges the gap between elegance and complexity
• Reduce the need for complex loops and auxiliary data structures
• Can reduce time complexity easily with memoization (I’ll write another article to explain what is memoization)
• Works really well with recursive structures like trees and graphs

Cons

• Slowness due to CPU overhead
• Can lead to out of memory errors or stack overflow exceptions
• Can be unnecessary complex if poorly constructed

Implementation Steps

1. Determine the base case to avoid infinite loop
2. Do something so that the input works toward the base case
3. Call it self using the outcome from step 2 as function input. This step is recursive case

Reference

YouTube — Recursion in Programming — Full Course

FreeCodeCamp — How Recursion Works — Explained with Flowcharts and a Video