Playing with recursion

README.md

Recursion

It's such a beautiful thing, huh? Recursion basically is returning a another functions result that will eventually lead to the calling function to be called again. That didn't make any sense right? Look at it like this:

function foo(bar){
  if(bar==0){
  return 'bar is at zero!';
  }
  else{
  //we take one away from bar to make it one less and not cause an infinite loop
  return foo(bar-1);
  }
}

Because bar is being subtracted by one every time that foo is called we can be assured that if foo is given a positive integer it will continously subtract one until it hits zero and will then return the string bar is at zero! It takes a little getting used to but this is pretty useful and sometimes neccesary in programming for things that are inside other things.

Example: I have the array

var arr=[
1,
2,
3,
[4,5,6],
7
];

I want to add one to each of the elements but adding 1 wont work in the case of [4,5,6]. A solution using recursion might be:

function addOne( arr ) {
    for ( var i = 0; i < arr.length; i++ ) {
        if ( Array.isArray( arr ) ) {
            arr[ i ] = addOne( arr[ i ] );
        } else {
            arr[ i ] += 1;
        }
    }
    return arr;
}

Now this looks a little messy only because I'm trying to make this as easy as possible to understand if you come from other languages. In ES2016 JavaScript it would look a little more somethig like this:

function addOne( arr ) {
    return arr.map( ( curVal ) => {
        if ( Array.isArray( curVal ) ) {
            return addOne( curVal );
        }
        return curVal + 1;
    } );
}

Looks a little less clunky without the for loop.

Mutual Recursion

Now what you saw was single recursion which can be identified when a function calls itself.

Mutual recursion on the other hand is when two or more functions call and depend on each others results. I included an example of this in mutualrecursion.js

MutualRecursion.js

function isEven( a ) {
    if ( a == 0 ) {
        return true;
    } else {
        return isOdd( a - 1 );
    }
}

function isOdd( a ) {
    if ( a == 0 ) {
        return false;
    } else {
        return isEven( a - 1 );
    }
}
//Compact definition
function isEven( a ) {
    return a == 0 ? true : isEven( a - 1 );
}

function isOdd( a ) {
    return a == 0 ? false : isEven( a - 1 );
}

NormalRecursion.js

function isEven( a ) {
    if ( a == 0 ) {
        return true;
    }
    if ( a == -1 ) {
        return false;
    }
    return isEven( a - 2 );
}

function isOdd( a ) {
    if ( a == 0 ) {
        return false;
    }
    if ( a == -1 ) {
        return true;
    }
    return isOdd( a - 2 );
}
//compact definition
function isEven( a ) {
    return a == 0 ? true : a == -1 ? false : isEven( a - 2 );
}

function isOdd( a ) {
    return a == 0 ? false : a == -1 ? true : isOdd( a - 2 );
}

TheRightWay.js

function isEven( a ) {
  return a % 2 == 0;
}
function isOdd( a ) {
  return a % 2 == 1;
}