Section 8 - Introduction to Recursion

[INCOMPLETE…..]

-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???

That's recursion!!

Example-

-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!

#include <iostream.h>

#include <fstream.h>

#include <stdlib.h>

//function prototype

void ProcessOneNumber(void);

//global variables for simplicity of example

double

sum, mean;

int

n,count;

fstream

infile;

int main(void)

{

sum = 0.0;

count = 0;

infile.open("rec.dat", ios::in||ios::nocreate);

if (infile.fail())

{

cout << "file didn't open!\n";

exit(-1);

}

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;

return 0;

}//end main

//function definition:

void ProcessOneNumber(void)

{

int

x;

if (!infile.eof())

{

infile >> x;

sum += x;

n++;

ProcessOneNumber(); //RECURSIVE CALL!!

if (x > mean)

count++;

}//end if

else

mean = sum / n;

}//end function


[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

In General:

  1. Make the recursive call inside some conditional structure, so that there is an option where it won't be called (see above)
  2. Make sure each recursive call works toward the condition that doesn't recurse (as in the above example, when reading numbers brought us closer to the eof, and the else statement)

(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

another example:

-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]

#include <iostream.h>

//function prototype:

void Convert(int num);

int main(void)

{

int

num;

char

ans;

do

{

cout << "enter a # to convert: \n";

cin >> num;

Convert(num);

cout << "\nDo another?\n";

cin >> ans;

}

while (ans == 'y');

return 0;

}//end main

//function definition:

void Convert(int num)

{

int

temp,rem;

temp = num /2;

rem = num % 2;

if (temp > 0)

Convert(temp);

cout << rem;

}//end function