Many of the submissions made a poor use of recursion.  While the
output of the your code might have been correct, the use of recursion,
in some cases, was not.  We weren't testing you on the proper use of
recursion in A4, but we will be on assignment 5.

If you use recursion properly, then it will be much easier to do the
recursive family trees of assignment 5.


The following points out the problems, so that you can write better
recursive code.

I
---
The worst error is the following: using a global variable to
accumulate your results.  That's not really recursion.  In fact, NEVER
USE GLOBALS unless you have a really good reason.  If you use global
variables on assignment 5 to implement recursion, you will get a very
low mark on the correctness.  Here is an example of what I mean:

    var leaves : int := 0

    procedure recCountLeaves (root : ^nodeType)
        if root not= nil then
            if (root -> left) = nil and (root -> right) = nil then
                leaves += 1
            end if
            RecCountLeaves (root -> left)
            RecCountLeaves (root -> right)
        end if
    end RecCountLeaves

II
---
The second major problem: using a parameter and a return value to do
the same thing.  Example:

    function recCountLeaves (curr : ^nodeType, var count : int) : int

What is the purpose of this count variable?  You don't need to start
with a count variable to count leaves in a tree.  Is it passing
something back?  Then what is the return value for?  

The first thing to figure out with recursion is what information the
subprogram needs to know and what is needs to return.  That means you
have to ask yourself what parameters and return values does the
function/procedure require.  In this case, it needs a pointer to the
root of a tree, and it returns the number of leaves.  Some people got
confused here, and included an additional parameter for counting
leaves.  This is not necessary.

III
---
The rest can be classified as style problems.
Counting the leaves in a tree seems naturally to be a function.  So a
procedure, like the following, isn't as clear as a function
implementation would be.

    proc recLeaves (current : ^nodeType, var numleaves : int)


IV
----
Try to simplify the code.  Remember what the base cases are there to
do.  For example, some of the cases in the code below are not necessary
because the base case handles the 'nil' pointer.

  function recCountLeaves (root : ^nodeType) : int
      if root = nil then
          result 0
      elsif root -> left = nil and root -> right = nil then
          result 1
      elsif root -> left = nil then
          result recCountLeaves (root -> right)
      elsif root -> right = nil then
          result recCountLeaves (root -> left)
      else
          result recCountLeaves (root -> left) + recCountLeaves (root -> right)
      end if
  end recCountLeaves

V
----
Use var and non-var parameters appropriately.  Only use a var
parameter if you want to change the parameter's value in the
function/procedure.  Otherwise the code is confusing.  Make sure you
know the difference between var and non-var parameters.  (Or the
difference between pass-by-value and pass-by-reference).  For example,
in

  function recLeaves (var root : ^nodeType) : int

there is no need to have the root as a var parameter, because you
don't have to change it.