CSC 148H: INTRODUCTION TO COMPUTER SCIENCE

Old Announcements -- Week 10

Thursday 14 November: Typo in handbook

CSCA58S SECOND TERM TEST, SPRING 1996            Page 5 of 6

Question 4
(c) [10 marks]
        The second result statement should read:
        result leftCount + rightCount + 1

---

Wednesday 13 November: Assignment 3 ready

Assignment 3 is now available under the "tests and assignments page", or just click here. One small part is missing, but it should appear later today.

---

Monday 11 November: The second midterm

Click here for information about the midterm test on Wednesday.

---

Monday 11 November: Communication during recursion

Question: How does one initialize a variable within a recursive subprogram so that it is only initialized once. For example, in "frequency," I want to create a variable, "match," which will keep the total number of nodes with number values matching the input value. The problem is that every time the function calls itself, it would reinitialized it to 0.
Answer: I presume you mean something like this:

     function frequency (value : int, root : ^treeNode) : int
         var match : int := 0
         >> the rest of the function goes here ... <<
     end frequency

Variable `match' certainly would be initialized on every call to frequency, but remember that there is not just one variable called `match'. Every call to frequency has its own instance of this variable. (Look back at how we traced the factorial function in class.) And no call to frequency has access to the other instances of the variable. So recursive calls to frequency cannot contribute to the final answer by modifying a shared variable called `match'.

You are thinking the wrong way about how communication between instances of the function should work. When your frequency function calls itself with a smaller problem to solve (ie a smaller tree), the old and new instances of the function should not communicate via this answer variable. They should communicate exclusively through the function call itself -- the parameters and the returned value.

It will help if you think about the answer (that frequency should give back) in terms of answers to smaller instances of the problem. (Remember how we solved factorial the "lazy" way in class?) The questions on slides 328-331 try to lead you to think this way.