例 2: 再帰(recursion)

再帰と言うのは, 感覚的に漸化式をそのままプログラムする様なものです. 例えば, は漸化式 を満たします. ほとんどの高級言語では, これをそのままプログラムで表現する事が できます. C 言語では, 次のようになります. 次の例の sum が まさに上の漸化式の定義通りになっています. 実際の計算が どのようになされるかを考えて見ると, コンパイラの仕事の 理解につながるかも知れません. 興味のある人は, 調べてみて下さい. 再帰という言葉が, 適切である事がわかります.

/* File name 4-4.c */

#include <stdio.h>
#define BUFFSIZE 1024

unsigned long sum(long n);

main()
{
       int n;
       char nyuryoku[BUFFSIZE];

       printf("Input a positive integer.>> ");
       fgets(nyuryoku, BUFFSIZE, stdin);
       sscanf(nyuryoku, "%d", &n);
       printf("The sum of 1 to %d is %d .\n", n, sum(n));
}

unsigned long sum(long n)
{
      if ( n==1 ) 
           return 1;
      else 
           return sum(n-1)+n;
}