HackerRank stone division - recursive design study (series 4 of 5)

Nov. 23, 2016

Introduction

It is time to get some training on recursive function. Learn a few terms related to recursive function first, Julia can describe what problems she had in the contest. She had problem to come out a simple recursive function, after so many years hard working as a scholar and full time programming experience.

She missed the important part to work on, recursive step, build a recurrence formula.  

C# solution - copy the code from editorial notes: score 50 - maximum score, pass all test cases

In the above C# solution, line 80:

ans = Math.Max(ans, 1 + ( (pile/runner) * rec(runner) ) );

Study Recursive Function
Julia googles searched the recursive function, and then she found 3 things to work on. And then, she noticed that her study lacks depth of industry experience. She found an engineer on stackoverflow.com, and then she spent a few hours to read his blog. Great teaching about recursive. 

Google Search: recursive function common mistakes

Choose some content to read:

1. university lecture notes - umd.edu
2. IBM article
3. lecture notes - MIT
4. recursive function blogs

Here are the details. 

1. university lecture notes - umd.edu:

Write down keywords:

c - core dump 

c - compact code - recursive solution 

h - How to think recursively?

s - stack space - recursive vs iterative 

     O(n)  vs  O(1)

    stack size - several megabytes - 1000 recursive calls 

t - tail-recursive function 

Google those keywords, and get more readings.

2. IBM article 

Notes:

Inductive definition 

inductively-defined 

Bug source: state changes

Ideas to avoid bugs:

    No variable does double-duty

    Be certain that all variables hit the state they are supposed to be in when the loop restarts. 

One rule: 

Assign a value to a variable only once and NEVER MODIFY IT!

1. Reusing a variable 

2. Conditional modification of a variable 

3. Loop variables

Base case proof. 

Inductive step proof. 

3. Lecture notes - MIT

Two common mistakes:

1.     The base case is missing entirely. or the problem needs more than one base case but not all the base cases are covered. 

2.     The recursive step doesn't reduce to a smaller subproblem, so the recursion doesn't converge. 

base cases

recursive steps

decompose a recursive problem into recursive steps and base cases

when and how to use helper methods in recursion

understand the advantages and disadvantages of recursion vs. iteration 

Structure of recursive implementations

- base case

- recursive step

A direct recursive implementation 

Don't expose the helper method to your clients

Temporary state 

Evolution of the computation

Recurrence relation 

Helper methods

Choose the right recursive subproblem

4. Eric Lippert's blog about recursive function

More reading:

stackoverflow->
recursive question/ answer by Eric Lippert
->       Eric Lippert

->  recursive blog

->  fibonacci challenge blog

-> teach recursive - how not to teach recursion

Recursion series:

Part 0:

Part 1: 

Teach how to think about recursion 

Julia's notes

recursive way to think about a list emphasize the similarity of a fragment of the list to the whole list. 

recursively define a list as either

1. the empty list with zero items on it, or

2. an item followed by a list

appear to be a circular definition, but it is really not. 'Spiral' definition

All recursive functions follow the same basic pattern: 

Am I in the base case? If so, return the easy solution. 

Otherwise, figure out some way to make the problem closer to the base case and solve that problem. 

bottom out - base case 

A binary tree is either:

an empty tree, or 

a value associated with two binary search trees, called the left and right child trees. 

inductive hypothesis - 

Part two: unrolling a recursive function with an explicit stack 

1 million nodes - balanced tree - 20 recursive depth - 2¹⁰ = 1024, so 1 million is around 2²⁰

"anonymous locals" - 

callee's frame   -  caller's frame  - current activation frame 

the temporary variables are spelled out 

each recursion happens on its own line

Part three: build a dispatch engine

Follow up after 3 months

Feb 23, 2017

Because of this study, Julia looked into stackoverflow.com, and then she found the code review on stackexchange.com. She did great job to help herself, from a failure to solve a recursive function to study recursive function, know one person/ a blog/ code review site, she is no longer a lone coder. She asked a lot of questions and tried to answer a few questions. She tasted the success of solving problem with other's help.