Content deleted Content added
types of recursion |
|||
Line 88:
= 6
</math>
==Types of recursive functions==
Most of simple recursive functions can be classified in one of following types of recursive functions.
===Tail recursive function===
A function executes a number of tests and then if a certain test is true returns a certain value. If all tests evaluated as false, the function calls it self recursively on reduced input value. In talil recursive functions, the return value of last function call is the return value of the whole recursion. The template in [[Common Lisp]] would be:
(DEFUN ''func'' (X)
(COND (''end-test-1'' ''end-value-1'')
(''end-test-2'' ''end-value-2'')
; ...
(''end-test-n'' ''end-value-n'')
(T (''func'' ''reduced-x''))))
====Double-Test Tail Recursion====
The most common variat of Tail recursive function is double-test tail recursion. This type of recursion first tests if the recursion reached the end (without finding the result), then tests if it found result and if neither if true, calls it self recursively. The template in [[Common Lisp]] would be:
(DEFUN ''func'' (X)
(COND (''end-test-1'' ''end-value-1'')
(''end-test-2'' ''end-value-2'')
(T (''func'' ''reduced-x''))))
====Single-Test Tail Recursion====
If we are sure that the function will find what it's looking for eventualy, we can ommit the first test and only test if the result has been found. The template in [[Common Lisp]] would be:
(DEFUN ''func'' (X)
(COND (''end-test'' ''end-value'')
(T (''func'' ''reduced-x''))))
===Augmenting Recursion===
In augmenting recursion, the return value of one function call is augmented before returning it to the calling function. Therefore, the return value of a recursion is not the same as a return value of each function call. The template in [[Common Lisp]] would be:
(DEFUN ''func'' (X)
(COND (''end-test'' ''end-value'')
(T (''aug-fun'' ''aug-val''
(''func'' ''reduced-x'')))))
==See also ==
*[[Recursion]]
==References==
* [http://www.cs.cmu.edu/~dst/LispBook/ David S. Touretzky: "Common Lisp: A Gentle Introduction to Symbolic Computation"]
[[category:computer science]]
| |||