we use this in college because our program is Information Systems. i still do not get it.
In: Other
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