Analysis of Recursive Algorithms

Analysis of Recursive Algorithms
A recursive function is a function that is defined in terms of itself.
Similarly, an algorithm is said to be recursive if the same algorithm is
invoked in the body. An algorithm that calls itself is direct recursive.
These recursive algorithms are extremely powerful, but even more
importantly, need more times and storage than iterative algorithms ( that
consist of iterative instruction like for, while, and repeat), therefore ,
recursive algorithms are worse than iterative algorithms because they are
used the stack, but they are more clearly than an iterative.
When analyzing a recursive function for its step count ( analysis its
running time), we often obtain a recursive formula. These recursive
formulas are referred to as recurrence relations which are solved by
repeated substitutions (iterative substitution) method.
Ex. 6:
Find the summation of one dimension array s elements.
The instance characteristics of this problem is n (number of elements).
Space Complexities:
Total space complexity
of recursive functions
cells number
for each calling
number of calling
= *
2
Each call to Rsum function needs two cells (one for variable S and the
other one for return address).
= ?n-0?+1 = n+1
Thus space complexities:
This is linear formula.
This space inconstant and dependents on instance characteristics (n).