Consider a simple factorial function

Here is a simple Java implementation that uses recursion:

1 2 3 4 5 6 7 8 9 10 | public void factorial(int n) { if (n <= 1) { return 1; } else { return n*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 10 | public static int sum(int a,int b) { if ( a == 0 ) { return b; } else{ return sum(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.

## No comments:

## Post a Comment