Tree created using the Logo programming language and relying heavily on recursion. For general use of the term, see Recursion. For recursion in computer science acronyms, see Recursive acronym § Computer-related examples. For proofs by recursion, see Mathematical induction. In the above example, call/cc can be used to take the remaining part of the computation and to throw it away, so performing a sort of "exit" that stops the computation and empties the stack.This article is about recursive approaches to solving problems. In cases like our example, the use of the operator call/cc enables you to stop the computation as soon as we meet a 0, by "removing" all that is still on the "stack".Ĭall/cc work on the remaining part of the computation. Since, even if at a certain point you could stop the computation, you are sort of "obliged" to complete the recursive calls present on the "stack".
There is no way to prevent this waste of computation if you do not use call/cc or something similar However, the interpreter proceeds in the computation, evaluating also (Mt (leftchild tree)), even if such evaluation is completely useless. This means that the product of all the nodes of the tree will be also 0, by the property of multiplication. So the function Mt applied to this subtree returns 0 as result. The right subtree of the upper node 2 has the root with label zero. Let's assume we want to apply it to the following tree: The above function computes the product of all the nodes of a binary tree with numeric labels. We just show an example of the sort problems these kind of operators have been devised for. We do not explain how these particular Scheme operator, and other similar operators in In fact the list type-constructor in Haskell is a Monad. Notice how the tail-recursive solution in Haskell uses the operator >=. In a tail recursive and non tail-recursive way. In the page of Haskell Exercises, the same problem is solved in Haskell Prolog program is the one finding all the possible paths between two nodes inĪ non tail-recursive version of such a program can be found in the exercises page Tail recursion can be thought of as the functional counterpart of Iteration.Īlso in Prolog we can have tail recursive programs. In this definitions there is a "hidden" iterative imperative algorithm. ReverseIterAux (x:xs) as = reverseIterAux xs (x:as)ĪppendIterAux ys as = appendIterAux ys ĪppendIterAux (x:xs) ys as = appendIterAux xs ys (x:as) Let us see a few tail recursive versions of well known functions It is possible to provide iterative versions of all the functions, not always easily. In a sense, each recursive call is like an iteration that modifies a variable, the accumulator, and the "assignment" of a new value to the accumulator is mimicked by passing the new value as second argument of the recursive call. In each recursive call a shorter list is passed to aux, while the accumulator is "extended" with the first element of the list. In the function sumAux (used by sumIter) the argument 'c' plays the role of an accumulator. The translation of a non tail recursive function, instead, will definitely use a stack, or something equivalent.) Tail recursion, in a sense, correspond to the notion of iteration in functional programming (indeed you can translate tail recursive functions in an imperative language by using a simple loop. You need to remember nothing, since no operation is left to be computed.
Now, mimic the evaluation of sumIter on the same input. In a sense, you need a stack to remember what "remains to be computed". When the base case is reached, all the additions can be made.
You need to leave a number of additions uncompleted until you reach the base case. Try and see by yourself what happens during the evaluation of sum on a list, say (2 4 6 1 3). If we define the same function without tail recursion we get The function SumAux is tail recursive because after the recursive call there is nothing else left to do. Lecture Notes on Tail Recursion and call/ccĪ function is said to be tail recursive when the recursive call is the last function invoked in the evaluation of the body of the function.
0 kommentar(er)
