RecursionAan de slag met recursie


Opmerkingen

Recursie verwijst naar iets dat op zichzelf wordt gedefinieerd. In de context van programmeren is het ofwel het gebruik van functies die zichzelf noemen of recursieve typen.

Recursieve functies

Een recursieve functie bestaat uit twee delen:

  • Een of meer basisgevallen
  • Een recursieve stap

Omdat een recursieve functie zichzelf aanroept, zou de reeks functieaanroepen voor altijd kunnen doorgaan. Om er zeker van te zijn dat de functie base cases moet worden opgenomen. Deze vertellen de functie wanneer een waarde moet worden geretourneerd in plaats van een andere recursieve aanroep uit te voeren. Meestal zullen recursieve functies hun invoer vergelijken met het basisgeval en terugkeren als het basisgeval is bereikt. Als het basisgeval niet is bereikt, gaat de functie door naar de recursieve stap.

De recursieve stap is wanneer een functie zichzelf aanroept. Veel recursieve functies retourneren een berekening die is uitgevoerd op het resultaat van de recursieve aanroep. Het Fibonacci-reeksvoorbeeld toont dit aan. Die functie roept zichzelf twee keer recursief op en retourneert vervolgens de som van de resultaten van die oproepen

Een veelgebruikt gebruik voor recursie is navigeren en berekeningen uitvoeren op grote gegevensstructuren zoals bomen en grafieken. Dit werkt goed omdat recursie het probleem afbreekt om kleinere problemen op te lossen en voortbouwt op die oplossingen om het grotere probleem op te lossen. Een ander algemeen gebruik voor recursie is het uitvoeren van iteratieve bewerkingen (looping) in talen (meestal functionele talen) die geen ingebouwde looping-structuren hebben.

Recursieve typen

Een recursief type is een type waarvan de waarden zijn samengesteld uit waarden van hetzelfde type, of anders geformuleerd: een recursief type wordt op zichzelf gedefinieerd. Een lijst is bijvoorbeeld een recursief type omdat elke subset van de lijst zelf een lijst is. Bomen zijn een ander voorbeeld, omdat knopen uit een boom worden verwijderd, blijft het resterende construct een boom.

Formeel wordt de set waarden van een recursief type, T , gedefinieerd door een recursieve setvergelijking op de vorm:

T = ... T ...

Een recursieve setvergelijking kan veel oplossingen hebben, maar een dergelijke vergelijking heeft altijd de minste oplossing die een subset is van elke andere oplossing.

Beschouw als een praktisch voorbeeld deze Haskell-definitie voor een lijsttype,

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

wat betekent dat een lijst met a 's hetzij een lege lijst of nadelen cel met een' a "(de 'kop' van de lijst) en de andere lijst (de 'staart').

Controleren op palindromen met recursie in 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;
    }
}
 

Maak een hiërarchiestructuur met behulp van recursie [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, ' ');

 

uitgang


[{
  "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": []
      }
  ]
}]
 

Fibonacci-reeks met behulp van recursie in 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);
    }
}
 

Download alle combinaties van elementen van arrays in 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);
 

voorbeeld:

Stel dat we een vraag hebben met IN-caluses:

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

AND wil graag alle combinaties van parameters krijgen om query's te genereren zonder IN-voorwaarden:

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

Om alle mogelijke combinaties van parameters voor gelijkwaardige query's te krijgen, kunnen we de functie hierboven uitvoeren:

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

Zoeken naar een waarde in een binaire zoekboom met recursie in C / C ++

Structuur voor Binary Search Tree (BST) knooppunten:

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

Zoek algoritme

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