Here, we briefly discuss recursion.
To understand recursion one must first understand recursion
Structurally, recursive definitions are common for building recursively defined sets (e.g. N: 1 in N and [n in N => n+1 in N]); functionally, for building recursively defined functions.
These are alternatively referred to as inductively defined functions, but we will prefer the former term. The Recursion Theorem states their existence and unicity, their general form is given as is from http://www.cs.toronto.edu/~vassos/b36-notes/:
In many cases it is hard to derive a closed form for such functions, however for the special case of functions defined by simple recursion (where there is a single recursive call in the recurrence relationship), a method called repeated substitution can be applied, we give its outline:
Let k be large enough, consider the recursively defined function: T(k) = T(h(k)) + nk
> Substitute T(h(k)) recursively in the equation:
T(k) = T(h(h(k))) + h(k)k + nk
> Then apply arithmetic rules to simplify it
> Repeatedly iterate the process until a pattern emerges (not always the case!), then write the general formula for the ith iteration. In that form, substitute the input k by an input that will eliminate the recursive call by transforming it into the base case. Now the closed form can be proved to be valid using induction. Note that sometimes it might be necessary to make specific assumptions on k (if h(k)=k/2 then we might want to consider k to be a power of 2) in order to make progress.
We provide a working example:
open form : T(n) = 2T(n/2)+n (n>1; T(1)=1)
let n=2^k : T(2^k) = 2T(2^k-1)+2^k
1st sub. : T(2^k) = 2^2 * T(2^k-2) + 2 * 2^k
2nd sub. : T(2^k) = 2^3 * T(2^k-3) + 3 * 2^k
3rd sub. : T(2^k) = 2^4 * T(2^k-4) + 4 * 2^k
gen. ith form : T(2^k) = 2^i * T(2^k-i) + i * 2^k
let i=k : T(2^k) = 2^k * T(1) + k * 2^k
elim rec. call : T(2^k) = 2^k + k * 2^k
n=2^k => k=logn : T(n) = n + log_2(n) * n
closed form : T(n) = n*log_2(n) + n (when n is a power of 2)
In algorithm design, recursion is a powerful tool applied in many paradigms (strategical approaches to problems), the most notorious being the divide and conquer method.
To understand recursion one must first understand recursion
Structurally, recursive definitions are common for building recursively defined sets (e.g. N: 1 in N and [n in N => n+1 in N]); functionally, for building recursively defined functions.
These are alternatively referred to as inductively defined functions, but we will prefer the former term. The Recursion Theorem states their existence and unicity, their general form is given as is from http://www.cs.toronto.edu/~vassos/b36-notes/:
In many cases it is hard to derive a closed form for such functions, however for the special case of functions defined by simple recursion (where there is a single recursive call in the recurrence relationship), a method called repeated substitution can be applied, we give its outline:
Let k be large enough, consider the recursively defined function: T(k) = T(h(k)) + nk
> Substitute T(h(k)) recursively in the equation:
T(k) = T(h(h(k))) + h(k)k + nk
> Then apply arithmetic rules to simplify it
> Repeatedly iterate the process until a pattern emerges (not always the case!), then write the general formula for the ith iteration. In that form, substitute the input k by an input that will eliminate the recursive call by transforming it into the base case. Now the closed form can be proved to be valid using induction. Note that sometimes it might be necessary to make specific assumptions on k (if h(k)=k/2 then we might want to consider k to be a power of 2) in order to make progress.
We provide a working example:
open form : T(n) = 2T(n/2)+n (n>1; T(1)=1)
let n=2^k : T(2^k) = 2T(2^k-1)+2^k
1st sub. : T(2^k) = 2^2 * T(2^k-2) + 2 * 2^k
2nd sub. : T(2^k) = 2^3 * T(2^k-3) + 3 * 2^k
3rd sub. : T(2^k) = 2^4 * T(2^k-4) + 4 * 2^k
gen. ith form : T(2^k) = 2^i * T(2^k-i) + i * 2^k
let i=k : T(2^k) = 2^k * T(1) + k * 2^k
elim rec. call : T(2^k) = 2^k + k * 2^k
n=2^k => k=logn : T(n) = n + log_2(n) * n
closed form : T(n) = n*log_2(n) + n (when n is a power of 2)
In algorithm design, recursion is a powerful tool applied in many paradigms (strategical approaches to problems), the most notorious being the divide and conquer method.
No comments:
Post a Comment