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:
The 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*(n-1) in total; this is O(n). For the factorial function, the number of calls is the value of its parameter.
In the case of the following exponentiation function
which calculates xn
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, n-1), 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/xn if x~=0 (ii) x0 = 1 (iii) x2n = (xn)2 (iv) x2n+1 = x*x2n
which has solutionT0 = b Tn = Tn/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.Tn = 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. Allison, www.allisons.org/ll/ (or as otherwise indicated).
Created with "vi (Linux)", charset=iso-8859-1, fetched Monday, 18-Oct-2021 10:25:06 EDT.
Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.