Reccursive methods

#reccursive #javascript #mazesolver

Introduction

Hi there, once again my main objective is to share knowledge, code. Feel free to give any kind of feedback and to improve my code in any way you'd think it's better.

This time i'll add some explanation on recursive methods, not just the code itself.

Recursive methods

A recursive method is a method which can at some point call itself in order to simplify a problem into an easy result, which the method itself can then return as response.

Can be a bit confusing at the beginning while trying to implement at different problems, but once
accustomed it's even more logical to use this kind of problem solving.

Without any further delay, let's go straight into recursiveness!

Like everything i learned, i allways learned better when examples are given, so here my example for a problem and we'll solve it with recursiveness (NO CODE AT THIS POINT ).

Problem :

You're a sleepy programmer at work, and you need to get yourself a nice cup of coffee! But the office you're working at it's a complete mess and confusing!

Your objective is to reach the coffee, but how ?
Well, even if this “maze” is simple, my first approach will be “Try it”!
So, i pick a direction and start walking, changing my direction every time i encounter an obstacle.

Some decisions may have been “bad” since i got myself into a no exit situation, BUT i know for my next attempt i'll be better if i just don't go that way again!
That “bad” decision of going in the red path is the one which give me, eventually, my solution !

Now, i want to solve my problem with recursive methods, and let me tell you the approach is very similar!

My method to be recursive should receive an input, do something with it and then return the result.

Let's assume the follow :

So, my recursive method accept, as input, the maze and my current position.

Inside my method i do one of three possible actions:
1- I found a wall, cannot go anywhere, so i return “success” as false so my chained recursive calls receive this info and know it's not the path to take;
2- I found more paths to follow, will follow them by changing my position to the next position of that path and returned the result of method itself being called;
3- I found coffee, much similar as first response i'll return “success” as true so chained recursive calls knows this is the path to take;

Here is where the recursive is implemented, every time i know there is a path to follow, i call the method itself as i was on that path ! The returned result will be eventually true, if the maze is soluble!

Now, let's see some code of the idea:

Link to gist code HERE!!!

What can you find in this gist ? A simple recursive function i made for the purpouse of setting this example.

I gave an already build “maze” which i used in my method tests :

And the recursive method itself :

Underlined in green it's a method (also recursive) that i made that just retrieves all the start points and all the possible end points of a maze !

Underlined in purple is a method which ONLY verify if in the given array there is already the object “pos”, this is used to avoid the recursive method to be going back and forward on the same spots as the method already been.

Underlined in orange there is the recursive maze solver method, just want to point out that it is important to define some “brakes” in our recursive methods (“brakes” = some breakpoints to jump out of recursiveness when a limit is reached to avoid infinite methods call).

On my implementation i receive all the maze points (start and finish) and start at the only start point until i reach any end point, giving that my first solution. I also changed the original method i build to present to you, so it can work with infinite dimensions, in this context, one dimension represent one axis.

I won't go through my code, but i'll be available to answer any question about it. I commented it so it's easier to understand.

Hope you guys find it usefull, feel free to use it anyway and to improve it in anyway.