Chapter 8 uses recursive function to write a tree. I would like to point out that deep recursive function is an inefficient algorithm and programmer should avoid this.
See the following code of calculating n-th Fibonacci number:
int recursiveFib(n) {
if (n == 1 || n == 2) {
return 1;
} else {
return recursiveFib(n - 1) + recursiveFib(n - 2);
}
}
int loopFib(n) {
int fib_1 = 1;
int fib_2 = 1;
for (int i = 3; i < n + 1; i++) {
int temp = fib_1 + fib_2;
fib_1 = fib_2;
fib_2 = temp;
}
return fib_2;
}
Map<int, int> memory = {1: 1, 2: 1};
int recursiveFibwithMemory(int n) {
if (!memory.containsKey(n)) {
memory[n] = recursiveFibwithMemory(n - 1) + recursiveFibwithMemory(n - 2);
}
return memory[n] as int;
}
final programList = [recursiveFib, loopFib, recursiveFibwithMemory];
int n = 30;
for (int i = 0; i < programList.length; i++) {
final stopwatch = Stopwatch();
stopwatch.start();
programList[i](n);
stopwatch.stop();
print("${i + 1}th program runtime is ${stopwatch.elapsedMicroseconds}");
stopwatch.reset();
}
// output:
// 1th program runtime is 11625
// 2th program runtime is 147
// 3th program runtime is 545
Explanation
The first program is a recursive function. The second program is using a loop. The third program optimize the recursive function using memoization. See below for more explanation.
Why recursive function is so slow?
This is because the lower n value is re-calculated a large amount of times.
What is the rescue?
Usually you can re-write a recursive function as a loop. It looks awkward and not so clean as the recursive version. But it is much faster.
Another way is to use an optimization technique called memoization. The concept is simple: just store the calculated value in a table. When the program needs the value again, look up from the table instead of calculating again. In practice, this can speed up the runtime of recursive function tremendously.
In the example above, the calculated values are stored in the map memory. Every time the program needs a calculated value. The program can look up from the map directly. You may not feel comfortable in using a global variable. You can do the same trick by using a class or closure.
Other programming language has memoization feature built-in. For example, Python has a lru_cache function in the functools module that can be used as a decorator. I do not know how to write a similar function in Dart because a decorator needs to make use of the Python language feature *args and **kwargs that can capture all the positional and keyword arguments. Dart don’t has such language feature. But still, you can use a class in Dart as the memory table in memoization.
Very nice! Thank you for that detailed analysis. This is good timing because I had been planning to do some more research on recursion for an upcoming update on the Data Structures and Algorithms in Dart book.
I’m in middle of writing a new chapter on recursion for Data Structures & Algorithms in Dart, so after doing more research I’ve come back here to have another look at your warning.
I agree that what you said was very valid for the unoptimized recursive Fibonacci algorithm, because as you said, it is repeating a lot of unnecessary work (which memoization or a simple loop can help with). The unoptimized algorithm has a time complexity of O(2^n), which is terrible.
However, you said:
Chapter 8 uses recursive function to write a tree. I would like to point out that deep recursive function is an inefficient algorithm and programmer should avoid this.
This seems to imply that the algorithm used in Chapter 8 would be equally bad to the unoptimized recursive Fibonacci algorithm. However, I don’t see that to be the case.
Here is the algorithm from Chapter 8 again for reference:
Node<E>? createTree<E>(List<E> nodes, [int index = 0]) {
if (index >= nodes.length) return null;
final node = Node(nodes[index]);
final leftChildIndex = 2 * index + 1;
final rightChildIndex = 2 * index + 2;
node.leftChild = createTree(nodes, leftChildIndex);
node.rightChild = createTree(nodes, rightChildIndex);
return node;
}
Here are the reasons I still think recursively building a tree is a valid algorithm:
The time complexity is O(n), which is decent, nothing near the terrible O(2^n) time complexity for Fibonacci. The createTree function visits each element only once, so no extra work is being done.
The space complexity is also O(n), mainly because of list you pass in as a parameter. The space complexity of the recursive call stack is O(log n) for a balanced tree (better than O(n)), but even in the worst case (for a completely unbalanced tree), it is still only O(n). So overall the space complexity is O(n).
If you wanted to rewrite the function using a loop rather than with recursion, you would need to use a queue or a stack to keep track of your position in the tree. The code for that is more complex than the recursive version since recursion uses the built-in call stack. Also, the loop would still have a time and space complexity of O(n).
When working with tree data structures (even large ones), I still think that recursion is a good approach. If I’m missing something, though, I’d like to hear about it.
Hi I just finished the whole book and browse around the forum. @suragch thank you for your explanation. Your consideration on complexity is what I have missed here. I agree with what you say actually.
I somewhere remember that I have learnt complexity in a Coursera course but just give back these to the teachers in Rice university. The reason may be I really not learning so deep in the topic and only touch on the surface.
Are you going to update the data structure and algorithm book to second edition? Although I have bought the first edition, I still not having time to read yet.
In the mean time I would probably learn some flutter development and see what it look like. May be I wait for your second edition come out and will have a look.
Yes, the second edition of Data Structures & Algorithms in Dart should be out in a few months. Besides the new chapter on recursion, I’m not expecting any major changes to the content of the book, so you are fine reading the one you have. I don’t think recent changes to the Dart language affect it much. Of course, if you want to wait and read the new edition, that would be helpful to me for any problems you find with it.
I think that would be a good idea to learn some Flutter. In my opinion, the best way to learn Flutter and Dart is to just begin building something that you want to make.