Recursivitate de coadă

  • 2 minute de citit
  • 4 exemple de cod
  • 2 imagini

Disponibil și în English

Pe această pagină

Salut tuturor! 👋

Articolul de astăzi va fi despre recursivitatea de coadă, o tehnică ce permite optimizarea anumitor funcții recursive.

Introducere

Pe scurt, de fiecare dată când scrii o funcție recursivă, fiecare apel nou al acesteia alocă un cadru (frame) pe stivă. De exemplu, să luăm următoarea funcție:

        private static long RecursiveFib(long n)        {            if (n <= 1)            {                return n;            }            return RecursiveFib(n - 1) + RecursiveFib(n - 2);        }

Dacă setăm un breakpoint la return n și apelăm funcția cu RecursiveFib(10), vom obține următorul cadru de stivă. Există 10 intrări în cadrul de stivă.

Fiecare apel recursiv al RecursiveFib() depinde de cel anterior, iar programul trebuie să adauge un nou cadru de stivă pentru a reține apelurile vechi. Procesul de adăugare a unui nou cadru de stivă durează puțin timp, iar dacă programul tău are nevoie de multe dintre ele, s-ar putea să întâlnești o eroare de Stack Overflow.

Dacă măsurăm RecursiveFib(40) obținem aproximativ 4986853 tick-uri scurse.

Versiunea iterativă

Poți rescrie funcția într-o manieră iterativă, folosind o buclă și uneori o stivă. Buclele pot fi apoi optimizate și mai mult de compilator, folosind o tehnică numită Loop Unrolling.

Versiunea iterativă a lui RecursiveFib arată astfel.

        private static long IterativeFib(long n)        {            var a = 0L;            var b = 1L;            if (n == 0)            {                return a;            }            for (var i = 1; i < n; i++)            {                var c = a + b;                a = b;                b = c;            }            return b;        }

În versiunea iterativă, stiva lui IterativeFib(10) are doar 2 intrări.

Măsurătoarea pentru IterativeFib(100) arată 19 tick-uri scurse, adică ~26246594% mai rapid decât versiunea recursivă RecursiveFib(40), iar nu vom primi nicio eroare de stack overflow.

Recursivitate de coadă

Recursivitatea de coadă este asemănătoare recursivității obișnuite, dar în loc să folosească stiva, compilatorul va folosi regiștrii. Se realizează scriind funcția astfel încât apelul recursiv nu depinde de apelul anterior. De obicei va trebui să adaugi parametri suplimentari la semnătura funcției pentru a păstra datele.

        private static long TailRecursiveFib(long n, long a , long b )        {            return n switch            {                0 => a,                1 => b,                _ => TailRecursiveFib(n - 1, b, a + b)            };        }

Măsurătoarea pentru TailRecursiveFib(100, 0 ,1) arată 21 tick-uri scurse, ceea ce este foarte aproape de versiunea iterativă.

Concluzie

Recursivitatea de coadă este o tehnică de rescriere a unei funcții recursive astfel încât noul apel recursiv să înlocuiască cadrul de stivă curent, fără a adăuga unul nou.

Mulțumesc că ai citit și sper că ai învățat ceva! 🍻

Fragment complet de cod
using System;using System.Diagnostics;namespace TailRecursion{    static class Program    {        private static long TailRecursiveFib(long n, long a , long b )        {            return n switch            {                0 => a,                1 => b,                _ => TailRecursiveFib(n - 1, b, a + b)            };        }                private static long RecursiveFib(long n)        {            if (n <= 1)            {                return n;            }            return RecursiveFib(n - 1) + RecursiveFib(n - 2);        }        private static long IterativeFib(long n)        {            var a = 0L;            var b = 1L;            if (n == 0)            {                return a;            }            for (var i = 1; i < n; i++)            {                var c = a + b;                a = b;                b = c;            }            return b;        }        private static void Main(string[] args)        {            var st = new Stopwatch();            var r = new Random();            for (var i = 0; i < 5; i++)            {                RecursiveFib(i);                IterativeFib(i * 10 );                TailRecursiveFib(i * 10, 0, 1);            }            long result = 0;            st.Restart();            // result = RecursiveFib(10);            result = TailRecursiveFib(100, 0, 1);            // result = IterativeFib(100);            st.Stop();            Console.WriteLine("Elapsed ticks: {0}", st.ElapsedTicks);            Console.WriteLine(result);        }    }}