Recursive Algorithms Analysis

Recursive Algorithms Analysis
The recursive algorithm is the algorithm that call itself many times. To find the Space complexity we multiply the number of words by the depth of recursion, that is computed by the following equation:

The Depth of Recursion=

And the Time complexity can be computed in a form of recurrence relations, then solved using Iterative substitution method.
Example 6:
Function Rsum ( a: as array of integer, n :number of element)
Begin
If (n<=0) then
s= 0
Else
s = a(n)+Rsum(a,n-1)
endif
return s
End
Solution:
Note: The problem is described by n
For example n=3, a(3)=(6, 4, 2)






Space complexities: each call for the function require four words that s, n , name of function and return address.
Depth of Recursion = | n – 0 | + 1 = n+1
Then the space complexity SRrsum (n)= 4 (n+1)

Time complexities: we use the Iterative substitution method.
TRsum (n) = 3 , n<=0
3 + TRsum (n-1) , n >0
TRsum (n) = 3 + TRsum (n-1)
= 3+ [3 + TRsum (n-2)]
= 2(3)+ TRsum (n-2)
= 2(3) + [3+ TRsum (n-3)]
=3(3) + TRsum (n-3)
.
.
= m(3) + TRsum (n-m)
Where n=m
= 3n + 3
Example 7: Find factorial number n!.
Algorithm Rfactorial(n):
Input: a positive integer n.
Output: the result of n!.
Begin
If n=0 then
Return 1
Else
Return n*Rfactorial(n-1)
End

Solution:
Space complexities:
Each call to Rfactorial function needs three word for n, name of function and return address.
number of calling=|n-0|+1=n+1
(depth of recursion)
Thus space complexities:
SRfactorial (n)= 3 * ( n + 1 ) = 3n + 3
Time complexities:
TRfactorial(n)= 2 , n=0
2 + TRfactorial(n-1) , n>0
TRfactorial(n) = 2 + TRfactorial(n-1)
= 2+[2+ TRfactorial(n-2)]
=2(2)+ TRfactorial(n-2)
=2(2)+[2+ TRfactorial(n-3)]
=3(2)+ TRfactorial(n-3)]
.
.
=m(2)+ TRfactorial(n-m)
Stop s condition is n-m=0 , m=n
TRfactorial(n)=2n+ TRfactorial(0) = 2n+2
H.W. Analyze the following problems using recursion schema
1. Find the power of two positive numbers
2.Write a function for printing elements of one dimension array in reverse form.
3. Write function for finding the summation of elements of two dimensions array.