Rookie in recursive function design

May 29, 2017

Introduction

It is the great experience to teach myself how to write a correct recursive function to implement a depth first search algorithm. Julia spent over hours to teach herself, how to track a route in depth first search over one hour.

In order to figure out the issue, Julia wrote a depth first search algorithm using stack to help herself. She compared to the version using stack to the one using recursive function. She found out that the issue she had, she did not need to use memoization, she needed a memo to mark visited node to avoid dead loop.

Code practice 

C# code with dead loop, stack overflow issue. Mocking code is here. 

C# code to write a stack to implement Depth First Search (DFS). Code is here. 

C# code to write a recursive function. Code is here. 

A cheerful heart is medicine. Smile to my own mistake, next time I will ace the recursive function. Coding is done by a human, crafting takes practice!

Recursive - HARD TO TELL

Argument:

Use non-recursive depth first search algorithm to help the design. Using an explicit stack, it is much easy to follow. Write pseudo code, figure out base case, the design to avoid dead loop, cycle issue, memoization issue, structure the algorithm first. And then use it as the helper of recursive function design.

Recursive function is short and efficient to implement DFS, but error-prone. It is not straightforward. Practice this way to help yourself.

Use stack to help

Every mistake is valuable

I should say that memoization is extra, next step. Need to work on basic recursive function boundary check first. One thing is to test the code with the sample test cases, slowly and carefully, mark the test case for each line of code using comment.

To be a good tester all the time. Read your own code and go over it, with test cases. Julia, you got the tip from mocking experience.