Consider a simple factorial function

Here is a simple Java implementation that uses recursion:

1 2 3 4 5 6 7 8 9 10publicvoidfactorial(intn){if(n<=1){return1;}else{returnn*factorial(n-1);}}

If you called factorial(5), this is how recursion evaluate.

factorial(5)

5 * factorial(4)

5 * (4 * factorial(3))

5 * (4 * (3 * factorial(2)))

5 * (4 * (3 * (2 * factorial(1))))

5 * (4 * (3 * (2 * 1)))

120

Note how every recursive call has to complete before the java interpreter begins to actually do the work .

Here's a tail-recursive version of function that add N Integers.

1 2 3 4 5 6 7 8 9 10publicstaticintsum(inta,intb){if(a==0){returnb;}else{returnsum(a-1,b+a);}}

Here's the sequence of events that would occur if you called sum(5,0).

sum(5, 0)

sum(4, 5)

sum(3, 9)

sum(2, 12)

sum(1, 14)

sum(0, 15)

15

In the tail-recursive case, with each evaluation of the recursive call, the b is updated.

Here is a simple Java implementation that uses recursion:

1 2 3 4 5 6 7 8 9 10publicvoidfactorial(intn){if(n<=1){return1;}else{returnn*factorial(n-1);}}

If you called factorial(5), this is how recursion evaluate.

factorial(5)

5 * factorial(4)

5 * (4 * factorial(3))

5 * (4 * (3 * factorial(2)))

5 * (4 * (3 * (2 * factorial(1))))

5 * (4 * (3 * (2 * 1)))

120

Note how every recursive call has to complete before the java interpreter begins to actually do the work .

Here's a tail-recursive version of function that add N Integers.

1 2 3 4 5 6 7 8 9 10publicstaticintsum(inta,intb){if(a==0){returnb;}else{returnsum(a-1,b+a);}}

Here's the sequence of events that would occur if you called sum(5,0).

sum(5, 0)

sum(4, 5)

sum(3, 9)

sum(2, 12)

sum(1, 14)

sum(0, 15)

15

In the tail-recursive case, with each evaluation of the recursive call, the b is updated.