For further actions, you may consider blocking this person and/or reporting abuse
Read next
Revolutionary Differential Transformer Boosts AI Performance with Focused Attention Mechanism
Mike Young -
Create a Stunning Light/Dark Mode Toggle in 5 Minutes 🎨✨
WEBDEVTALES -
Supercharging LLM Testing: TICK Lets You Check the Boxes
Mike Young -
Selective Attention Boosts Transformer Performance on Language Tasks
Mike Young -
Top comments (14)
A lot of great recursion explanations here:
Explain Recursion Like I'm Five
Sloan ・ Oct 7 '18 ・ 1 min read
😄
StackOverflowError
I was about to do that :P
Epic. :-D
Do you know Matryoshka dolls?
When you open a doll, you find another doll inside, and when you open that one, there's another one inside. The act of doing this is called recursion. Let's write code for that.
Recursion is a way of doing an operation over a set of values, where each value is related to the previous one, without iterating or using loops.
Imagine you go to open a room, but the room is locked. You have someone come up to you with a box and they tell you that the key to the room is in there. But inside the box is many other boxes, that also contain boxes and you don't know which box contains the key. So you need an algorithm to find the key!
Imagine you want to pan-fry some fish, but you have a huge fish and not so large a pan. Write down the steps to cut the fish so it fits in the pan.
Fish-Cutting-Steps:
Done😆
Let's say you want to add up a bunch of numbers. You have the numbers on a stack of index cards, one number on each card. Somebody asked you to add them up and tell them the result. That sounds like a lot of work. I mean, come on, adding a couple numbers is fine, but there are probably like 50 numbers in this deck of cards. So you hatch a plan...
You keep the top card, and you hand the rest to your classmate and ask them to add up rest of the cards. You don't tell them that this was supposed to be your job.
Your classmate says fine, but then realizes there must be like 49 cards in this deck, which sounds like a lot, I mean come on? So they hatch a plan. They keep one card for themselves and ask somebody else to add up the rest of the cards...
And so on down the line (fortunately your school is pretty overcrowded and you have a lot of classmates) until somebody is handed just one card and asked to add "them" up.
"What do you mean add 'them' up, it's just one card."
"But what do they add up to?"
Okay whatever, so the last person just says the number on the card.
The second-to-last person takes that number and adds it to the card they kept, and tells it to the person who asked them.
The third-to-last person takes the number that the second-to-last person tells them and adds it to the number on the card they kept, and so on back up the line....
You get the number that the second person tells you and add it to the one card you kept. Easy peasy lemon squeezy! Then you tell the person who asked you.
In code, this would look something like:
One problem is that this destroys the deck. We could have each person give the card back when they say the result (
deck.push(mycard)
), but in code it's cleaner to just pass a slice of the rest of the deck:fantastic example!
To begin, if you want to understand recursion, you must understand what is recursion.
This explain pretty much the concept of recursion. :D
In the programming world, you can find recursive algorithms, such as sorting ones, and you can guess they aren't looping on themselves infinitely, we always add a return condition to be sure we won't have an infinite loop.
FYI we don't do infinite recursive function because it would pollute the "call stack". This stack keeps track of which function was called, and from where it was called, to be able to get back there when we'll met a
return
statement.Those functions are pretty useful to apply a repeating behaviour to a serie of data.
For example :
(actually this function isn't working as intended, it was created only to show you the concept of recursion)
In order to understand recursion, one must first understand recursion.
Another good one can be found on "The C Programming Language" (Kernighan and Ritchie). If you look up the word "recursion" in the index, you'll find that they have listed page 269 as one of the reference pages. Page 269 happens to be the page of the index containing the word recursion.
Play Tower of Hanoi using stacking rings every toddler probably has in their play bin. That is how I really really understood recursion when I first learned it couple decades ago and it blew my mind :)