XSLTで fibonacci

フィボナッチ数列を得る再帰関数を書くと、加算して F_n を計算するための F_n-1 と F_n-2 を求める際に、一度通った再帰の道筋を何度も通ってしまって、無駄な計算が物凄く多くなるのが、よく問題になる。

これを何とかして重複計算のないように改良するというのが、いろんな言語で初学者の練習問題にもなったりするようだけど、ここでは XSLT でそれをやってみる。

test2.xml

<?xml version="1.0" encoding="UTF-8"?>
<fib nth="10"/>

上のような XML を読んで、1番から nth番までのフィボナッチ数列を縦に並べたテキストが得られるようにしたい。一個の解として、こんな XSLT コードを考えてみた。

test2.xsl

<?xml version="1.0" encoding="UTF-8" ?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="text" indent="no"/>
  <xsl:template name="fib">
    <xsl:param name="n" select="1"/>
    <xsl:variable name="pair">
      <xsl:choose>
        <xsl:when test="$n=1">0,1</xsl:when>
        <xsl:otherwise>
          <xsl:call-template name="fib">
            <xsl:with-param name="n" select="$n - 1"/>
          </xsl:call-template>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:variable>
    <xsl:value-of select="substring-after($pair, ',')"
    />,<xsl:value-of select="substring-before($pair, ',') + substring-after($pair, ',')"/>
  </xsl:template>

 <xsl:template name="fib-print">
    <xsl:param name="p1"/>
    <xsl:param name="p2"/>
    <xsl:if test="0 &lt; $p1">
      <xsl:call-template name="fib-print">
        <xsl:with-param name="p1" select="$p2 - $p1"/>
        <xsl:with-param name="p2" select="$p1"/>
      </xsl:call-template>
    </xsl:if>
    <xsl:value-of select="$p2"/><xsl:text>&#010;</xsl:text>
 </xsl:template>

  <xsl:template match="/fib">
    <xsl:variable name="pair">
      <xsl:call-template name="fib">
        <xsl:with-param name="n" select="@nth - 1"/>
      </xsl:call-template>
    </xsl:variable>
    <xsl:call-template name="fib-print">
      <xsl:with-param name="p1" select="substring-before($pair, ',')"/>
      <xsl:with-param name="p2" select="substring-after($pair, ',')"/>
    </xsl:call-template>
  </xsl:template>
</xsl:stylesheet>

テンプレート fib は、二つの値を「F_n, F_n-1」のような形でカンマ区切りの文字列で返すようにした。例えば nth = 5 だと "5,8"、nth = 1 だと "1,1"となる。テンプレート fib-print は、この値の組をいったん逆にたどって、"0,1"に届いたところから折り返して出力するようにしてみた。

Eclipseで実行すると、1, 1, 2, 3, 5, 8, 13, 21, 34, 55と 縦に並んだテキストが生成される。文字列操作が多いのがちょっと面白くないけど、O_(n)のロジックにはなった。