Section 8 - Introduction to Recursion
-Recursion is a powerful, but possibly hazardous, means of iteration - without loops!
-We use the nature of function calling to do the repetition for us
-makes for short code (usually) but can be
VERY costly in terms of time/efficiency
-When a program executes, a pointer keeps track of which line is being executed
-when a function is called, a marker is set at the point of the call, and the instructions for the function are placed "on the stack" (of previous instructions)
-The function's instructions are then executed, and when the function is over, execution returns to the point where the function was called (where the marker was set)
-We know that a function can call another function, but what if a function calls itself???
-given a file of test scores, process them to find the average, and also to count the number of scores above the average
-this requires us to process the scores twice: once to sum and find the average, and once again to compare each number to the average
-recursion provides a way for us to do this
without storing the numbers in an array!
//global variables for simplicity of example
sum = 0.0;
count = 0;
cout << "file didn't open!\n";
ProcessOneNumber(); //initial call to recursive function
//recursion is now finished- here are results:
cout << "number of scores processed: " << n << endl;
cout << "sum of scores: " << sum << endl;
cout << "average of scores: " << mean << endl;
cout << "number of scores above average: "
<< count << endl;
infile >> x;
sum += x;
ProcessOneNumber(); //RECURSIVE CALL!!
if (x > mean)
mean = sum / n;
[see hand trace diagram]
-in this example, we processed the scores once, going "down" the recursive tree, and then we processed each one again, as we "popped" back from each call
-Recursion allows us to "store" the values in each instantiation of the function call
-we use the stack to "store" the
number, instead of an array
(The "anchor" is the case where the
recursive call is NOT made)
-without following these two guidelines, you will continue to make recursive calls, putting more and more functions on the stack, until you literally run out of "stack space" and the program crashes!
-the use of stack space and repeated function
calls is why recursion can be very inefficient
-printing the binary value of a decimal number
-again, we will do work "on the way down", and then do something else "on the way up"
[see hand trace]
void Convert(int num);
cout << "enter a # to convert: \n";
cin >> num;
cout << "\nDo another?\n";
cin >> ans;
while (ans == 'y');
void Convert(int num)
temp = num /2;
rem = num % 2;
if (temp > 0)
cout << rem;