Question about recursion
-
Hello, I am trying to understand recursion by using the following example.
#include #include using namespace std; unsigned long factorial( unsigned long ); // function prototype //------------------------------------------------------------------------- int main() { // Loop 4 times. During each iteration, calculate factorial( i ) and display result. for ( int i = 0; i <= 4; i++ ) { cout << "\n i = " << i << endl; cout << endl << setw( 2 ) << i << "! = " << factorial( i ) << endl; } return 0; // indicates successful termination } // end main //------------------------------------------------------------------------- // recursive definition of function factorial unsigned long factorial( unsigned long number ) { // base case if ( number <= 1 ) { return 1; } // recursive step else { cout << endl << "number = " << number << " factorial(number - 1) = " << factorial(number - 1) << " number * factorial(number - 1) = " << number * factorial( number - 1 ) << endl; return number * factorial( number - 1 ); } } // end function factorial //------------------------------------------------------------------------- /* output: i = 0 0! = 1 i = 1 1! = 1 i = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 2! = 2 i = 3 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 3! = 6 i = 4 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 4 factorial(number - 1) = 6 number * factorial(number - 1) = 24 number = 2 factorial(number - 1) = -
Hello, I am trying to understand recursion by using the following example.
#include #include using namespace std; unsigned long factorial( unsigned long ); // function prototype //------------------------------------------------------------------------- int main() { // Loop 4 times. During each iteration, calculate factorial( i ) and display result. for ( int i = 0; i <= 4; i++ ) { cout << "\n i = " << i << endl; cout << endl << setw( 2 ) << i << "! = " << factorial( i ) << endl; } return 0; // indicates successful termination } // end main //------------------------------------------------------------------------- // recursive definition of function factorial unsigned long factorial( unsigned long number ) { // base case if ( number <= 1 ) { return 1; } // recursive step else { cout << endl << "number = " << number << " factorial(number - 1) = " << factorial(number - 1) << " number * factorial(number - 1) = " << number * factorial( number - 1 ) << endl; return number * factorial( number - 1 ); } } // end function factorial //------------------------------------------------------------------------- /* output: i = 0 0! = 1 i = 1 1! = 1 i = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 2! = 2 i = 3 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 3! = 6 i = 4 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 4 factorial(number - 1) = 6 number * factorial(number - 1) = 24 number = 2 factorial(number - 1) =The recursive calls have to complete before the output can be sent to
cout. So what you're seeing is the output from the deepest recursive call first. --Mike-- Visual C++ MVP :cool: LINKS~! Ericahist | NEW!! PimpFish | CP SearchBar v3.0 | C++ Forum FAQ -
The recursive calls have to complete before the output can be sent to
cout. So what you're seeing is the output from the deepest recursive call first. --Mike-- Visual C++ MVP :cool: LINKS~! Ericahist | NEW!! PimpFish | CP SearchBar v3.0 | C++ Forum FAQHasn't the output already been sent to cout? The program already output 2! = 2 and i = 3. At the point in the program where i = 3 is output, doesn't that signify the beginning of a new iteration? Thanks, Eric
-
Hasn't the output already been sent to cout? The program already output 2! = 2 and i = 3. At the point in the program where i = 3 is output, doesn't that signify the beginning of a new iteration? Thanks, Eric
OK, I still don't get it. I changed the code a little to make the invocations easier to see.
#include #include using namespace std; unsigned long factorial( unsigned long ); // function prototype //------------------------------------------------------------------------- int count = 0; int main() { // Loop 2 times. During each iteration, calculate factorial( i ) and display result. for ( int i = 0; i <= 2; i++ ) { cout << "\n i = " << i << endl; cout << endl << setw( 2 ) << i << "! = " << factorial( i ) << endl; cout << endl << "--------------------------------------------" << endl; } return 0; // indicates successful termination } // end main //------------------------------------------------------------------------- // recursive definition of function factorial unsigned long factorial( unsigned long number ) { count++; cout << endl << "factorial was invoked for the " << count << " time " << " number = " << number << endl; // base case if ( number <= 1 ) { cout << endl << "number <= 1" << endl; return 1; } // recursive step else { cout << endl << "number = " << number << " factorial(number - 1) = " << factorial(number - 1) << " " << number << " * " << factorial( number - 1 ) << " = " << number * factorial( number - 1 ) << endl; return number * factorial( number - 1 ); } } // end function factorial //-------------------------------------------------------------------------OUTPUT:i = 0 factorial was invoked for the 1 time number = 0 number <= 1 0! = 1 -------------------------------------------- i = 1 factorial was invoked for the 2 time number = 1 number <= 1 1! = 1 -------------------------------------------- i = 2 factorial was invoked for the 3 time number = 2 factorial was invoked for the 4 time number = 1 number <= 1 factorial was invoked for the 5 time number = 1 number <= 1 factorial was invoked for the 6 time number = 1 number <= 1 number = 2 factorial(number - 1) = 1 2 * 1 = 2 factorial was invoked for the 7 time number = 1 number <= 1 2! = 2 -------------------------------------------- Press any key to continue */Please walk me through the following:i = 2 factorial was invoked for the 3 time number = 2 factorial was invoked for th -
Hello, I am trying to understand recursion by using the following example.
#include #include using namespace std; unsigned long factorial( unsigned long ); // function prototype //------------------------------------------------------------------------- int main() { // Loop 4 times. During each iteration, calculate factorial( i ) and display result. for ( int i = 0; i <= 4; i++ ) { cout << "\n i = " << i << endl; cout << endl << setw( 2 ) << i << "! = " << factorial( i ) << endl; } return 0; // indicates successful termination } // end main //------------------------------------------------------------------------- // recursive definition of function factorial unsigned long factorial( unsigned long number ) { // base case if ( number <= 1 ) { return 1; } // recursive step else { cout << endl << "number = " << number << " factorial(number - 1) = " << factorial(number - 1) << " number * factorial(number - 1) = " << number * factorial( number - 1 ) << endl; return number * factorial( number - 1 ); } } // end function factorial //------------------------------------------------------------------------- /* output: i = 0 0! = 1 i = 1 1! = 1 i = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 2! = 2 i = 3 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 3! = 6 i = 4 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 4 factorial(number - 1) = 6 number * factorial(number - 1) = 24 number = 2 factorial(number - 1) =It appears that you are calling
factorial()three times within itself (one for the algorithm itself, and two for thecoutstatements). With all of thosecoutstatements, that may be leading to the confusion.
"The greatest good you can do for another is not just to share your riches but to reveal to him his own." - Benjamin Disraeli
-
Hello, I am trying to understand recursion by using the following example.
#include #include using namespace std; unsigned long factorial( unsigned long ); // function prototype //------------------------------------------------------------------------- int main() { // Loop 4 times. During each iteration, calculate factorial( i ) and display result. for ( int i = 0; i <= 4; i++ ) { cout << "\n i = " << i << endl; cout << endl << setw( 2 ) << i << "! = " << factorial( i ) << endl; } return 0; // indicates successful termination } // end main //------------------------------------------------------------------------- // recursive definition of function factorial unsigned long factorial( unsigned long number ) { // base case if ( number <= 1 ) { return 1; } // recursive step else { cout << endl << "number = " << number << " factorial(number - 1) = " << factorial(number - 1) << " number * factorial(number - 1) = " << number * factorial( number - 1 ) << endl; return number * factorial( number - 1 ); } } // end function factorial //------------------------------------------------------------------------- /* output: i = 0 0! = 1 i = 1 1! = 1 i = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 2! = 2 i = 3 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 3! = 6 i = 4 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 4 factorial(number - 1) = 6 number * factorial(number - 1) = 24 number = 2 factorial(number - 1) =If you are trying to track the stages of recursion with the cout line then I suggest that you minimise your confusion by calling your recursive function just ONCE and storing the result to use in your cout line and to return, I think that this will you help dissect what is going on? Good luck I´m sure it will just click and you will go "Ah!":)
-
Hello, I am trying to understand recursion by using the following example.
#include #include using namespace std; unsigned long factorial( unsigned long ); // function prototype //------------------------------------------------------------------------- int main() { // Loop 4 times. During each iteration, calculate factorial( i ) and display result. for ( int i = 0; i <= 4; i++ ) { cout << "\n i = " << i << endl; cout << endl << setw( 2 ) << i << "! = " << factorial( i ) << endl; } return 0; // indicates successful termination } // end main //------------------------------------------------------------------------- // recursive definition of function factorial unsigned long factorial( unsigned long number ) { // base case if ( number <= 1 ) { return 1; } // recursive step else { cout << endl << "number = " << number << " factorial(number - 1) = " << factorial(number - 1) << " number * factorial(number - 1) = " << number * factorial( number - 1 ) << endl; return number * factorial( number - 1 ); } } // end function factorial //------------------------------------------------------------------------- /* output: i = 0 0! = 1 i = 1 1! = 1 i = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 2! = 2 i = 3 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 3! = 6 i = 4 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 3 factorial(number - 1) = 2 number * factorial(number - 1) = 6 number = 2 factorial(number - 1) = 1 number * factorial(number - 1) = 2 number = 4 factorial(number - 1) = 6 number * factorial(number - 1) = 24 number = 2 factorial(number - 1) =OK, thanks to all of the great feedback, I have a better understanding about recursion. I am now attempting to apply it and I have come across a problem that I can't seem to pinpoint. I have written the "eight queens" program, but for some reason, I get an infinite loop. I think my base case is ok. Can someone help me figure out what I am doing wrong here? Thanks in advance, Eric
#include using namespace std; const int BOARD_SIZE = 8; // function prototypes void fillBoard( int [], int, int ); bool noConflict( int [], int, int ); void printBoard( int [], int ); //-------------------------------------------------------------- // main method int main() { int chessboard[ BOARD_SIZE ]; // represents a chessboard with 8 rows (0-7) int column = 0; int count = 0; // keeps track of the count fillBoard( chessboard, column, count ); // invokes fillBoard function to start filling the chessboard return 0; // indicates sucessful termination } // end main method //-------------------------------------------------------------- // fillBoard method void fillBoard( int board[ BOARD_SIZE ], int c, int cnt ) { for( int r = 0; r <= 7; r ++ ) // for every row on the board { board[ c ] = r; // assign the value of row to the column if( noConflict( board, r, c ) ) // if there is not a conflicting queen { if( c == 7 ) // if it is the last column { printBoard( board, cnt); // output the board } else { fillBoard( board, c + 1, cnt ); // else recursively invoke fillBoard for the next column } } } } // end fillBoard method //-------------------------------------------------------------- // noConflict method bool noConflict( int board[ BOARD_SIZE ], int r, int c ) { for( int col = c - 1; col >= 0; col-- ) // for each column on the board { if( board[ col ] == r // checks horizontally to the left || board[ col ] == r + c - col // checks diagonally moving down and to the left || board[ col ] == r + col - c ) // checks diagonally moving up and to the left { return false; // there is a conflict } else { return true; // there is not a conflict } } return true; // there is not a conflict } // end noConflict method //------------------------------------------------------------- // printBoard method void printBoard( int board [ BOARD_SIZE ], int cnt ) { cout << "Count = " << ++cnt << endl; // output the count for( int r