番号シーケンスの再帰関数を作成する

Question

これは基本的なCS知識ですが、forループを介して再帰関数を実行する考えはまだ分かりません。私は、特に数字による再帰の考え方にはまだ混乱しています。数列3、11、27、59、123があると言うことができます。An = 1 +（8 *（n-1））の数学的再帰的シーケンスを理解する方法を知っていますが、これをC++の再帰関数に入れる方法は本当に分かりません。

誰かが上記の数値シーケンスの再帰関数の作成について概要を説明できますか？

Answer 1

再帰関数には、基底と再帰の2つの「部分」があります。基本ケースは、関数が再帰を停止したとき（呼び出しスタックの巻き戻しを開始するとき）です。ベースがなければ、スタックオーバーフローが発生してプログラムがOSによって終了するまで、関数は自分自身を呼び出し続けます。

再帰部分は、（あなたのケースではi番目の数をシーケンス内で見つける）初期の問題を取り、それを縮小します。これは、ベースケースがヒットするまで発生します。したがって、シーケンス内のi番目の番号を見つけるには、4番目の数字を探し始めるとしますが、3番目の数字に依存します。これは3番目の数字に依存します。最初の再帰は、問題を4番目の数字から3番目の数字に縮小します。

シーケンスの再帰関数でスタブ（テストされていません）があります。

int recursive(int i) { 
    // This is your base case, it prevents infinite recursion. 
    if (i == 0) return 0; // Or whatever you base value is 
    else { 
    int sum = recursive(i-1) + 8 * (i-1); 
    return sum; 
    } 
} 

回帰関数をループで行うことができます。しかし、再帰を必要とする関数があります。たとえば、Ackermann's Functionです。機能のComputerphile

Answer 2

基本的な再帰的な実装には本当に良いビデオ（あなたの順序のための適切な値は3、11、27、51、83、123、...ところであり）：

int seq(int n) 
{ 
    if (n <= 1) 
     return 3; 
    else 
     return seq(n-1) + 8 * (n-1); 
} 

しかし、この実装テール再帰的ではありません（したがって、反復的な実装ではスタックを使用しません）。 A[n] = A[n-1] + 8*(n-1)：あなたのシーケンス機能は次のように定義されている場合は

#include <functional> 

int seq(int n) 
{ 
    std::function<int(int, int)> seq_r = [&] (int n, int acc) -> int { 
     if (n <= 1) 
      return acc; 
     else 
      return seq_r(n-1, acc + 8 * (n-1)); 
    }; 
    return seq_r(n, 3); 
} 

Answer 3

：

int seq_r(int n, int acc) 
{ 
    if (n <= 1) 
     return acc; 
    else 
     return seq_r(n-1, acc + 8 * (n-1)); 
} 

int seq(int n) 
{ 
    return seq_r(n, 3); 
} 

あるいは、同じ実装が、ラムダ式を使用して、関数の内部に隠されseq_rと：私たちは、アキュムレータのパラメータを導入することにより、末尾再帰バージョンを書くことができますあなたは2つのことが必要です。 1）数字のシーケンスを保持する構造、および2）それらの数字を生成する関数またはループ。構造のために私はのstd ::ベクトルを使用し、ループや関数は以下のように使用することができます。

ループ

#include <vector> 

int main() 
{ 
    std::vector<int> storage; 

    // Seed the storage with a number since the sequence looks back. 
    storage.push_back(3); 

    // Define the maximum number count. 
    int maxNum = 5; 

    // Create the sequence by starting from n=1 since there are [n-1] terms. 
    for(int n = 1; n <= maxNum; n++) 
     storage.push_back(storage[n - 1] + 8*(n - 1)); 

    return 0; 
} 

機能

#include <vector> 

std::vector<int> storage; 

void DoSequence(int maxNum, int n = 0) 
{ 
    // Check the limit. 
    if(n > maxNum) 
     return; 

    // Check seeding condition if adding the first element, 
    // otherwise run the equation. 
    if(n == 0) 
     storage.push_back(3); 
    else 
     storage.push_back(storage[n - 1] + 8*(n-1)); 

    // Call the same function. 
    DoSequence(maxNum, n + 1); 
} 

int main() 
{ 
    // Call the recursive function with upper limit (n=5). 
    DoSequence(5); 

    return 0; 
} 

詳細を実装するための他の方法があります。 storageがどのように宣言されているか、または処理されているかなど、個人的な好みです。注：私はこのコードをテストしませんでしたが、うまくいけばあなたはそのアイデアを得るでしょう。つまり、シーケンス関数を定義したら、ループ関数またはプログラム関数を作成して数値を生成します。