# Thread: Need help with understanding a recursion function

1. ## Need help with understanding a recursion function

Code:
```void dohanoi(int N, int from, int to, int using)
{
if (N > 0)
{
dohanoi(N-1, from, using, to);                //1
printf ("move %d --> %d\n", from, to);  //2
dohanoi(N-1, using, to, from);               //3
}
}

dohanoi(4, 1, 3, 2);```
I know most have you have seen this Towers of Hanoi recursive function before so hopefully someone'll be able to shed some light in how it works.

When dohanoi() is called how does it all exactly work? I'm so lost. What happens when n=1 for example. I know that "1 --> 3" is printed but I'm exactly sure why?

How is it that anything even happens when n=1? I mean, the first line of the if statement is to call
Code:
`dohanoi(N-1, from, using, to);`
. Shouldn't it go back to the top with the function now being
Code:
`dohanoi(0, 1, 2, 3)`
? And then nothing happen? Why does //2 happen?

I would love it if someone could break down what's going on for n=1 and maybe n=2 and n=3 too.

I've looked at a factorial recursion example and it was quite simple understand, but this Tower one just isn't making sense to me. I think part of it is that it's a void function and secondly that there are multiple things under the if statement. I think I'm making more difficult than it is, but I just transferred schools and am frustrated to see that my previous school left me under prepared for this semester's courses. I'm feeling a bit overwhelmed.

2. for n== 0 function checks if conditions and does nothing

for n == 1 function calls
itself for n == 0 (which does nothing)
moves 1 piece from "from" bar to "to" bar (notifying user with printf)

and calls itself for n==0 once again, which again does nothing

So summurizing

n==0 - do nothing
n == 1 - move circle "from" --> "to"
n==2 - could you investigate yourself?

3. Thanks for the quick response. I think that it's making a bit more sense.

So for n=1 the if statement triggers, the function calls itself for 0, the if statement DOESN'T trigger. Then the print statement executes. Then that second function call happens but why is it for 0 again, with nothing happening.

I must be missing something still because I'm still confused for n=2. Let's see:
function calls for 2
if statement occurs
function calls for 1
does it then go to the print statement to the print statement?
and then do the second function call for 1 again?

I imagine the output would be:
1 --> 2
1 --> 3
2 -->3

I can picture it in my head but I don't see how it happens with the dohanoi()..

4. Thanks for that link. I don't have the time to check it out right this second but I'm gonna look over it tonight or tomorrow morning. From the glance I had of it, it looks like exactly what I need, but I'll be back if I have further questions.

Thanks again

5. Ok. I've got a pretty decent understanding of recursion itself now and am now working on my Tower program Everything's working well but I'd like to spice up my output a bit. Currently my output looks like this:

1 ==> 3
1 ==> 2
2==> 3
etc.

But I really wanna add a counter to count the current move so that my output can be something like this

Move 1 1 ==> 3
Move 2 1 ==> 2
Move 3 2==> 3
etc.

I've tried adding a counter in a couple of different places but it never seems to increment so my out is always

Move 1 1 ==> 3
Move 1 1 ==> 2
Move 1 2==> 3
etc.

I've been looking on the web for the past few hours for any type of example to help me out but I just can't seem to find anything

6. Nevermind. Global or static variable, duh

7. Originally Posted by CS_Student8337
Nevermind. Global or static variable, duh
Or, perhaps just pass in another variable (as a pointer, perhaps, so that you can update the same value from all levels).

--
Mats