# Recursive Tracing

## Table of contents

## Recursion

Throughout the course so far, we’ve seen that the choice of **data abstraction** affects how we solve programming problems. For example, we learned about certain templates for solving list problems, stack problems, queue problems: each of which required us to engage differently with how we organize code to manipulate data in a program.

For the remaining half of the course, we’ll study an equivalent paradigm shift in the context of **functional abstraction**. Earlier, we presented a narrow definition of functional abstraction focusing on the relationship between client and implementer.

The

`Balance`

class defines public methods so that other programs written by anyone, anywhere, at anytime before or after it can rely on its functionality as long as they know how to interface with it.

A more general definition for functional abstraction considers all **algorithms** as having three parts.

- All algorithms take parameters as input.
- All algorithms perform computation with the given parameters.
- All algorithms return results based on the computations.

**Recursive algorithms** represent a style of solving problems by combining solutions to smaller subproblems.

- Recursive algorithms take parameters as input.
- Recursive algorithms perform computation with the given parameters.
- Identify smaller
**subproblems**that can be solved independently. - Solve each smaller subproblem with
**recursive calls**. - Combine the result of each subproblem to compute the complete result.

- Identify smaller
- Recursive algorithms return results based on the computations.

## Language Generator

It turns out that humans use recursion in everyday English. English grammar allow syntactic recursion with phrases embedded within phrases.^{1} (In the following examples, brackets denote recursive structure.)

- Conjunction
- [[John and Mary] and Bill]
- Clausal complements
- [John thinks that [Mary said that [the girl cried]]]
- Possessives
- [[[[John]’s mother]’s brother]’s house]
- [the house of [the brother of [the mother of [John]]]]

In syntactocentric linguistics, **recursive syntax** (embedding phrases within phrases) has been hypothesized to be the critical feature of human language capacity. Although this claim has been challenged in recent decades, generating understandable human language remains a key challenge for computer programming given the infinite expressiveness of human language. Can we define a program to generate all possible English sentences?

## Language Generator

- Oct 26
**Recursive Programming**- BJP 12.3, 12.4

- Apply the three-step outline to define programs with a single recursive call.
- Define recursive programs by passing parameters to a private helper method.

- Oct 27
**Section****Recursive Programming**- Oct 28
**Structural Recursion**- Define public/private paired recursive programs to traverse linked nodes.
- Apply the
`x = change(x)`

pattern to recursively change linked node references.

- Oct 29
**Section****Structural Recursion**- Oct 30
**Generative Recursion**- Trace the execution of programs with more than one recursive call.
- Define generative recursive programs that create new data on each recursive call.

Recursive algorithms present one direct approach for answering this question. But before we try to tackle that question, we’ll study recursive algorithms for problems that we already know how to solve in order to build a foundation for answering these bigger questions in the future.

Edward Gibson. 9.59J Lab in Psycholinguistics. Spring 2017. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA. ↩

## Recursive cases

Say we want to implement `writeStars`

, a method that takes an integer `n`

and prints out `n`

asterisks `*`

followed by a new line. We can solve this by defining an iterative algorithm.

```
// pre : n >= 0
// post: Prints a line containing the given number of stars
public static void writeStars(int n) {
for (int i = 0; i < n; i++) {
System.out.print("*");
}
System.out.println();
}
```

In order to solve the `writeStars`

problem using recursion, we’ll temporarily disallow ourselves from using iteration. (This is not a general rule. Many recursive algorithms use recursion together with iteration to solve problems.)

One way to solve this problem without using any loops is to write out every possible case using `if`

statements. But this gets tedious very quickly. How do we even cover all possible values of `n`

?

```
public static void writeStars(int n) {
if (n == 0) {
System.out.println();
} else if (n == 1) {
System.out.print("*");
System.out.println();
} else if (n == 2) {
System.out.print("*");
System.out.print("*");
System.out.println();
} else if (n == 3) {
System.out.print("*");
System.out.print("*");
System.out.print("*");
System.out.println();
} ...
}
```

This is where recursion can help. Notice the `n == 3`

case contains the same code from `n == 2`

but with an extra asterisk at the beginning. We can factor-out the repeated code and call the `n == 2`

case with `writeStars(2)`

.

```
public static void writeStars(int n) {
if (n == 0) {
System.out.println();
} else if (n == 1) {
System.out.print("*");
System.out.println();
} else if (n == 2) {
System.out.print("*");
System.out.print("*");
System.out.println();
} else if (n == 3) {
System.out.print("*");
writeStars(2);
} ...
}
```

Notice the `n == 2`

case also contains the same code as the `n == 1`

case! And the `n == 1`

case also contains the same code as the `n == 0`

case!

```
public static void writeStars(int n) {
if (n == 0) {
System.out.println();
} else if (n == 1) {
System.out.print("*");
writeStars(0);
} else if (n == 2) {
System.out.print("*");
writeStars(1);
} else if (n == 3) {
System.out.print("*");
writeStars(2);
} ...
}
```

## What are the steps for evaluating writeStars(3)?

- Call
`writeStars(3)`

, use the`n == 3`

case. - Print
`*`

. - Call
`writeStars(2)`

, use the`n == 2`

case. - Print
`*`

. - Call
`writeStars(1)`

, use the`n == 1`

case. - Print
`*`

. - Call
`writeStars(0)`

, use the`n == 0`

case. - Print a new line.

More generally, every case except for `n == 0`

can be rewritten with two statements.

```
public static void writeStars(int n) {
if (n == 0) {
// Base case
System.out.println();
} else {
// Recursive case
System.out.print("*");
writeStars(n - 1);
}
}
```

## What are the steps for evaluating writeStars(3)?

- Call
`writeStars(3)`

, use the`n >= 1`

case. - Print
`*`

. - Call
`writeStars(2)`

, use the`n >= 1`

case. - Print
`*`

. - Call
`writeStars(1)`

, use the`n >= 1`

case. - Print
`*`

. - Call
`writeStars(0)`

, use the`n == 0`

case. - Print a new line.

This recursive program has two parts: a **base case** and a **recursive case**.

- Base case
- A simple input that is computed directly.
- Recursive case
- A complex input that is computed with recursive calls to smaller subproblems.