再帰関数での実装例（ヒント）：

int nthprime( int n )
{
    if( n == 1 ){
        return 2;
    }
    else{
        int prime;
        ★primeに "(n-1)番目の素数+1" を代入（ここで再帰）
        ★primeが素数でない間、primeをインクリメントする
        return prime;
    }
}

★のコードを書くと解答になっちゃうので、伏せておきます。

> 自力で考えたけど if (i == 1) return 2; ぐらいまでしか思いつかない... orz
> ネットもがんばって探しましたが，n番目の素数を再帰で書く方法が見つからないよ〜。

あえて再帰を使うなら、こんな枠組みかと。意味ないですね。

int foundPrimes[1024];

int GetNthPrime(int n)
{
    int result, prevPrime;
    if (n == 1)
        result = 2;
    else {
        prevPrime = GetNthPrime(n - 1);
        
        // foundPrimes を使って、ｎ番目を見つける
        // prevPrime 以降を foundPrime で割って試す。

        // result = ...;
    }
    foundPrimes[n - 1] = result;
    return result;
}

#include <assert.h>
#include <stdio.h>

unsigned nthprime(unsigned n)
{
    static unsigned called = 0;
    ++called;
    printf("nthprime %u 回目の呼び出し\r", called);
    assert(n);
    if (n == 1) {
        return 2;
    } else {
        unsigned prime;
        for (prime = nthprime(n-1)+1; ; ++prime) {
            unsigned i = n - 1;
            for (; i > 0 && prime % nthprime(i); --i)
                ;
            if (i == 0) {
                break;
            }
        }
        return prime;
    }
}

int main(void)
{
    unsigned i;
    for (i = 1; i <= 500; ++i) {
        printf("\n%d 番目の素数: %u\n", i, nthprime(i));
    }
    return 0;
}

nthprime 1 回目の呼び出し
1 番目の素数: 2
nthprime 4 回目の呼び出し
2 番目の素数: 3
nthprime 16 回目の呼び出し
3 番目の素数: 5
nthprime 60 回目の呼び出し
4 番目の素数: 7
nthprime 340 回目の呼び出し
5 番目の素数: 11
nthprime 1300 回目の呼び出し
6 番目の素数: 13
nthprime 7441 回目の呼び出し
7 番目の素数: 17
nthprime 28464 回目の呼び出し
8 番目の素数: 19
nthprime 163264 回目の呼び出し
9 番目の素数: 23
nthprime 1277287 回目の呼び出し
10 番目の素数: 29
nthprime 4945881 回目の呼び出し
11 番目の素数: 31
nthprime 37474812 回目の呼び出し
12 番目の素数: 37
nthprime 43588205 回目の呼び出し

そのような面倒なことにはなりませぬ。

#include <stdio.h>

int nthprime( int n );

int main( void )
{
    int i;
    for( i = 1; i <= 500; i++ ){
        printf( "%3dth prime : %5d\n", i, nthprime( i ) );
    }
    return 0;
}

int nthprime( int n)
{
    if( n == 1 ){
        return 2;
    }
    else{
        int prime = nthprime( n - 1 ) + 1;
        for( ; ; prime++ ){
            int is_prime = 1;
            int i;
            for( i = 2; i * i <= prime; i++ ){
                if( prime % i == 0 ){
                    is_prime = 0;
                    break;
                }
            }
            if( is_prime ){
                break;
            }
        }
        return prime;
    }
}


あるいは、素数判定を補助関数化した方がスッキリするかも。

int is_prime( int n );

int nthprime( int n )
{
    if( n == 1 ){
        return 2;
    }
    else{
        int prime = nthprime( n - 1 ) + 1;
        while( !is_prime( prime ) ){
            prime++;
        }
        return prime;
    }
}

int is_prime( int n )
{
    int i;
    for( i = 2; i * i <= n; i++ ){
        if( n % i == 0 ){
            return 0; // n は素数でない
        }
    }
    return 1;         // n は素数である
}

> for (prime = nthprime(n-1)+1; ; ++prime) {
>   unsigned i = n - 1;
>   for (; i > 0 && prime % nthprime(i); --i)
>     ;
>   if (i == 0) {
>     break;
>   }
> }

これはわざとですよね？
よくある Fibonacci 数列の例もこんな感じですが、非効率を極めた感じ。
素数候補未満の自然数全てで割った方がよっぽど速いのに、
わざわざ素数を探し出して割っている。
Ackermann 関数みたいですね。

素数を再帰的に求める、というテーマに相応しいのではないでしょうか。
グローバルや static 変数を使うのなんて、むしろ邪道です。

# 500番目は無理でしょう。

> 素数を再帰的に求める、というテーマに相応しいのではないでしょうか。
> グローバルや static 変数を使うのなんて、むしろ邪道です。

強く同意します^^

#include <stdio.h>

static int next_prime_sub(int num, int divisor)
{
    int next_prime(int num);
    if (num < divisor * divisor) return num;
    if (num % divisor) return next_prime_sub(num, next_prime(divisor));
    return next_prime(num);
}

int next_prime(int num)
{
    return next_prime_sub(num + 1, 2);
}

int nth_prime(int no)
{
    if (no < 1) return -1; // エラー
    if (no == 1) return 2;
    return next_prime(nth_prime(no - 1));
}

int main(void)
{
    printf("%d\n", nth_prime(500));

    return 0;
}

1. 素数の定義に沿って関数を書く
2. 再帰にこだわる

> > よくある Fibonacci 数列の例もこんな感じですが、非効率を極めた感じ。
> > Ackermann 関数みたいですね。
> 
> これの意味が分かりません。無駄が多いってことでしょうか?
> # 帰納的関数うんぬんは勉強不足のため現在理解できません… orz

Fibonacci 数列の定義に関しては、ググってもらっているとして、
よくこんな関数で書かれています。

int Fibonacci(int n) {
    if (n == 1 || n == 2)
        return 1;
    else
        return Fibonacci(n - 2) + Fibonacci(n - 1);
}

Fibonacchi(10) == 55 ですが、この値を計算するために、
Fibonacchi(1) と Fibonacchi(2) が、合わせて５５回呼ばれています。

普通に人が計算するなら、1,1,2,3,5,8,13,21,34,55 と順に計算すれば
１０回程度の足し算で計算できるのに、わざわざ再帰関数を
使っているのが無駄ということです。

数列の定義が再帰的（≒帰納的）だからといって、再帰関数の例題に
されているのが良くなく、素数探索と同様、再帰関数の良くない使いかた
だと思います。素数ほどひどいとは思いませんが。

Ackermann 関数も再帰的に定義されていますが、小さな引数で
再帰の回数が爆発的に増えるのが特徴です。
この特徴を生かしてコンピュータの性能試験に使うとか読んだことが
ありますが、他には用途はあるのでしょうか？

> # 褒め言葉 ですよね…

手放しで絶賛です。

再帰関数の有効な使いかたの学習の為に良いと思うのが、以下のＨＰ。
人によってはパズルを解くという用途を"有効"とはみなさないかもしれませんが。

http://www.pro.or.jp/%7Efuji/index.html
http://www.pro.or.jp/%7Efuji/puzzlestudy/recursive/index.html

http://www.ic-net.or.jp/home/takaken/index.html
http://www.ic-net.or.jp/home/takaken/pz/index.html

あんまり変わりばえしませんが：

#include <stdlib.h>
#include <stdio.h>

int is_prime( int num, const int* found )
{
    int i;
    for( i = 0; found[i] * found[i] <= num; i++ ){
        if( num % found[i] == 0 ){
            return 0;
        }
    }
    return 1;
}

int nthprime_sub( int index, int* found  )
{
    if( index == 0 ){
        return found[index] = 2;
    }
    else{
        int prime = nthprime_sub( index - 1, found );
        while( !is_prime( ++prime, found ) ){
            ;
        }
        return found[index] = prime;
    }
}

int nthprime( int n )
{
    int* found = (int*)malloc( sizeof( int ) * n );
    int result = nthprime_sub(  n - 1, found );
    free( found );
    return result;
}

int main( void )
{
    printf( "%d\n", nthprime( 500 ) );
    return 0;
}

#include <stdio.h>

int is_prime(int i, int j)
{
    return (i % j) ? is_prime(i, j + 1) : (i == j);
}

int prime_sub(int n, int i)
{
    return (is_prime(i, 2) && --n == 0) ? i : prime_sub(n, i + 1);
}

int nthprime(int n)
{
    return prime_sub(n, 2);
}

int main(void)
{
    printf(" %d\n", nthprime(500));
    return 0;
}

#include <iostream>

int is_prime(int i, int j)
{
    return (i % j) ? is_prime(i, j + 1) : (i == j);
}

int nthprime(int n, int i = 2)
{
    return (is_prime(i, 2) && --n == 0) ? i : nthprime(n, i + 1);
}

int main()
{
    std::cout << nthprime(500) << '\n';
}