Recursion

Anatomy of Recursion

Base case:

When the problem we're trying to solve is so small, we already know the answer and there's nothing left to do. We do not call the method recursively in the base case.

Recursive area of work:

1. Take care of the current value
2. Recursively call the method to solve a slightly smaller version of the same problem... may involve a "recursive leap of faith"

Performance

The stack takes up space in the computer. Recursion increases the stack space, in terms of stack frames, so this can be a downside. If you have a horribly long linked list, you can get a stack overflow in recursion.

Recursion and LinkedLists

When doing linked lists and recursion, you write your recursive methods to take in and return the nodes, not the list itself.

When dealing with lots of pointers in the code, especially when there are temps in the code, consider recursion!

Example:

A -> B -> C -> D

Find the length of a list recursively

1 + (length of the rest of the list)

Find the length of the rest of the list first - think of this as the .next part. Then, add in the base case.

int recursiveLength (Node n) {
  if (n == null) {
    return 0;
  }
  recursiveLength(n.next) + 1;
}

or, write it more broken up:

int recursiveLength (Node n) {
  if (n == null) {
    return 0;
  }
  int lengthOfThisNode = 1;
  int lengthOfTheRestOfTheNodes = recursiveLength(n.next);
  return lengthOfThisNode + lengthOfTheRestOfTheNodes;
}

Find the total sum of the nodes of a linkedlist:

int recursiveSum (Node n) {
  if (n == null) {
    return 0;
  }
  int sumOfThisNode = n.value;
  int sumOfRestOfNodes = recursiveSum (n.next)
  return sumOfThisNode + sumOfRestOfNodes'
}

or, just...

int recursiveSum (Node n) {
  if (n == null) {
    return 0;
  }
  return n.value + sum(n.next);

Resources

Code Example from Code401 Java Michelle Fereirrae

https://github.com/codefellows/seattle-java-401d6/tree/master/class-09

FrontRow video of Stepping through Recursion

Demo code based on counting the number of leaves in a tree from class 19 of Java-401d6. Java-401d6 video

My trees wiki

https://github.com/SharinaS/java-fundamentals/wiki/Trees

Code Challenge Tree Intersection

FrontRow from October 30, 2019, Code Review of TreeIntersection Code Challenge

TreeIntersection Code Challenge

Practice Whiteboarding of checking imbalanced tree

FrontRow from Nov 6th from 4-5

makeStars() lecture cookie

FrontRow from Nov 6th at 5 onward