Lepší rekurze s optimalizací Tail Call

Jednoho krásného dne v Kraji se Bilbo Pytlík učí programování a cvičí rekurze.

Napsal tento kód

const fact = (num) =>{
  if(num === 1) return 1; // non-recursive base case
  return n * fact(n-1); // recursive part
}

Tak to spustil, s 3 a 4 to fungovalo dobře.
Ale tento zvědavý hobit s hlavou chce zkontrolovat, jak dlouho to může jít.
Zadal vstup 100 000 a

RangeException:
Maximum stack size exceeded

Běžel hledat pomoc od Gandalfa, pak mu moudrý čaroděj vysvětlil, jak zásobníky fungují.

Whenever you call a function then it pushes a new frame on to the stack and once the operation of that frame is done then it is removed from the stack

Výše uvedený kód pro vstup "4" by se tedy přeložil do tohoto

Protože ram má omezenou velikost a při každém spuštění programu alokuje malou část. S ohledem na toto omezení, když spustíte stejný kód se vstupem "100000", délka zásobníku se zvětší a nakonec dosáhne bodu, kdy do něj nebude možné přidat žádné nové snímky.

A teď se Bilbo ptá Master can we not optimize it?

Šedý kouří dýmku a říká Of course my old friend!

Optimalizace Tail Call
If the last thing a routine does before it returns is call another routine, rather than doing a jump-and-add-stack-frame immediately followed by a pop-stack-frame-and-return-to-caller.
Tail call optimization reduces the space complexity of recursion from O(n) to O(1). Our function would require constant memory for execution. It does so by eliminating the need for having a separate stack frame for every call.

Gandalf tedy kód přepsal

 const fact = (num,acc = 1) => {
     if(num === 1) return acc;
     return fact(n-1,acc * n);
 }

Zobrazení zásobníku nyní vypadá nějak takto

Kdykoli zde zavoláte funkci fact místo přidání nového rámce do zásobníku, rám se ze zásobníku odstraní, protože je to poslední věc, kterou lze udělat.