Recitation 8: Closure and Variable Capture

Stack: Where the method calls and local variables live. Heap: Where objects live

Essentially, both finds the closest declaration. x → b.this.x y → 2 (a copy stored in the A object through a = b.f()) b.this.x = 2 (accessed via reference)

---

---

long sum(long n, long result) {
	if (n == 0) return result;
	return sum(n - 1, n + result); // nothing left to do 
	after the call
}

This is like the iterative type of recursion. Tail-recursive: The recursive call is the very last action. Current stack frame is no longer needed once the recursive call is made.

long sum(long n) {
	if (n == 0) return 0;
	return n + sum(n - 1); // addition is done AFTER the 
	recursive call returns
}

Caller must still perform n + … after it returns. Each call must therefore keep its own stack frame alive. Causing O(n) stack frames to accumulate, leading to StackOverflowError.

---

abstract class Compute<T> {
	public abstract boolean isRecursive();
	public abstract Compute<T> recurse();
	public abstract T evaluate();
	public abstract T evaluate2();
}

// Base is the last part of Compute
class Base<T> extends Compute<T> {
	private final Supplier<T> val;
	
	public Base(Supplier<T> v) {
		this.val = v;
	}

	// once reached base, no longer recursive
	public boolean isRecursive() {
		return false;
	}

	// there's nothing to recurse, so just return this
	public Base<T> recurse() {
		return this;
	}

	// get the final value
	public T evaluate() {
		return this.val.get();
	}

	public T evaluate2() {
		return this.val.get();
	}
}

// Recursive is a part of Compute
class Recursive<T> extends Compute<T> {
	private final Supplier<Compute<T>> val;
	
	public Recursive(Supplier<Compute<T>> v) {
		this.val = v;
	}

	// while recursive, isRecursive
	public boolean isRecursive() {
		return true;
	}
	
	// activating it
	public Compute<T> recurse() {
		return this.val.get();
	}
	
	// unwrap one level and and calls evaluate (assumes base)
	public T evaluate() {
		Compute<T> v = this.val.get();
		return v.evaluate();
	}
	
	// safer as it checks if it's a base
	public T evaluate2() {
		Compute<T> result = this.val.get();
		while (result.isRecursive()) {
			result = result.recurse();
		}
		return result.evaluate2();
	}
}

Potential naivety

public T evaluate() {
	Compute<T> v = this.val.get();
	return v.evaluate();
}

// If not managed well,
// This is just normal recursion — each evaluate() call pushes a new stack frame. For large n, you get stack overflow!

The fix is to convert recursion into a loop

long sumit(long n, long result) {
	while (n != 0) {
		result = n + result;
		n = n - 1;
	}
	return result;
}

// Instead of recursive method calls building up on the stack, you just update variables in place:

---