How can a function execute an action after recursing?

I know that recursion is a technique to call a function within the function itself. but the below code confuses me on how it is able to do the cout part after the first recursion:

(This code solves the tower of hanoi puzzle)

#include <iostream>
using namespace std;

void move_rings(int n, int src, int dest, int other); 

int main(void) 
{
    int rings;                      
    cout << "Number of Rings: ";   
    cin >> rings;
    move_rings(rings, 1, 3, 2);   

    system("PAUSE");
}

void move_rings(int rings, int source, int destination, int other)
{
     if (rings == 1)
     {
        cout << "Move from " << source << " to " << destination << endl;
     }
     else    
     {
         move_rings(rings - 1, source, other, destination);
         cout << "Move from " << source << " to " << destination << endl;
         move_rings(rings - 1, other, destination, source);  
     }
}

As you can see, the function move_rings calls itself after the if statement.

When I开发者_如何学编程 visualize this, I see a never ending loop... How is it possible for this function to do the

cout << "Move from " << source << " to " << destination << endl; 

part?

The output of the program is this:

Move from 1 to 3
Move from 1 to 2
Move from 3 to 2
Move from 1 to 3
Move from 2 to 1
Move from 2 to 3
Move from 1 to 3

Recursion can be a bit tough to grasp at first. It "clicked" for me when I thought about it like this: you have a base case, which is the condition that will lead the recursive function not to call itself anymore, and then you have the other part ("else" in your code), where the function will continue to be called. The "rings == 1" condition is your base case.

The function "move_rings" gets called with a smaller argument each time. In each subsequent call, the variable "rings" gets smaller (and therefore "moves closer" to the base case), until "rings == 1" is true, and then the function stops calling itself.

Hope that helps.

Because every time move_rings() is called, its first argument is smaller. Eventually, assuming a non-infinite number of rings, the function will be called on only one ring. That's the terminating condition that causes the recursion to return.

Picture it like a binary tree structure. Assuming a non-infinite number of nodes, you will eventually reach a leaf node beyond which there are no more. Then you can begin traversing back up the stack along with the other code paths which found leaf nodes.

Because in each call to move_rings it passes the parameter rings - 1. In the end, the passed parameter will be 1 and rings == 1 will be true.

When dealing with recursively (or any kind of reentrant) functions, it is important to understand how local variables work. Each invocation of a function has it's own incarnation of the local variables and the parameters. Envision a stack (like one of the piles in the tower of Hanoi) of bricks. Each brick contains the function parameters. When a function is called, the parameters for that one is placed on top of the stack and the function is executed, using the topmost brick's values. When the function returns, the topmost brick is discarded, returning to the values of the brick below.

Every time the function recurses, the it gets a ring count decremented by 1. Eventually, all branches reach the rings==1 state and terminate. You can imagine this as a binary tree with its branches in the else state and its leaves in the if state.

In the else branch, the call is done with rings - 1. As you never increase it, eventually rings will be 1 and the if branch will be hit. As no recursion occurs in this branch, the method terminates.

Each time you call the move_rings function, number of rings is decremented by one. Eventually, number of rings will be 1. This code, however, could indeed produce an endless loop, because it is not well written. Number of rings is never checked to be greater than 1. So if number of rings entered in the main function is less than 1, the condition to stop recursion will never be reached.

When move_rings calls move_rings, the second call of the function starts completely fresh. It has a completely separate set of variables. It is just as if move_rings called any other function. It just happens to be calling "another function" that has the same name and contains the same logic.

In the second call of the function, rings will have a lower value, because the first call passed a smaller value for that parameter than its own. Eventually, on one of these recursive calls, the value will reach 1, and the if test at the beginning of the function will test true. This avoids further recursion, and that function returns. The immediately previous call of the function then resumes from where it was, just as if it had called any other function. It does its print, and then makes another recursive call where something similar happens, and then completes. And so on all the way "back up".