Meta Topics

Software Technology: Tail recursion

Programming
  1. Transition to Processing
  2. Primitive Operations
  3. Algorithms
  4. Variables
  5. Debugging in Processing
  6. Conditions
  7. Loops
  8. Functions
  9. Scope
  10. Compound Data
  11. Reference Semantics
  12. Refactoring
  13. Program Design
  14. Transition to Java
  15. Debugging in Java
  16. Unit Testing
  17. Classes - Writing your own Types
  18. Classes - Copying objects
  19. Classes - Functions inside objects
  20. Classes - Composition
  21. Classes - Array of objects
  22. Classes - Class holding array(s)
  23. Recursion - What goes on during a function call
  24. Recursion
  25. Recursion with String data
  26. Tail-optimized recursion
  27. Recursion with arrays
  28. Lists
  29. Iteration
  30. List of Lists
  31. Custom-built ArrayList
  32. Recursive data structures - 1
  33. Recursive data structures - 2
  34. Searching
Mathematics for Programmers
  1. Logic and Proofs
  2. Relations
  3. Mathematical Functions
  4. Matrices
  5. Binary Numbers
  6. Trigonomtry
  7. Finite State Machines
  8. Turing Machines
  9. Counting - Inclusion/Exclusion
  10. Graph Algorithms
Data Structures and Algorithms
  1. Algorithm Efficiency
  2. Algorithm Correctness
  3. Trees
  4. Heaps, Stack, and Queues
  5. Maps and Hashtables
  6. Graphs and Graph Algorithms
  7. Advanced Trees and Computability
Systems Programming
  1. Command line control
  2. Transition to C
  3. Pointers
  4. Memory Allocation
  5. IO
  6. Number representations
  7. Assembly Programming
  8. Structs and Unions
  9. How memory works
  10. Virtual Memory
The Practice of Programming
  1. Version Control with Git
  2. Inheritance and Overloading
  3. Generics
  4. Exceptions
  5. Lambda Expressions
  6. Design Patterns
  7. Concepts of Concurrency
  8. Concurrency: Object Locks
  9. Modern Concurrency
Distributed Systems
  1. System Models
  2. Naming and Distributed File Systems
  3. Synchronisation and Concurrency
  4. Fault Tolerance and Security
  5. Clusters and Grids
  6. Virtualisation
  7. Data Centers
  8. Mobile Computing
Programming Languages
  1. Transition to Scala
  2. Functional Programming
  3. Syntax Analysis
  4. Name Analysis
  5. Type Analysis
  6. Transformation and Compilation
  7. Control Abstraction
  8. Implementing Data Abstraction
  9. Language Runtimes
Provably Correct Programs
  1. Transition to Coq
  2. Proof by Induction, Structured Data
  3. Polymorphism and Higher-Order Functions
  4. More Basic Tactics
  5. Logical Reasoning in Proof Assistants
  6. Inductive Propositions
  7. Maps
  8. An Imperative Programming Language
  9. Program Equivalence
  10. Hoare Logic
  11. Small-Step Operational Semantics
  12. Simply-typed Lambda Calculus
Assumed Knowledge:
Learning Outcomes:
  • Have an understanding of tail recursion.
  • Be able to tail-optimize a recursive function.

Author: Gaurav Gupta

The problem with recursion

Every call to a function requires keeping the formal parameters and other variables in the memory for as long as the function doesn’t return control back to the caller.

These variables and the function’s stack frame (the entry in the call stack) must be retained until it’s no longer required.

For example, consider the following function definition:

1
2
3
4
5
6
7
8
9

public static int factorial(int n) {
	if(n <= 1) {
		return 1;
	}
	int contribution = n;
	int sub = factorial(n-1);
	int result = contribution * sub;
	return result;
}

Each call to function factorial has to wait for the next call to return the value to it, before it can be terminated, and the frame stack removed.

Let’s say the origin call is factorial(4) (which calls factorial(3), which calls factorial(2), which calls the terminal case in factorial(1)). Green represents the stack frame on the top of the call stack (active function).

At the time factorial(1) executes, the call stack looks like the following:

Eureka!

Instead of creating all these variables inside the function, if we can (and pay attention to the statement carefully), pass the state of the stack so far as parameters, we wouldn’t need to maintain the previous stack frames. Oh my several Gods - that would be amazing!

P.S. Java still doesn’t support tail optimization… 😞

(Definition) Tail-optimized design is when every last possible statement (typically a return statement) in a function is a just the recursive call (or the end case value).

