Functional JS w/Recursive Functions

Question

Alright, I realize this is probably very beginner-ish for many of you on here, but I'm hoping someone can explain this in a way I can wrap my head around. My question centers around what I've heard is the basis for functional JavaScript - recursion. I was working on a personal project, and found a great use case for one, but I still don't quite get what's going on - need a visual way of thinking through it.

So, here's an example. The problem that's being solved is a simple helper function to find the next sibling in the DOM matching a specific tagname (assume the current element and tagname are passed in when calling the function, i.e. findSibling(this, 'DIV')).

var findSibling = function(el, tagName) {
  if (el.nextSibling.tagName === tagName.toUpperCase())
    return el.nextSibling;
  else
    return findSibling(el.nextSibling, tagName);
}

Ok, so this works! Great! But, it took me forever to land here, and it really shouldn't have. I tried whiteboarding it out, the best I can understand is that something like this is happening:

findSibling(<span>, div) ▸ findSibling(<span>, div) ▸ findSibling(<span>, div) ▸ <div>

Assuming we have HTML something like this:

<div></div>
<span></span>
<span></span>
<span></span>
<div></div>

Can anyone help me visualize this a bit more? Any tips/tricks that you may have used when first learning this concept? I'm just looking for that lightbulb...

Also, the one thing I was stuck on for awhile was the second return statement. Why can't I just call the function in the else? Why do I need the return? Seems like it would just call the function with the sibling element.

Thank you!

<head> Explanation </head>

Abraham Hamidi
– Abraham Hamidi

2014-02-15 03:55:48 +00:00
Commented Feb 15, 2014 at 3:55 — Abraham Hamidi
– Abraham Hamidi, Commented Feb 15, 2014 at 3:55

David Stanley · Accepted Answer · 2014-02-15 04:12:40Z

To explain your second question first, let's rewrite your function a little:

var findSibling = function(el, tagName) {
    var match;
    if (el.nextSibling.tagName === tagName.toUpperCase()) {
        match = el.nextSibling;
    } else {
        match = findSibling(el.nextSibling, tagName);
    }
    return match;
}

Both returns in your original code are doing the same thing, returning the tag you're searching for. What's different in each case is how that match is calculated.

To answer your first question, let's look at your code in a different way. Anytime you have a function, you can always replace the function call with the code of the function, with parameters properly replaced. For example:

function hello(text) {
    alert('Hello ' + text);
}
hello('to you.');

is the equivalent to

alert('Hello to you.');

So let's do this with your recursive function:

if (el.nextSibling.tagName === tagName.toUpperCase()) 
    return el.nextSibling;
else 
    if (el.nextSibling.nextSibling.tagName === tagName.toUpperCase()) 
        return el.nextSibling.nextSibling;
    else 
        if (el.nextSibling.nextSibling.nextSibling.tagName === tagName.toUpperCase()) 
            return el.nextSibling.nextSibling.nextSibling;
        else 
            etcetera...

From this you should be able to see how a recursive function hides a loop in itself. This also shows the danger of recursive functions - that they can keep calling themselves without end. Which leads me to wonder - what will happen to your function if el doesn't have a nextSibling?

Thanks. I think I get it, and I appreciate the time you took to answer in an easy to understand way.

ltalhouarne · Accepted Answer · 2014-02-15 04:01:58Z

1

I like to think as recursion as the mirror effect or the Droste effect, based on the following picture:

enter image description here

Where each level digs deeper into the next one until it reaches a limit. In your case, find the sibling with the desired tag name.

So essentially your base code is the first picture, and the first recursion is the first level. It will go a level deeper until it reaches its goal.

answered Feb 15, 2014 at 4:01

ltalhouarne

4,6382 gold badges25 silver badges32 bronze badges

Comments

Community · Accepted Answer · 2017-04-12 07:31:21Z

Can anyone help me visualize this a bit more? Any tips/tricks that you may have used when first learning this concept?

Maybe thinking of an iterative version would help understand:

function findSibling(el, tagName) {
  while (el = el.nextSibling) {
    if (el.tagName == tagName.toUpperCase()) {
      return el;
    }
  }
}

Also, the one thing I was stuck on for awhile was the second return statement. Why can't I just call the function in the else? Why do I need the return?

A recursive function as general rule will have a recursive call and an exit condition. The definition itself is recursive. In your code the exit condition is finding the tagName.

Explaining recursion is hard if you don't understand recursion. The Wikipedia has a good explanation with visualization. http://en.wikipedia.org/wiki/Recursion

Edit: See this question too https://softwareengineering.stackexchange.com/questions/25052/in-plain-english-what-is-recursion

Julian · Accepted Answer · 2014-02-15 04:23:28Z

1

You call a function findSibling to find 'tag'
   But it doesnt find tag so it calls function findSibling to find 'tag'
       But it doesnt find tag so it calls function findSibling to find 'tag'
           But it doesnt find tag so it calls function findSibling to find 'tag'
               It retrns tag to its caller
           It returns tag to its caller
       It returns tag to its caller
   It returns tag to its you.
You have tag.

I think the best you can understand is the correct answer to this particular problem. To find something in a nested DOM is only slightly more complex to think about but its the same concept... and almost the same code.

edited Feb 15, 2014 at 4:23

answered Feb 15, 2014 at 4:08

Julian

5002 silver badges11 bronze badges

Collectives™ on Stack Overflow

Functional JS w/Recursive Functions

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related