BATファイルでフィボナッチ数列(末尾再帰の展開)

これは、コマンドプロンプト(cmd.exe) Advent Calendar 2015 - Qiitaの14日目の記事です。

※Windows 10 Home 64bit 搭載のcmd.exeにて検証を行っています。

さて、お代の通り、BATファイルでfibコマンドを実装します。

……が、普通に作ってしまうと再帰呼び出しになってしまってアレなので、まずは別言語で試してみます。

• ①ただの再帰で実装
• ②末尾再帰で実装
• ③展開してGOTOに
• ④BATファイル化

という順番でやります。

①ただの再帰で実装

後でGOTOを使うことも考えて、とりあえずCで実装します。

#include <stdio.h>
int main(void){
    printf("%i", fib(10));
}
int fib(n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

②末尾再帰で実装

つまり、1つ前の結果と2つ前の結果を足す、ってことなので・・・
(aが1つ前の結果、bが2つ前の結果)

#include <stdio.h>
int main(void){
    printf("%i", fib(10));
}
int fib(n) {
    return fib_sub(n, 1, 0);
}
int fib_sub(n, a, b) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return a;
    } else {
        return fib_sub(n - 1, a + b, a);
    }
}

③展開してGOTOに

末尾再帰にできたので、gotoを使ったループに展開します

#include <stdio.h>
int main(void){
    printf("%i", fib(10));
}
int fib(n) {
    int a;
    int b;
    int swap;
    
    a = 1;
    b = 0;
    swap = 0;
    
loop:
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return a;
    } else {
        n = n - 1;
        swap = a + b;
        b = a;
        a = swap;
        goto loop;
    }
}

④BATファイル化

ではこれを、BATファイルで書き直します。

@echo off

set /a n = %~1
set /a a = 1
set /a b = 0
set /a swap = 0

:LOOP
	if "%n%"=="0" echo 0 && goto :eof
	if "%n%"=="1" echo %a% && goto :eof
	set /a n = n - 1
	set /a swap = a + b
	set /a b = a
	set /a a = swap
	goto :LOOP

実行してみましょう。

C:\Users\kunst\Desktop>fib 0
0

C:\Users\kunst\Desktop>fib 1
1

C:\Users\kunst\Desktop>fib 10
55

C:\Users\kunst\Desktop>fib 20
6765

できあがり！

C:\Users\kunst\Desktop>fib 50
-298632863

ありゃりゃ……