1
2
3
4
5
6

public static int factorial(int n, int currentState) {
	if(n <= 1) {
		return currentState;
	}
	return factorial(n-1, currentState * n);
}

The value for currentState in the initial call should be 1. Sample client:

1
2
3
4
5

public class Client {
	public static void main(String[] args) {
		int val = factorial(4, 1); //1 being the initial value of currentState
	}
}

Now, only the current stack frame needs to be kept in the memory and the previous stack frames for the recursive function can be discarded.

At the time factorial(1, 24) executes, the call stack looks like the following:

You can also create a second proxy function so that you don’t have to pass the second parameter during the initial call, like,

1
2
3

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

As long as the number (or order) of parameters is different, two functions can have the same name.

Benefits

  1. As already mentioned, stack frames of previous calls need not be kept on the stack.
  2. Achieves natural speedup (see example 6 at the bottom of the page).

Some more examples

Example 1

Without tail optimization

1
2
3
4
5
6

public static int sumDigits(int n) { //assuming n >= 0
	if(n == 0) {
		return 0;
	}
	return n%10 + sumDigits(n/10);
}

With tail optimization

1
2
3
4
5
6

public static int sumDigits(int n, int currentState) {
	if(n == 0) {
		return currentState;
	}
	return sumDigits(n/10, currentState + n%10);
}

Example 2 (small increment over example 1)

Without tail optimization

1
2
3
4
5
6
7
8
9
10
11

public static int sumEvenDigits(int n) { //assuming n >= 0
	if(n == 0) {
		return 0;
	}
	if(n%2 == 0) {
		return n%10 + sumEvenDigits(n/10);
	}
	else {
		return sumEvenDigits(n/10);
	}
}

With tail optimization

1
2
3
4
5
6
7
8
9
10
11

public static int sumEvenDigits(int n, int currentState) { //assuming n >= 0
	if(n == 0) {
		return currentState;
	}
	if(n%2 == 0) {
		return sumEvenDigits(n/10, currentState + n%10);
	}
	else {
		return sumEvenDigits(n/10, currentState);
	}
}

Example 3

Without tail optimization

1
2
3
4
5
6
7
8
9
10
11
12

public static boolean isPalindrome(String str) { 
	if(str == null) {
		return false;
	}
	if(str.length() < 2) {
		return true;
	}
	if(str.charAt(0) != str.charAt(str.length()-1)) {
		return false;
	}
	return isPalindrome(str.substring(1, str.length()-1));
}

With tail optimization

No change needed, already tail-optimized as the last statement is the recursive call and nothing else.

Example 4

Without tail optimization

1
2
3
4
5
6
7
8
9

public static String reverse(String str) { 
	if(str == null || str.length() < 2) {
		return str;
	}
	char first = str.charAt(0);
	char last = str.charAt(str.length()-1);
	String remaining = str.substring(1, str.length()-1);
	return last + reverse(remaining) + first;
}

The current version is not convenient for tail optimization, so we’ll do a slight modification.

Without tail optimization - version 2

1
2
3
4
5
6
7
8

public static String reverse(String str) { 
	if(str == null || str.length() < 2) {
		return str;
	}
	char first = str.charAt(0);
	String remaining = str.substring(1);
	return reverse(remaining) + first;
}

Now, it’s ready to tail optimize.

With tail optimization

1
2
3
4
5
6
7
8
9

public static String reverse(String str, String constructed) { 
	if(str == null) {
		return null;
	} 
	if(str.isEmpty()) {
		return constructed;
	}
	return reverse(str.substring(1), str.charAt(0) + constructed);
}

Example 5

Without tail optimization

1
2
3
4
5
6

public static int gcd(int a, int b) { //assuming a, b >= 0
	if(b == 0) {
		return a;
	}
	return gcd(b, a%b);
}

With tail optimization

Already tail-optimized.

Example 6

Without tail optimization

1
2
3
4
5
6

public static int fib(int n) { 
	if(n == 0 || n == 1) {
		return n;
	}
	return fib(n-1) + fib(n-2);
}

With tail optimization

*This is a tricky one. Please see 1 and 2 for some nice explanations.

1
2
3
4
5
6
7
8
9
10
11
12

//initially called as fib(n, 0, 1)
public static int fib(int n, int a, int b) { 
	if(n==0) {
		//it will only ever be called directly from client, 
		//never from another fib call
		return a; //which WILL be 0
	}
	if(n==1) {
		return b;
	}
	return fib(n-1, b, a+b);
}