Introduction to Recursion

Introduction to Recursion
> Click or hit Control-Enter to run Example.main above

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

public class Tree {
  Object value;
  Tree right;
  Tree left;
}

We are rarely interested in trees only for their structure. Usually we use them to structure data.

You’ll be working with binary search trees in MP5. They have rules about where elements get added.

Every subtree of a tree is, itself, a tree.

Recursion occurs when a thing is defined in terms of itself or of its type.

public class Tree {
  Object value;
  Tree right;
  Tree left;
}

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.

So far we’ve pursued iterative algorithms in this course. Recursion provides us with a new way to approach problems.

Iteration: repeat the same set of steps over and over again
Recursion: break a larger problem into smaller problems until they are small enough to solve easily

Let’s say that we wanted to count the number of nodes in the tree above.

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count iteratively:

Visit every node in the tree
Increment a counter by 1 each time

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

> Click or hit Control-Enter to run Example.main above

int factorial(int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1); // I called myself!
  }
}

We refer to a function that calls itself as a recursive function.

> Click or hit Control-Enter to run the code above

Recursion can be hard to wrap your mind around at first. But these three strategies will help.

Know when to stop. When you identify the smallest subproblem, you must return. Otherwise your program will not terminate. This is also called the base case.
Make the problem smaller in each step. If the problem doesn’t get smaller, you will never reach the base case. This is also called the recursive step.
Combine results from your recursive calls properly.

int factorial(int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1); // I called myself!
  }
}

Base case: n == 1
Recursive step: decrement n towards 1
Combine results: multiply current n with the result of the next subproblem

int factorial(int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1); // I called myself!
  }
}

You must reach the base case. Otherwise your problem will never stop, run out of memory, and crash.

How can the code above fail to reach the base case?

> Click or hit Control-Enter to run the code above

Recursive solutions can be difficult to understand.

The goal is to write clear code, not use a particular solution technique.
If an iterative solution is more clear, use that.
Sometimes a recursive solution is much more clear.
Don’t use recursion just to be cool.
Don’t use recursion because it is fewer lines of code. Who cares? Clarity is the goal, not brevity.

> Click or hit Control-Enter to run the code above

MP4 is due today at 5PM.
MP5 will be released today at 5PM.
We’ve added an anonymous feedback form to the course website. Use it to give us feedback!
My office hours continue today at 11AM in the lounge outside of Siebel 0226. I’ll need to leave at 11:30AM.

Binary Trees

Not Every Binary Tree Is A Search Tree

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Subtrees As Trees

Recursion

Recursion in Computer Science

Recursion v. Iteration

Tree Node Counting

Iterative Node Counting

Iterative Node Counting

Iterative Node Counting

Iterative Node Counting

Iterative Node Counting

Iterative Node Counting

Iterative Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Implementation

Recursive Strategies

Recursive Factorial

Reaching Base Camp

Recursion v. Iteration

Announcements