C言語完全に理解したい　再帰とフィボナッチ数

こんかいはただのC言語の話です。半分くらいは

再帰ってかっこいいよね

どのプログラミング言語でも使える、定石ともいっていいテクニックに再帰というものがある。これは自分自身を呼び出す関数を使う手法で、漸化式とか数列とかそういった問題についてエレガントにたちどころに解いてしまうすぐれものだ。よく階乗とかフィボナッチ数を求めるとかの問題が例題になるが、階乗は少し考えるとわかるけどすぐにオーバーフローしてしまうのでやりづらい。ここではフィボナッチ数を例としてあげてみよう。

フィボナッチ数

僕はフィボナッチ数についてはこれっぽっちもしらないけれど漸化式だけは知っている。

F(2+n) = F(1+n) + F(n), F(1) = 1, F(0) = 0

君は一般項を導いてもいいし、愚直に計算してもいい。フィボナッチ数列と金融の関係について語りだすのも自由だ。しかし再三強調したように今はフィボナッチ数列に興味はない。あくまでも再帰の典型的な適用例としてあつかう。

コーディング

#include<stdio.h>

int Fof(int n)
{
if(n == 0)
       return 0;
if(n == 1)
       return 1;

return Fof(n-1) + Fof(n-2);
}

int main()
{
printf("%d\n",Fof(10));
}

コーディングは冗談抜きで30秒で終わる。いやあ再帰っていいもんですねぇ。わざわざ説明するまでもないだろうが、関数Fof(n)は漸化式のようにFof(n-1), Fof(n-2)の和を返す。それを繰り返していくといつかはFof(1), Fof(2)に行き着き、最終的に値が帰ってくるわけだ。この方法はなんて賢いんだろう。しかし、こいつは関数が終わるまでに幾度となく関数を呼ぶ（たとえばFof(7)とFof(6)はどっちもFof(5)を呼ぶ）太え野郎でもある。実際に実装するときには気をつけよう。再帰でむちゃするとスタックオーバーフローなんてこともままにある。

前書きは終わって

記事の目的は再帰の素晴らしさを伝えることではなく、ましてやフィボナッチ数の不思議を知っていただくためでもない。典型的な再帰を使ったプログラムがLLVM-IRでどうなるか見てみたかったのだ。それではどうぞ。

define dso_local i32 @Fof(i32) #0 {
 %2 = alloca i32, align 4
 %3 = alloca i32, align 4
 store i32 %0, i32* %3, align 4
 %4 = load i32, i32* %3, align 4
 %5 = icmp eq i32 %4, 0
 br i1 %5, label %6, label %7

6:                                                ; preds = %1
 store i32 0, i32* %2, align 4
 br label %19

7:                                                ; preds = %1
 %8 = load i32, i32* %3, align 4
 %9 = icmp eq i32 %8, 1
 br i1 %9, label %10, label %11

10:                                               ; preds = %7
 store i32 1, i32* %2, align 4
 br label %19

11:                                               ; preds = %7
 %12 = load i32, i32* %3, align 4
 %13 = sub nsw i32 %12, 1
 %14 = call i32 @Fof(i32 %13)
 %15 = load i32, i32* %3, align 4
 %16 = sub nsw i32 %15, 2
 %17 = call i32 @Fof(i32 %16)
 %18 = add nsw i32 %14, %17
 store i32 %18, i32* %2, align 4
 br label %19

19:                                               ; preds = %11, %10, %6
 %20 = load i32, i32* %2, align 4
 ret i32 %20
}

clangが吐いたコードをFof関数のところだけ持ってきました。ところどころわからないものがありますが、if文だけだったらもう少しがんばればフロントエンドができそうではないですか…？