Recursive algorithm facts for kids

A recursive algorithm is like a special set of instructions that tells itself to repeat a task. It keeps doing the same thing, but on smaller and smaller parts of a problem. Imagine a set of Russian nesting dolls; each doll is like a smaller version of the one before it. A recursive algorithm works in a similar way, breaking a big problem into tiny, similar pieces until it reaches a very simple part it can solve directly. Then, it uses those simple solutions to build up the answer to the big problem.

What is a Recursive Algorithm?

A recursive algorithm is a way to solve problems in computer science. It's a method where a function or a procedure calls itself. This means the same set of instructions runs over and over. But each time, it works on a smaller piece of the original problem.

Think of it like a recipe that tells you to make a smaller version of the same dish. You keep making smaller versions until you get to one that's super easy to make. Then, you combine all the easy parts to finish the big dish.

How Does Recursion Work?

Every recursive algorithm has two main parts:

• Base Case: This is the stopping point. It's the simplest version of the problem that the algorithm can solve directly. Without a base case, the algorithm would run forever!
• Recursive Step: This is where the algorithm calls itself. It breaks the current problem into a smaller, similar problem. Then, it uses the same algorithm to solve that smaller problem.

The algorithm keeps calling itself with smaller problems until it hits the base case. Once the base case is solved, the results are passed back up. This builds the solution to the original, bigger problem.

Examples of Recursion

Recursion is used in many areas of computer science and even in nature.

Fractals and Trees

Look at a

Tree created using the Logo programming language and relying heavily on recursion. Each branch can be seen as a smaller version of a tree.

tree branch. Each smaller branch looks like a tiny version of the whole tree. This self-similarity is a perfect example of recursion. Computer programs can draw complex shapes like trees or fractals using recursive algorithms. They draw a main branch, then tell themselves to draw smaller branches off it, and so on.

The Tower of Hanoi Puzzle

The Tower of Hanoi is a classic puzzle that is often solved using recursion.

Towers of Hanoi

The puzzle has three rods and a number of disks of different sizes. The goal is to move all the disks from one rod to another. You can only move one disk at a time. Also, a larger disk can never be placed on top of a smaller disk.

A recursive way to solve it is:

1. Move n-1 disks from the starting rod to the helper rod.
2. Move the largest (nth) disk from the starting rod to the target rod.
3. Move the n-1 disks from the helper rod to the target rod.

This process keeps repeating for smaller sets of disks until you only need to move one disk (the base case).

Images for kids

• 

  Tree created using the Logo programming language and relying heavily on recursion. Each branch can be seen as a smaller version of a tree.

• 

  Towers of Hanoi