# Recursie

Recursie in programmeren is een techniek waarbij een functie zichzelf aanroept. Deze zal zichzelf herhalen tot er een zekere voorwaarde is bereikt.

Opgelet

Een recursieve functie moet een conditie bevatten om oneindige recursie (Eng. infinite recursion) te vermijden.

Een recursieve functie voert dus een bepaalde code uit en voert de functie vervolgens opnieuw uit, tenzij aan een exit-voorwaarde wordt voldaan. Dit klinkt gelijkaardig aan een for of while-loop, we kunnen dan ook loops steeds vervangen door een recursie-patroon.

# Wanneer recursie gebruiken?

Recursie is een krachtige oplossing om complexe problemen op te lossen maar kan onnodig complex zijn. Je zal het voornamelijk nodig hebben in volgende situaties:

Als het gaat om het doorlopen of sorteren van boomstructuren (knooppuntrelaties)
Als je merkt dat je lussen eindeloos in lussen begint te nestelen.

# Voorbeelden

# Aftellen naar 0

# For-loop

Een for-loop is voor dit eenvoudig probleem voldoende.

function countdown(num) {
  for (let i = num; i > 0; i--) {
    console.log(i);
  }
}

countdown(3); // 3 2 1

1
2
3
4
5
6
7

# Recursie

function recursiveCountdown(num) {
  if (num === 0) {
    return;
  }
  console.log(num);
  recursiveCountdown(num - 1);
}

recursiveCountdown(3); // 3 2 1

1
2
3
4
5
6
7
8
9

In dit voorbeeld declareren we eerst onze exit-voorwaarde if (num === 0). Als niet aan deze voorwaarde wordt voldaan, slaan we deze over. num wordt deze naar de console afgedrukt en wordt de functie opnieuw aangeroepen met een uitgebreid argument (num — 1).

recursiveCountdown(3) // first call (num = 3)
  recursiveCountdown(2) // second call (num = 3 – 1)
    recursiveCountdown(1) // third call (num = 2 – 1)
      recursiveCountdown(0) // last call (num = 1 – 1)
      return                   since num = 0, condition is met
                               and the function exits.

1
2
3
4
5
6

# Som van getallen tussen 1 en …

# For-loop

Opnieuw hebben we een voorbeeld waarbij recursie niet nodig is om ons probleem te bereiken. Een lus zal in dit geval aan onze eisen voldoen.

function rangeSum(num) {
  let total = 0;

  for (let i = num; i > 0; i--) {
    total += i;
  }

  return total;
}

rangeSum(3); // 6

1
2
3
4
5
6
7
8
9
10
11

# Recursie

function recursiveRangeSum(num, total = 0) {
  if (num <= 0) {
    return total;
  }

  return recursiveRangeSum(num - 1, total + num);
}

recursiveRangeSum(3); // 6

1
2
3
4
5
6
7
8
9

recursiveRangeSum(3) // defaults to recursiveRangeSum(3, 0)
  recursiveRangeSum(2, 3) // recursiveRangeSum(3 - 1, 0 + 3).
    recursiveRangeSum(1, 5) // recursiveRangeSum (2 - 1, 3 + 2)
      recursiveRangeSum(0, 6) // recursiveRangeSum(1 - 1, 5 + 1)
                                 num = 0 so the function returns 6

1
2
3
4
5

# Stamboom

We beschouwen onderstaande stamboom:

const tree = {
  name: "John",
  children: [
    {
      name: "Zoe",
      children: [],
    },
    {
      name: "Bob",
      children: [
        {
          name: "Joe",
          children: [],
        },
        {
          name: "Eloise",
          children: [],
        },
      ],
    },
  ],
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

We willen een lijst krijgen van alle kinderen in deze stamboom. We beginnen met John wie twee kinderen heeft: Zoe en Bob. Zoe heeft geen kinderen, maar Bob heeft er twee: Joe en Eloise. Deze hebben allebei geen kinderen.

Onze lijst met kinderen zou zijn: Zoe, Bob, Joe, and Eloise.

# For-loop

Om dit om te lossen met lussen, moeten we een loop in een loop schrijven. Maar hoeveel keer zullen we deze loop moeten uitvoeren? In dit geval zouden we het kunnen achterhalen omdat we de stamboom kunnen zien. Maar wat als Joe toch kinderen zou hebben?

# Recursie

function printChildren(obj) {
  if (obj.children.length === 0) {
    return;
  }

  obj.children.forEach((child) => {
    console.log(child.name);
    printChildren(child);
  });
}

printAllChildren(tree); // Zoe Bob Joe Eloise

1
2
3
4
5
6
7
8
9
10
11
12

Uitleg:

```
printAllChildren(tree)
```
1
De eerste node is ‘John’, hij heeft twee kinderen (tree.children.length === 2), bij zowel ‘Zoe’ als ‘Bob’ zal de log worden uitgevoerd en wordt de functie opnieuw opgeroepen.
- ```
  printAllChildren({
  name: "Zoe",
  children: [],
  })
```
  1
  2
  3
  4
  Het object van Zoe wordt doorgegeven maar Zoe heeft geen kinderen dus de functie zal stoppen.
- ```
 printAllChildren({
     name: "Bob",
     children: [
         {
         name: "Joe",
         children: [],
         },
         {
         name: "Eloise",
         children: [],
         },
     ],
     })
```
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  Het object van Bob wordt doorgegeven maar en Bob heeft twee kinderen dus de functie zal uitgevoerd worden. Hij zal voor ieder kind de naam loggen en vervolgens hun object meegeven.
  - ```
          printAllChildren({
              name: "Joe",
              children: [],
          })
```
  1
  2
  3
  4
  Het object van Joe wordt doorgegeven maar Joe heeft geen kinderen dus de functie zal stoppen.
- ```
        printAllChildren({
            name: "Eloise",
            children: [],
        })
```
    1
    2
    3
    4
    Het object van Eloise wordt doorgegeven maar Eloise heeft geen kinderen dus de functie zal stoppen.

Arrow vs. Function Oefeningen