関数 sum() を、ループと、再帰と、末尾再帰でそれぞれ書いたサンプルコード(Python)。末尾再帰のわかりにくさが目立つ。

gistfile1.py

## ループ
def sum(xs):
  t = 0
  for x in xs:
    t += x
  return t

## 再帰呼び出し
def sum(xs):
  if not xs:
    return 0
  else:
    return xs[0] + sum(xs[1:])

## 末尾再帰呼び出し
def sum(xs):
  def sum_(xs, t):
    if not xs:
      return t
    else:
      return sum_(xs[1:], xs[0]+t)
  return sum_(xs, 0)
  
  
## 追記：
## 「linked-listでないリストを再帰で回すことに一体何の意味があるんですかね…」
## という指摘があったので、部分配列の生成を避けて実行効率を改善したバージョンを追加。
## ただし本サンプルコードの目的は「末尾再帰がわかりにくいことを示す」ことであり、
## その目的のためならば、上のコードで十分である。

## 再帰呼び出し（効率良くしたバージョン）
def sum(xs):
  def _sum(xs, i, n):
    if i == n:
      return 0
    else:
      return xs[i] + _sum(xs, i+1, n)
  return _sum(xs, 0, len(xs))

## 末尾再帰呼び出し（効率良くしたバージョン）
def sum(xs):
  def _sum(xs, t, i, n):
    if i == n:
      return t
    else:
      return _sum(xs, t+xs[i], i+1, n)
  return _sum(xs, 0, 0, len(xs))

追加：
「linked-listでないリストを再帰で回すことに一体何の意味があるんですかね…」
という指摘があったので、部分配列の生成を避けて実行効率を改善したバージョンを追加。
ただし本サンプルコードの目的は「末尾再帰がわかりにくいことを示す」ことであることに注意。
その目的のためならば、最初に書いたコードで十分であり、連結リストか配列かというのはささいな問題にすぎないことを認識すべき。