Recursion is simple if you’ve been programming for a while but for someone just starting, this concept might be hard to comprehend. But fear not!
Examples
I have to admit: Wikipedia is pretty good explaining this concept. Let’s start with examples:
- recursive gif:
-
GNU stands for GNU’s Not Unix VISA — Visa International Service Association
-
recursive construction:
- recursive recipe:
Recently refreshed sourdough, bubbling through fermentation: the recipe calls for some sourdough left over from the last time the same recipe was made.
- recursive googling: recursion
Probably you see some pattern there.
So… what is it?
Wikipedia with simple english shortens it to:
It is used to define a thing, such as a function or a set. A recursive definition uses the thing it is defining as part of the definition.
To expand on this: General idea behind recursion is that smaller parts are the same as bigger part. They don’t need to be exactly the same, only conceptually the same. So in recursive gif you have image inside the same image, inside the same image etc. In recursive construction you have triangle, which has smaller triangles inside, which have even smaller triangles inside. But if you enlarge smaller triangles, there is no difference between them and its ‘parent’ triangle. They are the same.
In theory, recursion can be infinite. In practice, nothing is infinite. Apart from human stupidity, as Einstein once famously said (Or did he? Actually there is no real evidence that those are his words). Back to the topic - in theory you could draw triangles inside triangles inside triangles - but it doesn’t make sense at some point. If a triangle becomes smaller than a pixel, it’s a good idea to stop.
In practice, recursion has end condition. Is destination reached? Is problem small enough to be solved? Is accuracy good enough?
Algorithms
Recursion is connected to approach to solving algorithms called ‘divide and conquer’. Divide and conquer means: if the problem is too complicated to be solved, divide it into smaller parts and then solve (conquer) those smaller parts. And so on: divide parts, then divide each part into parts until divided part can be easily solved.
Divide and conquer is nothing groundbreaking - it’s very natural for people to be afraid of big tasks. And every self-development book will tell you: start small, divide big tasks into smaller tasks that you can handle right now. There is always a smaller task - unless you finished.
What does it mean ‘smaller parts are the same as a bigger part’ in this context? It means that to define algorithm we use algorithm itself. But how can we define algorithm if it contains itself? Where is the starting point?
Algorithm example
Let’s say we want to create an algorithm to walk 1 km to our home. This is a straight route, nothing fancy. How to get there? Assuming one step is 0.5 m, then:
Just a usual thing - do 2000 steps, you will go 1 km and be at home. BUT you can also do recursive algorithm:
Sure, it seems more complicated. And for that simple case it definitely is. But what if you don’t know exact distance to home? You know how to walk and how to know if you’re there. Then you need a loop, where you repeat some action until condition is met. There are two things worth noting here:
- not entire algorithm needs to be repeated to be recursive, only the part of it (to be precise only that part is really recursive, but that’s a detail)
- there is an end condition
These are two important things that will let you see or recognize recursion in other contexts.
What about programming?
Starting with written algorithm, above examples would be:
-
non-recursive way
1. Do 1 step 2000 times -
recursive way
1. Do 1 step 2. Are you at home? If not, go to 1
In programming you can do above with usual “loop” or with real recursion. The difference? Sometimes recursion is easier. Usually it’s not, but when it is, it is much easier.
Getting to home with real-world code:
- non-recursive way
(1..2000).forEach { doStep() }- recursive way
fun doAnotherStep() {
doStep()
if (atHome()) return else doAnotherStep()
}That was really simple example. For something a bit more complex I will give example (“Fibonacci? NOOOO!”) of famous game of “Bacon Number”. With simple twist: let’s find IF you have connection with Kevin Bacon. (Answer: you have)
Ok, So you want to know if you can somehow get in touch with Kevin Bacon? With algorithmic approach you could simply write:
1. Ask your friends if they know Kevin Bacon
If anyone answers "Yes", you win!
2. Ask them to ask their friends if they know Kevin Bacon.
If anyone answers "Yes", you win!
3. Ask them to ask their friends to ask their friends if they know Kevin Bacon.
If anyone answers "Yes", you win!
4. Ask them to ask their friends to ask their friends to ask their friends if they know Kevin Bacon.
If anyone answers "Yes", you win!
...
You see problem with “usual” approach? It’s hard to write a whole algorithm, because you simply don’t know how many levels would it take to get to Kevin Bacon. And it’s always better to err on the side of caution, so you would almost always write too many levels. What if you have no idea how many levels it might take? Should you write 10 levels or 100?
You can solve this easily with recursion:
1. Get list of your friends
2. Ask THEM if they know Kevin Bacon
3. Did anyone answered "Yes"?
a) Yep, you win!
b) Nope, ask each of them for a list of their friends and with that list in mind go to 2.
As before - if ending condition is not met, we are repeating some previous action. Nothing changed here. Important thing is that “THEM” at the beginning refers to your friends, but when you go through 3b) it refers to friends of your friends.
Also, comparing to preceding algorithm, we “create levels when they are needed”. Thus we don’t have unnecessary levels and when we have, they are not cluttering our algorithm, it stays simple for 100 levels. Even for 1000 levels. (But really, maximum found Bacon Number for an actor is 12, so 1000 in this case is pretty impossible.)
To finish off these algorithms with real code:
- non-recursive way
fun hasConnectionWithBacon(yourFriends: List<Person>) : String {
yourFriends.forEach { person ->
if (person.knowsBacon()) {
return "WIN"
} else {
person.getFriends().forEach { person ->
if (person.knowsBacon()) {
return "WIN"
} else {
person.getFriends().forEach { person ->
if (person.knowsBacon()) {
return "WIN"
} else {
person.getFriends().forEach {
...
...
}
}
}
}
}
}
}
return "LOSE :("
}- recursive way
fun hasConnectionWithBacon(person: Person) : String {
if (person.knowsBacon()) {
return "WIN"
} else {
return if (person.getFriends().any { hasConnectionWithBacon(it) == "WIN" }) {
"WIN"
} else {
"LOSE :("
}
}
}As you can see, ‘normal’ approach gets dirty very quickly, whereas recursive looks easy in comparison.
This post turned out to be much longer than I expected, but hopefully this gives you better - or any at all - understanding of recursion.