Example of recursively defined function:
defines the value of the function at some natural number n in terms of the function's value at the previous number, n-1, whereas the function at 0 is explicitly given.
- we would refer to the first part of the definition as the base-case and to the second part as the inductive step of the recursion.
when proving a recursively define function, first thing we would have to do is the step called "unwinding", which derives to find a closed-form formula for a function, f(n).
How-To-Do: we unwind(a technique called repeated substitution) the recursive definition of f(n) by simply repeatedly applying the induction step of the definition to smaller and smaller arguments of function(recursive steps), f. we keep this step until we discover a pattern that will convey us a closed-form formula.
1. find closed-form formula for the function by using unwinding technique
2. prove that the closed-form formula is equal to the recursive definition of the given function by using an appropriate induction.
No comments:
Post a Comment