Diberikan fungsi rekursif eksponensiasi berikut:
function f(x, y: integer): integer;
begin
if (y = 0) then f := 1
else if (y mod 2 = 1) then f := x * f(x, y – 1)
else f := f(x, y div 2) * f(x, y div 2);
end;
Jika fungsi tersebut dipanggil dengan f(4, 9), berapa KALI fungsi ‘f’ dipanggil secara total (termasuk pemanggilan pertama)?
Ini adalah modifikasi dari algoritma ‘Fast Exponentiation’. Untuk menghitung jumlah pemanggilan fungsi, kita dapat menggambar Tree Rekursi. f(4, 9) akan bercabang tergantung apakah y ganjil atau genap. Jika genap, ia bercabang 2. Jika ganjil, ia memanggil y-1. Menelusuri seluruh pemanggilan pada call stack memberikan total 24 kali pemanggilan.