we use this in college because our program is Information Systems. i still do not get it.
In: Other
Iterative: you call a function multiple times in a loop.
Recursion: you call a function once and the function calls it self until its finished.
In very general terms, think of it as building up to a solution versus working your way down to one.
The classic example in programming for recursion is the factorial function. A! = A x (A-1) x (A-2) x … x 1.
An iterative solution would start with one and work up. X factorial is 1, times 2, times 3… up to X. “Do the multiplying thing X times” is the iteration.
A recursive solution starts from the top and works down to an end-case. Here, it’s 1! = 1. So what is X factorial? It’s X times (X-1) factorial. What’s (X-1) factorial? It’s (X-1) times (X-2) factorial… until you get to 1. “Call this same function with one less than before” is the recursion.
When you’re *iterating* through something, you’re going through a loop until some condition is met. You see this with loops like:
for(int i = 0; i < 10; i++)
or
while(true)
or
while(isFinished == false)
or
List<string> strings;
foreach(string s in strings)
If you’re doing any of the .net languages, you’ll also see something like an IIterable interface that defines what you need to make something iterable. Essentially, it’s just looping through elements of some collection, or checking against a certain condition before running again.
Recursion is a little different. Recursion is when something calls itself.
A good example of that would be traversing a directory. You could set up a function to copy all files in a given folder and then move to the first folder in that folder, and you’d call the original function on that folder too.
So something like:
public void traverseDirectory(string path){
//TODO: copy files from this folder to another folder
foreach(string d in Directory.GetDirectories(path)){
traverseDirectory(d);
}
}
As you can see, you’re both iterating there (that foreach loop), but also doing recursion, because traverseDirectory is calling itself.
Think of **iteration** and **recursion** like solving a problem in two different ways.
**Iteration** is like following a set of steps repeatedly. Imagine counting from 1 to 10 by writing the numbers one by one in a list. You keep going until you reach 10. This is iteration—repeating a process over and over until you’re done.
**Recursion** is when you break a big problem into smaller versions of itself. Imagine asking someone else to count to 10, but they stop at 9 and ask another person to count from 1 to 9, and so on. In recursion, a problem solves itself by making smaller versions of the same problem until reaching a simple, base case (like 1 in this example).
So, iteration is like doing the job step-by-step yourself, while recursion is like dividing the task into smaller chunks and letting each chunk solve itself.
Recursion means you call the function inside that function and resolve it from the back, since you don’t have a value until resolving the last function call, which will end in a value.
Calls like this could look like:
int factorial(int number) {
if (number > 1) {
return number * factorial(number – 1);
} else {
return 1;
}
}
Iterative this would look like:
int factorial(int number) {
int factorial = 1;
while(number > 0) {
factorial = factorial*number;
number–;
}
return factorial;
}
Both functions do the factorial (in math it would be number!).
So for example: 5! = 5*4*3*2*1 = 120
Recursion will do in order 1*2*3*4*5 = 120 and the iteration will do 5*4*3*2*1 = 120.
As you can see, the iterative approach has an iteration (like the name suggests) using a while loop. The recursion example will use “it’s own” until you reach the end up in a value and then goes from bottom up and resolves the stack to evaluate the result.
Let’s say you have 7 identical robots, a table, a piece of paper, and seven markers. You ask them to draw a rainbow.
ITERATIVE
Robot 1 picks up a red marker, puts the paper on the table and draws an arc. They put the pen down and they leave.
Robot 2 picks up an orange marker, puts the paper on the table and draws another arc. They put the pen down and they leave.
Repeat for all 7 robots until the rainbow is finished.
RECURSIVE
Robot 1 picks up the red marker, hands the paper to Robot 2 and waits.
Robot 2 takes the paper, picks up the orange pen, hands the paper to Robot 3, and waits.
The process repeats until you get to Robot 7.
Robot 7 recieves the paper from Robot 6, picks up the violet pen, draws an arc, then hands the paper back to robot 6.
Robot 6 gets the paper back from Robot 7, uses the indigo pen they are already holding, draws an arc, then hands the paper back to Robot 5.
The process repeats until Robot 2 hands the paper back to Robot 1, who draws a red arc, and finishes the rainbow.
In both cases the end result is the same, the difference is how you got there.
So why use recursion instead of iteration? Because some algorithms are easier to write in code as recursive than iterative. And vice versa. Recursive algorithms take advantage of how computers operate, by placing function calls and their results on a stack, while iterative algorithms require the programmer to manage more directly how each step repeats.
At the end of the day there is no functional difference, you can replace any recursive function with an iterative one, though it’s not always easy to do so.
Recursion is where code calls itself to do a job. What’s important is that, when the new copy ends and returns control, it hasn’t arbitraily trashed any state information the top level copy was keeping. It’s like calling any other subroutine – except that the one it calls is itself, with new parameters.
**A classic “recursion” problem is the [Tower of Hanoi puzzle](https://en.wikipedia.org/wiki/Tower_of_Hanoi).**
Three rods hold disks of different sizes that can slide on and off the top. They all start stacked on a single one of the rods, in order of size, smallest at the top. A bit like a kid’s stacking toy, but with the extra rods.
The puzzle is to move the stack from that rod to another one. But you can only move them according to the following three rules:
1: You can only move one disk at a time, from one rod to another
2: You can only move the top disk in a stack
3: You may not move a larger disk onto a smaller one.
It’s worth trying it for yourself – but the recursive solution goes as follows.
Let’s say we have 8 disks (call them 1-8, top down – so 1 is smallest, 8 is largest). And call the rods A, B and C (say). the stack starts on rod A. Your task is to move it to rod B.
Now – to move the stack 1-8 from A to B, you obviously need to move the bottom disk (8) there, then build the rest up on top of it. But 8 is the biggest disk, so the only way you can do that is if ALL the other disks are out of the way – so first you need to move the stack of disks 1-7 to rod C. Then you can move disk 8 to B. Then you need to move the stack 1-7 from C to B.
To move the stack 1-7 anywhere, you need to move the stack 1-6 out the way, move disk 7, then move the stack 1-6 again.
And so on. The only exception is “move a stack of 1” – that’s just move disk 1.
So you could write a piece of code to move a stack of a given size (*n*, say) from a given rod (the “first” rod) to another given one (the “second” rod), using the remaining one (the “third rod”) as required, as follows:
If *n* is 1 (a stack of 1 disk) it should just move disk 1 from the first rod to the second rod.
For any other value, it should:
* call itself, with suitable parameters, to move a stack of size *n-1* from the first rod to the third rod
* move disk *n* to the second rod
* call itself again, with suitable parameters, to move a stack of size *n-1* from the third rod to the second rod
* return control to the next level up
You’ll need to make sure that each time the code is called, it knows the correct “first”, “second” and “third” rods. And that when it calls itself, the new copy doesn’t mess that up (hopefully the coding language will handle that) – because it’s going to hand control back to the copy that called it. The last copy to end will be the one that was called initially.
Trying coding it, by all means. The code that you end up with is surprisingly short. But add suitable output and kick it off, and the whole puzzle will solve itself correctly as if by magic.
Latest Answers