Linear Recursion 

The simplest form of recursion is linear recursion. It occurs where an action has a simple repetitive structure consisting of some basic step followed by the action again. This simple tale has amused generations of small children precisely because it is so simple but never ends. It seems somehow paradoxical.procedure ODSN begin One dark and stormy night, Three men sat in a cave, And one said to another, Dick, tell us a tale, And this is how the tale began: ODSN  again! end Generally we want the recursion to terminate on some condition. The song `Ten Green Bottles' does not go on forever:
FactorialThe factorial function is a popular mathematical example:
If the base case of the recursion takes time `a' and the recursive step takes time `b' then a linear recursive routine making `n' recursive calls takes time a+b*(n1) in total; this is O(n). For the factorial function, the number of calls is the value of its parameter. ExponentiationIn the case of the following exponentiation function
which calculates x^{n} Pre: x > 0 expn(x, 0) = 1 expn(x, n) = 1 / expn(x, n), if n<0 expn(x, n) = (expn(x, n div 2))^{2}, if n>0 and n is even expn(x, n) = x * expn(x, n1), if n>0 and n is odd Finally the time complexity of the routine fits the form for logarithmic complexity:If n>0: (i) x^{n} = 1/x^{n} if x~=0 (ii) x^{0} = 1 (iii) x^{2n} = (x^{n})^{2} (iv) x^{2n+1} = x*x^{2n} which has solutionT_{0} = b T_{n} = T_{n/2}+a if n>0 Many languages provide a numerical exponentiation operator `**' in which case the above algorithm is not required for numbers. However some languages do not provide this operator as standard. In addition other objects, such as matrices, can also be multiplied and therefore exponentiated. With modification, this algorithm can also be used for the latter purpose.T_{n} = a * log(n) + b + a, n>=1 The chapter on lists contains more examples of linear recursion. Note that a linear recursive routine usually has a simple iterative equivalent. The recursive step is placed within a loop and the terminating condition is used to exit from the loop. © L.A.


↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Monday, 18Oct2021 10:25:06 EDT. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 