Sponsored
Sponsored
Iterative Approach: In this approach, we compose the functions iteratively from the last function to the first. This is because function composition works in reverse order, i.e., f(g(h(x))) means first apply h, then g, and finally f. We start with the input value x and apply each function in the function list from right to left.
Time Complexity: O(n) where n is the number of functions.
Space Complexity: O(1) since we are using a fixed amount of extra space.
using System.Collections.Generic;
class Program {
static int ComposeFunctions(List<Func<int, int>> functions, int x) {
for (int i = functions.Count - 1; i >= 0; i--) {
x = functions[i](x);
}
return x;
}
static void Main() {
var functions = new List<Func<int, int>> {
x => x + 1,
x => x * x,
x => 2 * x
};
int x = 4;
Console.WriteLine(ComposeFunctions(functions, x));
}
}This C# solution defines a list of Func delegates. It iterates over the functions from the last to the first, applying them to the input value x.
Recursive Approach: This approach encapsulates the recursive function composition in a way that it applies the last function first and makes a recursive call to apply the rest. We either call the next composed function recursively until the base case, i.e., no functions left, is reached, or upon an empty function list, return the input as it is simply the identity function.
Time Complexity: O(n) where n is the number of functions.
Space Complexity: O(n) due to the recursive call stack.
1#include <iostream>
2#include <vector>
3#include <functional>
4
5int recursiveCompose(std::vector<std::function<int(int)>> &functions, int index, int x) {
6 if (index < 0) return x;
7 x = functions[index](x);
8 return recursiveCompose(functions, index - 1, x);
9}
10
11int main() {
12 std::vector<std::function<int(int)>> functions = {
13 [](int x) { return x + 1; },
14 [](int x) { return x * x; },
15 [](int x) { return 2 * x; }
16 };
17 int x = 4;
18 std::cout << recursiveCompose(functions, functions.size() - 1, x) << std::endl;
19 return 0;
20}This C++ solution applies each function recursively by invoking the composed function of the rest. Base case returns the identity value, mimicking right-to-left function application.