Photo by Laura Gilchrist on Unsplash

All About Recursion

Part 2 — Recursive Process vs Recursive Procedure and Tail Recursion

In part 1 of this series we talked about the basics of recursion. In this post we will be talking about the distinction between a recursive process and a recursive procedure. The distinction is easily overlooked but in essence a recursive procedure is when a program calls itself within its body (this is definition most people think of when talking about recursion) while a recursive process is a process that is executed recursively and not iteratively.

In some computer languages, not all procedures that call itself are executed in a recursive way.

For example, in Scheme, you can call a procedure within itself (recursive procedure) and pass in a counter as a parameter. After each execution of the call you add one to the counter. Each time you run through the calculations, a counter keeps track of the current state of the calculation. The computer only ever needs to keep track of one state.

If we wanted to calculate the factorial of 6 (and why wouldn’t want to calculate the factorial of 6?!) we can define a function called factorial(n) that takes in the number we want to find the factorial of (in this case 6) and define another function fact-iter(product, counter, max) that accepts three parameters:

• product — a number that keeps the running total of the numbers that have been multiplied
• counter — a number that keeps track of which number is currently being multiplied
• max— the number of times you would like to repeat this process

(define (factorial n)
     (fact-iter 1 1 n)
(define (fact-iter product counter max)
     if (> count max)
         product
        (fact-iter (* counter product)
                   (+ counter 1)
                    max)))

From the above code we see that fact-iter will handle the logic of finding the factorial while factorial will kick off the process. The fact-iter function will first check to see that the current running tally of multiplication steps is less than the max . If it is more than the max that means the correct amount of multiplications has taken place in which case it should return the product. If it is less than the max it should call itself again (this is what makes fac-iter a recursive procedure), however, because we are passing in the updated product and counter, this makes it an iterative process. Each step of the recursive call the computer is keeping track of an updated state. There is no deferred operation the computer must keep track of like there was in the fib(n) example in part 1 of this series.

If you are familiar with most common programming languages this may sound very similar looping constructs like the do, while and for statements. Scheme does not have these looping constructs and must use a recursive procedure to iterate. This process of using recursion to iterate (as opposed to a formal looping statement) is known as tail recursion because the last call in the procedure or statement (the tail end position, hence the name) is, and only is, a recursive call (i.e. there is no additional operation performed on the recursive call).