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.

Sudoku solver talk

April 11, 2017

Introduction

Sudoku solver is such interesting problem and Julia wrote more than 3 solution in her practice back in 2015. Here is one of the blogs, and also Leetcode 37: sudoku solver is also very good material to review the algorithm.

Sudoku solver talk 

Here is the C# code written in 30 minutes mocking experience.

Transcript is compiled to make it work. C# code is here.

Highlights of a few corrections:

3 nested for loops. The first 2 for loops is to find the first cell with value -1 to do search, try numbers from 1 to 9 and start a DFS search, if all of them are failed, then return false; otherwise return true.

Need to talk about optimization, use the first one with value -1 to start DFS or other cell?

Follow up

Sept. 6, 2017

It is very important to learn the algorithm. Start from code review and learn from the important message in the review.