Lecture notes for 09/02/97 o stacks and recursion 1 handout o C++ classes * C++ basics part II (rearranging order of material from what's in course guide a bit.) * Should read: Chap 2, 3 and 7.7 * Course notes available on web page. ============================================================================ Last time, we discussed a recursive program for checking to see if parens are matched in some input. Today: talk about how recursion is actually implemented in the computer. HOW FUNCTION CALLS AND RECURSION ARE IMPLEMENTED ------------------------------------------------ 2 part of memory: stack and free-store (also called "heap" but don't want to confuse with other kind of heap). Dynamic memory from free store. (e.g., when you use "new"). Local variables from stack. What's a stack? A stack is a way of storing data with two basic operations: push and pop. Think of it as a stack of plates. Pushing something onto the stack is like putting a new plate on top. Popping the top of the stack is like taking the top plate off. Called a "LIFO" access pattern: "last in (is the) first out". The computer uses a "call stack" to implements function calls and recursion. Let's use the example of matching parentheses. // match parens. int find_match(char left) { char c; for(c = read_to_next(); is_left(c); c = read_to_next()) { if (find_match(c) == 0) return 0; } /* c is a right marker */ return is_match(left, c); } int main(void) { int *arr = new int[10]; // just putting in this arr[5] = 42; // to demonstrate stack vs. freestore if (find_match(START)) cout << "OK\n"; else cout << "doesn't match\n"; cout << arr[5] << endl; return 0; } Run it on ...(...[...]...)...{...}... When you call a function in C++, it makes space in "call stack" for arguments and local variables, in what's called a "frame". +------------------------------ | main(void) | arr: | | ------ +------------------------------ Now, step through. Allocate space in the free-store. Then call find_match. So, create a new frame for find_match. find_match has 1 argument plus 1 local variable c. These are stored on the stack, along with a pointer to where in the code it was called from, so we know where to go when it's done (a couple more things are stored too, like a frame ptr, and there's space for the return value). Then find_match calls read_to_next(). +--------------------------------- | main(void)| fm(START) | rtn() | arr: | c: | ... | <----- | ->line 5 | ->line 14 +-------------------------------- Read-to-next returns '('. Then call "is_left('(')" which returns 1. Now we call find_match('('). +--------------------------------- | main(void)| fm(START) | fm('(') | arr: | c: | c: | <----- | ->line 5 | ->line 15 +-------------------------------- Now what: read_next returns '[' which is a left delimeter, so we call find_match on it. So, now what does the stack look like? +------------------------------------------------ | main(void)| fm(START) | fm('(') | fm('[') | arr: | c: | c: | c: | <----- | ->line 5 | ->line 15 | ->line 15 +----------------------------------------------- This reads up to ']' which is not left. So, returns 1. Now back in previous find_match. Go back through for loop and read in ')'. This is not left and does match the argument, so it returns 1. Now, we're back in originial fm. Read to '{'. +--------------------------------- | main(void)| fm(START) | fm('{') | arr: | c: | c: | <----- | ->line 5 | ->line 15 +-------------------------------- This reads to '}'. Then returns 1. Then read_to_next hits end-of-file and returns END. This is not a left marker, and does match so this returns 1. Finally back in main, and we're done. That's how function calls and recursion are implemented. One thing to notice about this. When a function returns, we pop the stack - so these local vars disappear. That's why you CANT RETURN ADDRESS OF LOCAL VARIABLE. E.g., imagine int *create_new_array() { int arr[100]; return arr; } This doesn't work because the space pointed to by "arr" will be overwritten next time we have a function call. ========================================================================== One way to match parentheses without recursion is to build our own stack. In C++, we would do this by building a Stack class. Let's see how we would do this: review notion of a Class + discuss idea of "data abstraction" First: Idea of "data abstraction" is you want to separate interface from the implementation of some way of storing and examining data. E.g., notion of "Stack" is a "data abstraction" (also called an Abstract Data Type). It specifies operations you can perform (push, pop,...) without specifying how it is implemented. E.g., view like this: +-----+ push----| | pop-----| | empty?--| | +-----+ Might implement in several ways, e.g., with arrays or linked lists, but user shouldn't have to know. Classes in C++ give us a way of doing that: separating interface from implementation. Let's write a class for a Stack of chars. Class definition goes in a header file, like stack.h // A Stack of chars. class Stack { public: // interface. Doesn't require knowing actual implementation Stack(); // constructor (initializer) void push (char c); // push c onto stack. char pop(void); // pop top of stack. Return 0 if already empty. int is_empty(void); // is it empty? private: static const int MAX_SIZE=1000; // max depth. Like a #define but internal char array[MAX_SIZE]; int counter; // how much in stack right now. }; Idea is (once we write these routines) we can say: Stack s,t; s.push('a'); s.push('b'); t.push('z'); cout << s.pop(); cout << t.pop(); cout << s.pop(); Let's write the member functions. These would be in a file stack.C. Start with: #include "stack.h" First function is "constructor". Think of as "initializer". It's job is to initialize the local variables. Stack::Stack(void) { counter = 0; } //push. Let's say we exit if it's full. void Stack::push(char c) { assert(counter < MAX_SIZE); // quit if full. #include array[counter] = c; ++counter; } char Stack::pop(void) { if (counter == 0) return '\0'; --counter; return array[counter]; } int Stack::is_empty(void) { return (counter == 0); } Now, suppose we say: Stack *p; p = new Stack; // allocate space for stack on free store. // calls constructor to initialize. p->push('a'); delete p; // free up storage. Say we have a main routine in main.C that uses stacks. E.g., #include #include "stack.h" int main(void) { Stack s; .... } main.C needs to include the stack.h header file. We use <...> for standard libraries, and "..." for headers in the current directory. Say we want to compile. Could do it like this: g++ -g main.C stack.C -o myprog (Don't need to specify .h files since they're already included. "-g" means to compile with debugging info. "-o" tells where output should go to). Say we change main.C a little. To recomplile we do it again. Really shouldn't need to compile stack.C again since we didn't change it. That's the idea behind Makefiles. Talk in more detail about makefiles later.