https://cs.slides.com/colt_steele/searching-algorithms-22

Understanding Recursion: The Tale of Martin and the Dragon

Recursion is a programming concept where a function calls itself to solve smaller instances of the same problem until it reaches a base case. Here's an illustrative story:

The Story of Martin and the Dragon

Once upon a time, there was a boy named Martin who lived in a world of wizards and alchemists. Martin was an apprentice wizard in training.

One day, Martin's master gave him a task: "Go to the dragon's cave with this list of numbers and find out if any of them are odd."

When Martin reached the cave, he found an irritable dragon who refused to check the entire list.

"I'll only tell you if the FIRST number in your list is odd. That's all," growled the dragon.

Martin thought carefully and came up with a clever solution:

• First, he showed the dragon his complete list [2, 4, 6, 8, 10]Dragon: "The first number is not odd."
• Then, Martin showed a shorter list [4, 6, 8, 10]Dragon: "The first number is not odd."
• Next, an even shorter list [6, 8, 10]Dragon: "The first number is not odd."
• Then [8, 10]Dragon: "The first number is not odd."
• Then [10]Dragon: "The first number is not odd."
• Finally, Martin showed an empty list []Dragon: "That's an empty list! There's nothing there to be odd or even!"

Martin smiled triumphantly. "Since none of the first numbers were odd, and I've checked every number by making it the first number in a smaller list, I can conclude that NONE of the numbers in my original list are odd!"

The dragon nodded. "Congratulations, boy. You've discovered recursion."

What is Recursion?

Recursion is solving a problem by:

• Breaking it down into smaller versions of the same problem