Recursion

Examples:

• List.java

• Nil.java

• Cons.java

• ListDemo.java

12.1 Recursive Thinking

Recursive definitions have:

• Base case

• Recursive step

Lists

Page 584: A list is

• a number, or

• a number comma List

But why not: A list is

• Empty, or

• Number comma List?

Factorial Function

Page 585:

• 1! = 1

• N! = N ⋅ (N − 1)! for N > 1

But why not

• 0! = 1

• N! = N ⋅ (N − 1)! for N > 0?

Base Cases

• Zero and empty are very important cases.

• We do well to make them base cases whenever possible.

Infinite Recursion

• What is it?

• How can we avoid it?

12.2 Recursive Programming

Translating a mathematical recursive definition into a recursive Java method is straightforward.

Do it for factorial:

// assumes n >= 0
public static int factorial (int n) 
{
  if (n == 0)
    return 1;
  else
    return n * factorial(n - 1);
}

How Does Recursion Work?

• Every call of the method generates a new environment.

  • Environments contain local variables including parameters.

  • Environments know where to return to.

• Environments are stacked up until reaching base case.

• Then we unstack them as method calls return.

• Demonstration: factorial(4) = …

Recursion and Iteration

• Recursion and iteration (loops) are equivalent in problem solving power.

• Tail recursion occurs when there is no further processing after the recursive call returns.

• Tail recursive methods can be properly compiled to act just like loops, without stacking up environments.

  • Common practice in functional languages.

  • Not done in Java (yet?)

• Iterative process and recursive process.

Example: Tail-Recursive Factorial

public static int factorial (int n)
{
  return factorial(n, 1);
}

private static int factorial (int n, int result)
{
  if (n == 0)
    return result;
  else
    return factorial(n - 1, n * result);
}

Demonstration

factorial(4) = …

Proper Tail Recursion

We cannot do this in Java, but we can in Haskell:

print_forever :: Int -> IO ()
print_forever n = do
  {
    print n
  ; print_forever (n + 1)
  }

Demonstration

• Start with print_forever 0; observe stack space with top.

• May need to compile this for the tail recursion optimization.

• Try equivalent method in Java?

Summary: Comparing Iteration and Recursion

1. Every iterative method is equivalent to some recursive method and vice-versa—equivalent in the sense of computing the same results.

2. We have seen how the recursive method may (or may not) be as efficient as the iterative method.

3. The recursive method may be much more elegant than the iterative method.

4. In such cases, the equivalent iterative method typically requires an explicit data structure called a stack (covered in chapter 13) to manage the stack of environments.

5. Some recursive methods are extremely inefficient (but then, so are the equivalent iterative methods).

Direct and Indirect Recursion

See Figure 12.4, p. 590.

Make this more concrete with a pair of methods:

public boolean even (int num)
public boolean odd (int num)

Also note that there is a much simpler, and faster, non-recursive (and non-iterative) solution to the even/odd problems, using % 2.

Part II: Recursion in Graphics

Sec. 12.4: Fractals

Fractals

• A fractal is a recursive geometric form; it repeats itself at different scales and rotations.

• The Koch snowflake is formed by recursively modifying the lines of an equilateral triangle:
  

• Code: Listings 12.6–12.7, KochSnowflake/KochPanel

Part III: Functional Lists

• A list is either empty, or it contains a first element, the head, and the rest of the elements are called the tail, which is also a list.

• How can we represent this in Java?
  

• In functional programs, methods behave like mathematical functions:

  • Same parameters  →  same result

  • Implies variables are really constants, no mutation of variables or objects

Functional List Class Hierarchy

Lists

• List.java

• Nil.java

• Cons.java

Using Lists

• Constructing lists

• Length of a list

• Searching in a list

• Summing a list of numbers

• Multiplying a list of numbers by a constant

• Code: ListDemo.java

References

• The functional list classes presented above are highly simplified

• The Functional Java project

• The Open Quark project

• The Haskell programming language

• CSCI C243 Introduction to Data Structures (every fall semester)

Document History

• Version 4.1, 2012 Apr 7. Added print_forever example, summary comparing iteration and recursion, and indirect recursion.

• Version 4.0, 2011 Apr 18. Added Parts II and III.

• Version 3.0, 2011 Apr 16. Initial draft for tex.m4, part I only.

• Version 2.2, 2010 April 20. Minor edit.

• Version 2.1, 2010 April 12. Converted to markdown.

• Version 2.0, 2009 April 20. Revised for 6th edition.