### re: Building a Simple Virtual DOM from Scratch VIEW POST

re: Cool! So, I see the use of recursion in the code (diff() calls diffChildren(), which calls diff()), and once I started looking for the worst case, ...

Sure. You have stepped into the common trap of thinking recursion recursively. Your brain will stack-overflow first before the computer does haha.

The reason why you are so confused is because you are lacking the "leap of faith" for recursion. You try to figure out what is happening, then you look into the function; it calls itself, and u look into the function again... Then you are lost.

All you need is faith!

The first thing is to define what `diff` and `diffChildren` do. I made it very clear for `diff`.

Imagine we have a function `diff (oldVTree, newVTree)` which calculate the differences between the two virtual trees; return a `patch(\$tree)` function that takes in the real DOM of `oldVTree` and perform appropriate operations to the real DOM to make the real DOM looks like `newVTree`.

So the idea is, you know `diff` will somehow call itself again at some point. And when this happens, all you need is the "leap of faith"; believe that `diff` will work as you wish! Don't look into `diff` again to try to figure things out! Just think about what `diff` should do and return. By our definition, it will return a `patch`! So just assume the recursive calls to `diff` will work and read on.

Teaching recursion using this example is a bit hard, have a look at this article which I explained very clearly how you could obtain faith in recursion.

The leap of faith takes some practice to get use to it. If you want some exercise, I am happy to give you some challenge and guide you through them. Feel free to DM me on twitter: @ycmjason

First off, five points for the funny poster! 🤭🤗

Now, I do have some experience with recursion, and I understand that one shouldn't try to trace it all the way down the rabbit hole, but this is just not done:

Don't look into diff again to try to figure things out! Just think about what diff should do and return. By our definition, it will return a patch!

The example you linked to didn't help me too much, for some reason. Can you please point out what the base case in this `diff` function is? 🤔

I am sorry that my explanation didn't help. :(

`diff` has two base cases:

1. If the new node is `undefined`
2. If the new and old nodes are of different types. This could be either of the cases below:
1. one of the node is a TextNode while the other one is an ElementNode
2. Both are ElementNode but with different tag.

In fact, all my base cases are defined in a guard clause. This means that all the return statement before the last return can be considered as base case.

Oops, I just realised there is one more, which is when there is no children in the node. But I didn't explicitly deal with that case as it will be automatically dealt with in the for loop in `diffChildren`

I am sorry that my explanation didn't help. :(

That's because the (I forget the name of the linked example . . . `flatten()?`) the second example is just a single function calling itself, whereas in the vDOM case, we have `diff` calling `diffChildren` calling `diff`, and so on, so it's harder to reason about.

This means that all the return statement before the last return can be considered as base case.

I see that, and what I did this time was write out a two-depth example and trace it by hand. My head still went for a spin, but I kind of see how this is supposed to work. I think I'll leave it at that for now. 😇

Now, on to a really important question: did you write this code simply based on the "leap of faith"? Is this how algorithms like merge sort and quick were written? On leaps of faith? I'm having a really hard time believing that! Is leap of faith good enough for serious professional/interview problems? 🤔

All said and done, this exercise has reminded me how badly I need to do a course in algorithms, which I'm going to do over the next few days. So, for that, too, thanks a lot! 😇😇

did you write this code simply based on the "leap of faith"?

Yes. Totally based on the leap of faith. It always work! It's the very important thing you need when dealing with recursion.

Is this how algorithms like merge sort and quick were written?

Well, merge sort and quick sort if written in a recursive way, can be reasoned about using the "leap of faith" for sure. Whether or not the original Author has the leap of faith there is noway to find out. 😂😂

Is leap of faith good enough for serious professional/interview problems?

Leap of faith will definitely work in professional and interview problems. It's just a mindset you should have when writing recursive solutions, not really a method. Once you do more recursion, you will become confident enough to hold that faith all time.

Thank you! :-)

code of conduct - report abuse