Drzewo wywołań funkcji – Wikipedia, wolna encyklopedia

Ten artykuł od 2017-06 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Drzewo wywołań funkcji (ang. call tree) – drzewo przedstawiające proces obliczania wartości wyrażenia. Liście drzewa wywołań zawierają niepodzielne części wyrażenia, czyli stałe i zmienne. Węzły wewnętrzne i korzeń odpowiadają wywołaniu funkcji (lub operatorów) z argumentami obliczonymi przez ich poddrzewa.

Drzewa wywołań rozpatruje się przede wszystkim w konstrukcji kompilatorów języków programowania, ale także w analizie programów (ang. program analysis), oraz w konstrukcji i analizie algorytmów. Najczęściej używa się takich drzew dla wyrażeń, które zawierają wywołania funkcji, lub drzewa dla obliczania wartości funkcji rekurencyjnych.

W typowych językach programowania wyrażenia mogą generować skutki uboczne. Zazwyczaj drzewo wywołań nie uwzględnia tego faktu i obrazuje jedynie strukturę obliczania. Szczególnie interesujące są drzewa wywołań dla funkcji rekurencyjnych nieposiadających skutków ubocznych. Drzewa takie można przekształcić zwykłymi metodami matematycznymi (zob. np. programowanie dynamiczne) w skierowany graf acykliczny (DAG), co umożliwia optymalizację.

Przykład[edytuj | edytuj kod]

Jako przykład rozważmy drzewo wywołań dla funkcji ${\displaystyle F}$ obliczającej wartość n-tego wyrazu ciągu Fibonacciego:

 fun F (n :int) :int =       if n=1 or n=2 then 1      else F (n-1) + F (n-2) 

Diagram po prawej stronie prezentuje drzewo wywołań dla wyrażenia ${\displaystyle F(6).}$ Dla uproszczenia pominięto tu wartości wyrażeń pośrednich, pokazując jedynie wywołania funkcji. Łatwo zauważyć, że drzewo to zawiera wiele zbędnych obliczeń, na przykład ${\displaystyle F(2)}$ jest obliczane pięciokrotnie a ${\displaystyle F(3)}$ trzykrotnie, pomimo tego, że wartość funkcji dla zadanych parametrów jest zawsze taka sama.

Kolejny diagram pokazuje jak powyższe drzewo może zostać zredukowane do grafu skierowanego za pomocą technik typu programowanie dynamiczne lub memoizacja.