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.
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:
Choose some content to read:
- university lecture notes - umd.edu
- IBM article
- lecture notes - MIT
- 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.
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:
Recursion series:
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 -
1 million nodes - balanced tree - 20 recursive depth - 210 = 1024, so 1 million is around 220
"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.
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.
