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:

function s(n) // happens to be a JavaScript program { if( n != 1 ) return 's'; else return ''; } function verse(n) { if( 0 < n ) { document.write(n + ' green bottle' + s(n) + ' hanging on the wall,<BR>\n'); document.write(n + ' green bottle' + s(n) + ' hanging on the wall,<BR>\n'); document.write('And if 1 green bottle' + ' should accidentally fall,<BR>\n'); document.write('There\'ll be ' + (n1) + ' green bottle'+s(n1)+' hanging on the wall.<BR><BR>\n'); verse(n1); } } verse(10); // or however many bottles it is
Factorial
The factorial function is a popular mathematical example:

f(0) = 1 base case f(n) = n*f(n1), if n > 1 general case
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.
Exponentiation
In 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.