In the sense that the function calls itself, it is recursive. However, it has the important attribute that the result of the invocation depends solely on the result from another function call; no values from the current stack are needed. The result is provided by
return iterativeSum(--x, ++y);
not from something like
return iterativeSum(--x, ++y) + x;
which would require "coming back" from the recursive call, doing something with the result, and then returning that. Because the result doesn't require anything from the current stack frame, an implementation (in some languages, depending on the semantics) could eliminate or reuse the current stack frame. That's called tail-call elimination, and it's mandated in some languages, like Scheme. That's why the Scheme implementation of that algorithm is essentially iterative: it doesn't require unbounded amounts of stack space.
In Scheme, the tail call elimination means that the implementation is essentially the following, in which iterativeSumDriver is a trampoline of sorts, or the iterative driver over the results provided by iterativeSumInternal.
public class IterativeSummer {
/**
* Returns a sum, computed iteratively.
*
* @param x the augend
* @param y the addend
* @return the sum of the augend and addend
*/
public int iterativeSumDriver(int x, int y) {
int[] state = new int[] { x, y };
while (state.length == 2) {
state = iterativeSumInternal(state[0], state[1]);
}
return state[0];
}
/**
* Returns the new computation state of a iterative sum
* computation. If x is 0, then returns an array of just y.
* Otherwise, returns an an array of x-1 and y+1.
*
* @param x the augend
* @param y the addend
* @return the next interal state
*/
int[] iterativeSumInternal(int x, int y) {
if (x == 0) {
return new int[] { y };
}
else {
return new int[] { x-1, y+1 };
}
}
public static void main(String[] args) {
int x = 5;
int y = 6;
int sum = new IterativeSummer().iterativeSumDriver(x,y);
System.out.println(String.format("%d + %d = %d", x, y, sum));
}
}
A Proper Trampoline
As Will Ness pointed out, a proper trampoline doesn't really know about the states used in a computation; it just needs to have something to call until a non-callable thing gets returned. Here's a version that does that.
public class Trampoline {
/**
* State of a computation for a trampoline.
*
* @param <T> the type of value
*/
public interface TrampolineState<T> {
/**
* Returns whether the state is a finished state.
*
* @return whether the state is a finshed state
*/
boolean isFinished();
/**
* Returns the value, if this state is finished.
*
* @return the value
* @throws IllegalStateException if the state is not finished
*/
T getValue() throws IllegalStateException;
/**
* Returns the next state, if this state is not finished.
*
* @return the next state
* @throws IllegalStateException if the state is finished
*/
TrampolineState<T> getNext() throws IllegalStateException;
}
/**
* Executes a trampolined state and its successors until a finished state is
* reached, and then returns the value of the finished state.
*
* @param state the state
* @return the value
*/
public <T> T trampoline(TrampolineState<T> state) {
while (!state.isFinished()) {
state = state.getNext();
}
return state.getValue();
}
/**
* Returns the state for for sum computation.
*
* @param x the augend
* @param y the addend
* @return the state
*/
private TrampolineState<Integer> getSumTrampolineState(int x, int y) {
return new TrampolineState<Integer>() {
@Override
public boolean isFinished() {
return x == 0;
}
@Override
public Integer getValue() {
if (!isFinished()) {
throw new IllegalStateException();
}
return y;
}
@Override
public TrampolineState<Integer> getNext() {
if (isFinished()) {
throw new IllegalStateException();
}
return getSumTrampolineState(x - 1, y + 1);
}
};
}
/**
* Returns a sum, computed by a trampolined computation.
*
* @param x the augend
* @param y the addend
* @return the sum
*/
public int sum(int x, int y) {
return trampoline(getSumTrampolineState(x, y));
}
}
See also:
