c++ - 再帰構造を計算するには?

Question

再帰的な値を計算する方法を教えてくれませんか?

たとえば、次の再帰関数:

int rec (int n)
{
    if (n==1) return (1);
    else  
        return (rec(n-1) + rec(n-1));
}

この種の問題を解決するための一般的な手がかりはありますか?

Answer 1

さて、これを次のように書くことから始めましょう

int rec (int n)
{
  if (n==1) return (1);
  else  
    return (2 * rec(n-1));
}

としてa+a = 2a

次に、 が 2 を乗算n-1し、n 回目に 1 を返していることがわかります。

したがって、これは 2^(n-1) と同等です

この意味はrec(5) = 2^(5-1) = 2^4 = 16

rec(n-1) rec(n-2)注：上記のフォームは、計算などを1回だけ行うため（線形再帰）、あなたが持っていたフォームよりもはるかに効率的です。関数と同様に、それぞれが指数関数的に何度も計算されます（指数再帰）。つまり、私の関数はかなりうまくスケーリングしますが、あなたの関数は基本的に 100 を超えるものには使用できません。