申論 4考慮以下兩個互相呼叫（mutually recursive）的C 語言函式：int foo(int n) {if (n <= 1) return 1;return foo(n - 1) + bar(n - 1) + 2;}int bar(int n) {if (n <= 1) return 1;return foo(n - 1) + bar(n - 1);}請回答下列問題：（每一小題請寫出推導過程，無推導過程不予計分。）㈠當執行foo(10)時，一共會呼叫foo()函式幾次（包含最外層foo(10)的這一次呼叫）？（10 分）㈡執行foo(10)的最終回傳結果為何？（10 分）㈢以Big-O 表示foo(n)的時間複雜度（time complexity）。本題若同一個「函式與參數」組合被呼叫多次，每次都重新計算，不會儲存先前的計算結果供之後使用。（5 分）