パスワードを忘れた? アカウント作成
626507 journal

YuAokiの日記: 男は黙って、末尾再帰(テールリカーシブ)

日記 by YuAoki
 再帰というのは、とても楽しい。いったん数学的帰納法がわかってしまうと、パターン当てはめだけで、どんどん計算をコンピュータがしてくれるようになる。
 ただ、再帰をCでも、C++でもJavaでも、使いまくっているとどうしても計算が遅くなるという状態に陥ってしまうことがある。
 付加級数的にスタック量が増えてしまうからだ。
 そこで、そういった場合には、末尾再帰というテクニックを使うのが普通らしい。Standard MLの授業のときに、先生がひたすらそればかりを強調するので、それをCで実現するテクニックを少し練習したくなって調べてみた。
 末尾再帰とは英語でtail call recasiveという。例えばfactorialをCで書くと、通常は、再帰を習っただけだと以下のような感じになる。

#include <stdio.h>

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

int main(void)
{
  int m;
  scanf("%d",&m);
  printf("%d\n",factorial(m));
  return 0;
}

これを、以下のように書くのが、テールリカーシブ(末尾再帰)テクニックだ。

#include <stdio.h>

int fact_temp(int n,int sofar)
{
  if(n<=1)
    return sofar;
  else
    return fact_temp(n-1,n*sofar);
}

int factorial(int n)
{
  if(n<0)
    return 0;
  else
    return fact_temp(n,1);
}

int main(void)
{
  int m;
  scanf("%d",&m);
  printf("%d\n",factorial(m));
  return 0;
}

■例2

上が、f(n)=n!=n*(n-1)*……1だったので、次は、f(n)=n+(n-1)+……+1をといてみよう。

まず、一般的には、以下のとおり。

#include <stdio.h>

int f(int n)
{
  if(n==0)
return 0;
if(n==1)
return 1;
return n+f(n-1);
}

int main(void)
{
  int m;
scanf("%d",&m);
printf("%d\n",f(m));
return 0;
}

これを、テールリカーシブで書くと、

#include <stdio.h>

int f_temp(int n,int sofar)
{
  if(n<=0) return sofar;
return f_temp(n-1,n+sofar);
}

int f(int n)
{
  if(n==1) return 1;
if(n==0) return 0;
return f_temp(n,0);
}

int main(void)
{
  int m;
scanf("%d",&m);
printf("%d\n",f(m));
return 0;
}

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

にわかな奴ほど語りたがる -- あるハッカー

読み込み中...