In plain English, what is recursion?
What is the best way to explain "Recursion" to 8 years old kid?
I tried with the Fibonacci Series but i failed.
Well, recursion is actually pretty simple to grasp for kids. Don't try it with mathematics or whatever the other people here are suggesting. They are too young to understand it. It's too abstract and boring for them.
Instead: Show them a picture of a painter who is painting a picture of painter who is painting a picture ...
Something like this:
There are probably even better examples to be found on the web. And trust me: They'll understand it in no time.
Regardless of the question, I think any child should own a book with paintings of M. C. Escher. It'll be good for their development and creativity.
Lately I have realized that you can explain recursion to children by using food, too. Take broccoli or cauliflower for example:
These are fractal vegetables. Tear them apart and you'll find that the smaller parts will turn out to look like the big whole you once had, just smaller. This has the advantage that you can teach your child recursion while eating. Don't laugh! Children will remember it better, because it's related to their meal (and thus important to their conciousness) and they can comprehend it. A German term for "comprehend" is "begreifen", which literally means "to touch something in order to understand it". Try it yourself. It's far easier to remember something you have once touched.
When trainer calls Pokemon it's "normal" function call. If Pokemon could call himself from Pokeball that would be recursive call (Did he watch Pokemons?).
When singer, e.g. Eminem, starts calling names like - Dr. Dre, 50 cent (normal calls), Eminem (recursion).
When daddy drives the car, it's "normal call". When Bob the Builder drives himself, it's recursion.
Other suggested fractals, that's a good idea. But Logo allows you to trivially make neat fractals.
The Koch's snowflake:
to koch :level :len ifelse :level == 0 [ fd :len ] [ koch level-1 len/3 lt 60 koch level-1 len/3 rt 120 koch level-1 len/3 lt 60 koch level-1 len/3 ] end koch 5 100 rt 120 koch 5 100 rt 120 koch 5 100
Then use various "basic shapes". Koch's Snowflake is
_/\_ defined by "forward, left 60, forward, right 120, forward, left 60, forward. Others to try:
_|_ _ _| |_ /\ __| __|_ |\
...remembering to always turn at the end to face the same direction as in the beginning.
Later you may suggest including some little discrepancies, like using 59 degrees instead of 60...
Generally, Logo is awesome language to teach recursion.
Use a mathematical monster like the Julia or Mandebrot set in fractal form. This will give the kid something tangible to grasp at. Each time you reduce the problem, it looks the same, it's just smaller. The infinite mirrors example works as well as a tangible example.
I'd start with a real world example. Use something non-code related, such as matryoshka dolls as a methaphore to explain the basic approach behind recursion. (divide and conquer) then use a simple visual example side by side with the code to explain how this relates to recursion in code. The Sierpinski's Triangle as mentioned by Mihai Maruseac is a nice start. Fibonacci is a good follow up for something abstract without visuals to match. if he doesn't get fibonacci, then get him to understand the math before explaining the code. He needs to understand the algorithm before he can understand the code that will accomplish it.
Give him (her?) something he can draw, like a Koch Snowflake or one of its variations.
For formulas, give him something concrete that he can relate to, rather than just numbers. Like, number of legos in a box after applying the next step in the algorithm (which I'd advice to call something less scary, such as a turn or a step).
Oh, and avoid mentioning infinity. Prefer: and again, and again, and again... Pan it out so he's getting the impression he's playing a game.
Point is, make sure you're extremely concrete. 8-year olds can be smart, but their brain is not really equipped at that age to grasp this level of abstraction.
One extra approach that might work is to work out, with him, the algorithm that solves a tower of Hanoi, a rubics cube, or even a simple puzzle (do a simple puzzle with the picture facing the floor, and you'll quickly end up working like a computer, trying combinations one at a time).
You do not use the Fibonacci example to explain the meaning of recursion, but use it for explaining the power of use of recursion.
if you want to explain to an 8 year old recursion, use the linear series 1,2,3,4,5,..
and tell him: lets say you know the k element, and you want to know the next element, you can express things in a few ways, one of them is k1 = 1 k2 = k1 +1 k3 = k2 +1 k4 = k3 +1 k5 = k4 +1 k6 = k5 +1 l7 = l6 +1 k8 = k7 +1
then you say, well i don't want to write them all down, so i want to generalize it, and one way to do it is to say K = k + 1 target number the number we know the step to the next element.
then do it for the series -1,-2,-3,-4,...
then do it for the series 2,4,6,8,..
then ask the kid to come up with a series.
now let him think about it for a day, and after a day, show something more meaningful, and useful, like use of calculating power, and say that this is finite series that stops at element number 1 , and we calculate it backwards: 2^5 = 2^4*2 2^4 = 2^3*2 2^3 = 2^2*2 2^2 = 2^1*2 = 2*2 =4 2^3 = 4*2 = 8 2^4 = 8*2 = 16 2^5 = 16*2 = 32
now you can try Fibonacci again.
what ever you try , it will take a few days, as the mind needs to adjust to the next syntax of recursion which is not normal to any human being that does not know of it.