Skip to Content

Before we start to research tail recursion, let’s first have a look at the normal recursion.

A simple factorial implementation by recursion:

function factorial(n){
  if(n ===1) {
     return 1;
  }
  return n *factorial(n -1);
}

Let N = 5, see how new stack frame is created for each time of recursive call:

/wp-content/uploads/2015/11/clipboard1_829799.png

We have two stack frames now, one stores the context when n = 5, and the topmost one for current calculation: n = 4

/wp-content/uploads/2015/11/clipboard2_829801.png

/wp-content/uploads/2015/11/clipboard3_829802.png

/wp-content/uploads/2015/11/clipboard4_829803.png

Now since n equals to 1, we stop recursion. The current stack frame ( n = 1 ) will be poped up, the frame under it will be activated and become the topmost frame, with calculated result 1 passed into.

/wp-content/uploads/2015/11/clipboard5_829804.png

/wp-content/uploads/2015/11/clipboard6_829805.png

/wp-content/uploads/2015/11/clipboard7_829806.png

/wp-content/uploads/2015/11/clipboard8_829807.png

/wp-content/uploads/2015/11/clipboard9_829808.png

key note for normal recursion: during recursion, every generated stack frame is needed and could not e destroyed until the final result is calculated. The calculation is actually not started until the recursion reaches the end ( the condition n === 1 fulfills ). If N is a big integer, it will lead to huge number of stack frames and finally the “stack overflow” or “out of memory” is inevitable.

tail recursion

Source code below:

function tailFactorial(n, total) {
if(n ===1)
    return total;
return tailFactorial(n -1, n * total);
}
function factorial2(n) {
  return tailFactorial(n,1);
}

There are two biggest differences compared with normal recursion:

1. A new internal function tailFactorial is introduced here.

2. The calculation is actually now spread within every recursive stack frame. Each frame finishes one part of calculation and pass the current result to the next frame. Once the current stack frame finishes its task, it is actually not needed any more. And thus for example the model browser can then do some optimization on those useless stack frames.

Observe the stack frame for tail recursion step by step:

/wp-content/uploads/2015/11/clipboard11_829809.png

/wp-content/uploads/2015/11/clipboard12_829810.png

/wp-content/uploads/2015/11/clipboard13_829814.png

/wp-content/uploads/2015/11/clipboard14_829815.png

/wp-content/uploads/2015/11/clipboard15_829816.png

/wp-content/uploads/2015/11/clipboard16_829817.png

/wp-content/uploads/2015/11/clipboard17_829818.png

stack popped up:

/wp-content/uploads/2015/11/clipboard18_829819.png

When N = 20, the tail recursion has a far better performance than the normal recursion:

/wp-content/uploads/2015/11/clipboard19_829820.png

Update 2016-01-11

Tail recursion implementation via Scala:

/wp-content/uploads/2015/11/clipboard4_829803.png

The interesting thing is, after the Scala code is compiled into Java Byte code, compiler will eliminate the recursion automatically:

/wp-content/uploads/2015/11/clipboard5_829804.png

Tail Recursion in ABAP

First this is the normal recursion:

REPORT zrecursion.

START-OF-SELECTION.

  DATA: lv_result TYPE int4.

  PERFORM fac USING 6 CHANGING lv_result.

  WRITE: / lv_result.

FORM fac USING iv_n TYPE int4 CHANGING cv_result TYPE int4.
  DATA: lv_n TYPE i.

  cv_result = lv_n = iv_n.
  lv_n = lv_n - 1.
  IF lv_n > 1.
    PERFORM fac USING lv_n CHANGING cv_result.
  ENDIF.
  IF lv_n = 1.
    cv_result = cv_result * lv_n.
  ELSE.
    cv_result = cv_result * iv_n.
  ENDIF.
ENDFORM.

And here comes tail recursion version:

REPORT ztail.

START-OF-SELECTION.

  DATA: lv_result TYPE int4.

  PERFORM fac USING 5 1 CHANGING lv_result.

  WRITE: / lv_result.

FORM fac USING iv_n TYPE int4 iv_acc TYPE int4 CHANGING cv_result TYPE int4.
  DATA: lv_n          TYPE i,
        lv_accumulate TYPE i.

  IF iv_n < 1.
    cv_result = 1.
  ELSEIF iv_n = 1.
    cv_result = iv_acc * iv_n.
  ELSEIF iv_n > 1.
    lv_n = iv_n - 1.
    lv_accumulate = iv_acc * iv_n.
    PERFORM fac USING lv_n lv_accumulate CHANGING cv_result.
  ENDIF.
ENDFORM.

Further reading

I have written a series of blogs which compare the language feature among ABAP, JavaScript and Java. You can find a list of them below:
To report this post you need to login first.

1 Comment

You must be Logged on to comment or reply to a post.

  1. Kimmo Jokinen

    Hi Jerry,

    Thanks for the post!

    With ECMAScript 2015 (or ES6) we will get proper tail call optimization. Tail recursion method takes advantage of tail call optimization when the code is run is strict mode.

    Unfortunately that feature is not really yet implemented by any JavaScript environment. So it’s better to be careful with recursive functions if there’s a risk that the stack would grow big. Overflowing the stack can produce some obscure bugs.

    If interested, see Axel Rauschmayer’s blog post for another good resource about tail call optimization.

    Best regards,

    Kimmo

    (0) 

Leave a Reply