Looking for recursion Answers? Try Ask4KnowledgeBase
Looking for recursion Keywords? Try Ask4Keywords

Recursion再帰の使い方


備考

再帰とは、それ自体で定義されているものを指します。プログラミングの文脈では、それ自身を呼び出す関数または再帰型を使用する方法です。

再帰関数

再帰関数には2つの部分があります。

  • 1つ以上のベースケース
  • 再帰的なステップ

再帰関数自体を呼び出すので、関数呼び出しの文字列は永遠に続く可能性があります。関数が終了することを確認するために、ベースケースを含める必要があります。これらは、別の再帰呼び出しを実行するのではなく、値を返すときに関数に指示します。通常、再帰関数は、ベースケースに対して入力をチェックし、ベースケースに達した場合にリターンします。基本ケースに達していない場合、関数は再帰的ステップに進む。

再帰的なステップは、関数が自身を呼び出すときです。多くの再帰関数は、再帰呼び出しの結果に対して実行された計算を返します。フィボナッチシーケンスの例は、これを実証しています。この関数は再帰的に自分自身を2回呼び出すと、それらの呼び出しの結果の合計を返します

再帰の一般的な用途の1つは、ツリーやグラフなどの大規模なデータ構造のナビゲーションや計算を実行することです。これは、再帰が小さな問題を解決するために問題を分解し、より大きな問題を解決するための解決策を構築するため、うまく機能します。再帰の別の一般的な使用法は、ループ構造が組み込まれていない言語(通常は関数言語)の反復操作(ループ)を実行することです。

再帰型

再帰型とは、値が同じ型の値から構成されているか、または異なる形で表現されている型です。再帰型は、それ自体で定義されます。たとえば、リストのすべてのサブセット自体がリストであるため、リストは再帰型です。木はノードがツリーから取り除かれるので、残りの構築物は依然としてツリーであるので、ツリーは別の例である。

形式的には、再帰型Tの値の集合は、次の形式の再帰集合式によって定義されます。

T = ... T ...

再帰的集合方程式は多くの解を持つことができますが、このような方程式は常に他のすべての解のサブセットである最小解を持っています。

実用的な例として、リスト型のこのHaskell定義を考えてみると、

data List a = Nil | Cons a (List a)

aのリストは、空のリストか、 ' a '(リストの "頭")と別のリスト( "tail")を含むコンスセルのいずれかでaことを意味します。

C ++で再帰を伴うパインドメイルのチェック

// Checks a string to see if it is a palindrome
bool function IsPalindrome(string input) {
    if (input.size() <= 1) {
        return true;
    }
    else if (input[0] == input[input.size() - 1]) {
        return IsPalindrome(input.substr(1,input.size() - 2));
    }
    else {
        return false;
    }
}
 

再帰を使用して階層構造を作成する[JavaScript]

var directories = [
  {name: 'users' , parent : null },
  {name: 'distalx' , parent : 'users' },
  {name: 'guest' , parent : 'users' },
  {name: 'shared' , parent : 'users' },
  {name: 'documents' , parent : 'distalx' },
  {name: 'music' , parent : 'distalx' },
  {name: 'desktop' , parent : 'distalx' },
  {name: 'javascript' , parent : 'documents' },
  {name: 'funjs' , parent : 'documents' },
  {name: 'functions' , parent : 'documents' }
]


var sortDirectories= function(directories, parent){
  let node = [];
  directories
  .filter(function(d){ return d.parent === parent})
  .forEach(function(d){
    var cd = d;
    cd.child = sortDirectories(directories, d.name);
    return node.push(cd);
  })
  return node;
}

var results = sortDirectories(directories, null);
JSON.stringify(results, null, ' ');

 

出力


[{
  "name": "users",
  "parent": null,
  "child": [
      { "name": "distalx",
        "parent": "users",
        "child": [
            { "name": "documents",
              "parent": "distalx",
              "child": [
                  { "name": "javascript",
                    "parent": "documents",
                    "child": []
                  },
                  { "name": "funjs",
                    "parent": "documents",
                    "child": []
                  },
                  { "name": "functions",
                    "parent": "documents",
                    "child": []
                  }
              ]
            },
            { "name": "music",
              "parent": "distalx",
              "child": []
            },
            { "name": "desktop",
              "parent": "distalx",
              "child": []
            }
        ]
      },
      {
        "name": "guest",
        "parent": "users",
        "child": []
      },
      {
        "name": "shared",
        "parent": "users",
        "child": []
      }
  ]
}]
 

Javascriptでの再帰を使用したフィボナッチシーケンス

// Returns the nth number in the Fibonacci sequence
function fibonacci(n) {
    if (n === 1 || n === 0) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
 

Javascriptで配列から要素のすべての組み合わせを取得

function getCombinations(params, combinationsResults){
    if(params.length == 0) return combinationsResults;
    var head = params[0];
    var tail = params.slice(1);
    var combinationsResultsCurrent = [];
    if(Array.isArray(head)){
        _.uniq(head).forEach(function(item){
            if(combinationsResults.length == 0){
                combinationsResultsCurrent.push(item);
            } else {
                combinationsResults.forEach(function(previousResultItem){
                    combinationsResultsCurrent.push(previousResultItem.concat([item]));
                });
            }
        });
    } else {
        if(combinationsResults.length == 0){
            combinationsResultsCurrent.push(head);
        } else {
            combinationsResults.forEach(function(previousResultItem){
                combinationsResultsCurrent.push([previousResultItem].concat([head]));
            });
        }
    }
    return getCombinations(tail, combinationsResultsCurrent);
 

例:

INカラスを使用したクエリがあるとします。

SELECT * FROM custom_table WHERE user_id = 'user1' AND location IN ('home', 'work', AND date IN ('2017-01-10', '2017-01-11'))
 

IN条件なしでクエリを生成するために、パラメータのすべての組み合わせを取得したいとします。

SELECT * FROM custom_table WHERE user_id = [value for user_id] AND location = [value for possible location] AND date = [value for possible date]
 

同等のクエリに対して可能なすべてのパラメータの組み合わせを得るために、上記の関数を実行することができます:

var params = ['user1', ['home', 'work'], ['2017-01-10', '2017-01-11']];
 

C / C ++での再帰によるバイナリ検索ツリーの値の検索

バイナリ検索ツリー(BST)ノードの構造:

struct node {
    int data;
    node * left;
    node * right;
}
 

検索アルゴリズム

// Check if a value exists in the tree
bool BSTSearch(node * current, int value)
{
    if (current->data == value)
    {
        return true;
    }
    else if (current->data < value)
    {
        if (current->left == NULL)
        {
            return false;
        }
        else
        {
            return BSTSearch(current->left, value);
        }
    }
    else if (current->data > value)
    {
        if (current->right == NULL)
        {
            return false;
        }
        else
        {
            return BSTSearch(current->right, value);
        }
    }
}