Logout

D.4.4

Trace recursive algorithms.

Teaching Note:

All steps and calls must be shown clearly.

LINK Connecting computational thinking and program design.

Sample Question - FORMER CURRICULUM - Not so much tracing, but a good overall recursive question.:

Given a program which functions like a linked list and has a recursive count method (HL 2 May 2008, question 1):

(e) State the name of the programming technique used in the countUp method used
in the List class. [1 mark]

To use this method the following statement is used.
output(list.count());

(f) State the sequence of steps that flow from executing the above statement and
state clearly how the count method stops executing. [4 marks]

Sample Question - FORMER CURRICULUM:

Consider the following recursive algorithm.

```  int recur(int b)
{ if (b==0)        return 1;
else
return 2*recur(b-1);
}```

(a) State two features of a recursive algorithm. [2 marks]
(b) State the value returned if the method is called by recur(3). [2 marks]

JSR Notes:

### Recursion Exercises

These come from a textbook I used to use teaching AP CS, by Leon Schramm. Above is an image of the tracing exercise m4.

And here is a video showing how to do the tracing exercise m5 below:

The idea is that when the first instance of the recursive method is called, the if condition is not true, so the method goes to the else block, in which another instance of the method is called. We show that in the trace table above as the call of m4(6, 7) is 7 + m4(5, 7). But we don't know what m4(5.7) is, since the "a" variable is still not 0. So another call to the m4 method is required, and so on, until, finally variable "a" is indeed 0, from which point we can work on up through the "stacked" calls.

```  public int m1(int n)                  // m1(6)
{
if (n == 1)
return 25;
else
return n + m1(n-1);
}

public int m2(int n)                 // m2(5)
{
if (n == 5)
return 0;
else
return n + m2(n+1);
}

public int m3(int n)                  // m3(6)
{
if (n == 1)
return 1;
else
return n * m3(n-1);
}

public int m4(int a, int b)                 // m4(6,7)
{
if (a == 0)
return 0;
else
return b + m4(a-1,b);
}

public int m5(int a, int b)                 //  m5(5,3)
{
if (a == 0)
return 1;
else
return b * m5(a-1,b);
}

public int m6(int a, int b)                 // m6(3,5)
{
if (b == 0)
return 1;
else
return a * m6(a,b-1);
}

public int m7(int a, int b)                 // m7(7,3)
{
if (a < b)
return 5;
else
return b + m7(a-1,b+1);
}

public int m8(int n)                 // m8(6)
{
if (n == 1 || n == 0)
return 0;
else
return n + m8(n-1) + m8(n-2);      //So this will require branching tracing
}
```

### Further Recursion Examples from the Morelli Textbook

Make sure you look at both of these examples, and the hints for understanding them in-between. Hints for understanding and following both of these, above and below:

- The difference between the two methods is mainly because of the order in which the printing out of the letter and the recursive call are made.

- In the diagram, each lower block is the instance of the method that was called in the block above.

- A method is not finished until you get to (in the diagram) its final semi-colon.

- In recursion, the methods that call other methods recursively are not out of memory until those that it called are finished; they are placed on a stack of unfinished methods.

- It is the interruption of the recursive calls which is the secret to how things work.

- In the code, recall that the charAt() method of the String class prints out the character at a certain element number. So for the String "hello world", charAt(7) would print return 'w'. 