1

私には次のタスクがあります。

数と力を求めるプログラムを作成します。数を累乗する再帰関数を記述します。たとえば、数値が2で、累乗が4の場合、関数は16を返します。

プログラムを作成しましたが、コンパイルしてもエラーは発生しませんが、プログラムを起動して値を入力すると、「StackOverflow」というエラーが表示されます。再帰関数が無限大になったと思いますが、他の方法で書く方法がわかりません。

これは私のコードです：

#include <iostream>
using namespace std;
int powpow(int number);

int main(){
    cout<<"Enter number:";
    int x;
    cin>>x;
    cout<<"The result of ("<<x<<" * "<<x<<") * "<<x*x<<" is: "<<powpow(x);
    system("pause");
    return 0;
}
int powpow(int number){
    int result = number*number;
    return powpow(result);
}
4

3 に答える 3

9

再帰の終了条件がないため、再帰は永久に実行されます。

再帰をよく理解していないように思われるので、もう少し単純なフィボナッチ数列から始めたいと思います。

再帰の観点から関数を定義するときはいつでも、最初にベースケースを定義する必要があります。フィボナッチの場合、2つの基本ケースがあります。

F(0) = 0
F(1) = 1

つまり、英語では、「0のFは0、1のFは1」です。または、さらに簡単に言えば、関数Fに0を渡すと、0が返されます。1を渡すと、1が返されます。

基本ケースを定義したら、漸化式を探す必要があります。フィボナッチの場合、次のような再発があります。

F（n）= F（n-1）+ F（n-2）

したがってn >= 2、については、上記の繰り返しを使用できます。なんで？さて、n=2で試してみましょう。

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

これで、F（2）の答えが1であることがわかりました。さらに、F（3）の答えを計算できます。なんで？さて、F（3）を計算するために何が必要ですか？F（2）とF（1）が必要です。F（1）が基本ケースであるため、これらの両方の答えが得られ、上記のF（2）を解きました。

それでは、Fを解くための擬似コードを書いてみましょう。

function F(int n) {
  // handle base cases
  if (n equals 0)
    return 0
  if (n equals 1)
    return 1

  // recurrence
  return F(n-1) + F(n-2);
}

再帰関数では、関数の最初で常に基本ケースを処理することに注意してください。基本ケースが設定されていない場合、この再発を定義することはできません。そうでない場合、再発の終了条件はありません。そのため、常に関数の先頭にベースケースを配置します。

さて、上記の説明を考えると、別の良い練習は階乗関数の再帰関数を書くことです。したがって、次の手順に従います。

1. Define the base case (use wikipedia article for hints).
2. Define recurrence in terms of base case
3. Write pseudo code to solve the recurrence, and be sure to put base case(s) at beginning of function, and recurrence at end.

これらの手順を理解したら、電源の繰り返しに進む方がはるかに理にかなっているはずです。

于 2012-05-28T22:34:37.333 に答える
3

あなたの機能

  • すべきことをしない
  • 終了条件がない

x^yこれについて考えてみてください:パラメーターとして 1 つの数値のみを受け取る場合、関数はどのように戻ることができるでしょうか。次に、数を累乗する方法を考えてみてください。実装は明らかです。

于 2012-05-28T22:36:05.023 に答える
2

再帰ルーチンには、常に「自明」または「基本」ケースが必要です。あなたが書いたことを考えて、x に 1 を渡します。再帰を止めるものは何ですか?

powpow(1)
  result = 1*1
  call powpow(1)
    result = 1*1
    call powpow(1)
      result = 1*1
      call powpow(1)

adinfinitum (またはスタックを実行するまで)

于 2012-05-28T22:39:05.160 に答える