RecursionRecursion入门


备注

递归是指根据自身定义的东西。在编程环境中,它是使用自称函数或递归类型的实践。

递归函数

递归函数有两个部分:

  • 一个或多个基本案例
  • 递归步骤

因为递归函数调用自身,所以函数调用字符串可以永远继续。为了确保函数终止必须包含基本情况。这些将告诉函数何时返回值而不是执行另一个递归调用。通常,递归函数将检查它们对基本情况的输入,并在达到基本情况时返回。如果尚未到达基本情况,则该函数将进入递归步骤。

递归步骤是函数调用自身的时间。许多递归函数将返回对递归调用的结果执行的一些计算。 Fibonacci序列示例证明了这一点。该函数递归调用自身两次,然后返回这些调用的结果总和

递归的一个常见用途是在大型数据结构(例如树和图形)上导航和执行计算。这很有效,因为递归可以解决问题并解决较小的问题,并以解决更大问题的解决方案为基础。递归的另一个常见用途是在没有内置循环结构的语言(通常是函数语言)中执行迭代操作(循环)。

递归类型

递归类型的值是由相同类型的值组成的,或者表达方式不同:递归类型是根据自身定义的。例如,列表是递归类型,因为列表的每个子集本身都是一个列表。树是另一个例子,因为节点从树中移除,剩下的构造仍然是树。

形式上,递归类型T的值集将由表单上的递归集方程式定义:

T = ...... T ...

递归集方程可以有许多解,但是这样的方程总是具有最小解,其是每个其他解的子集。

作为一个实际例子,考虑这个Haskell定义的列表类型,

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

这意味着列表a的或者是一个空列表或含有一个cons单元' 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中使用递归的Fibonacci序列

// 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 caluses的查询:

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);
        }
    }
}