Linear Recursion and Iteration

In the Factorial Kata article, the solution was driven by tests and used loop with explicit index in the solution. In this article, we will see how to encode mathematical truth in code.

Linear Recursive Process

Factorial function is defined by:

n! = n * (n-1) * (n-2) ... 3 * 2 * 1

We can make use of:

n = n * (n - 1)!
1! = 1

In Lisp:

(define (factorial n)
  (if (=n 1)
    1
    (* n (factorial (- n 1)))))

(factorial 6)

If you draw the diagram of this program execution by using the substitution model. You can see the shape of expansion followed by contraction. This is due to the pending operations (multiplications) that is pushed on to the stack and each of those pending operation executing and getting popped off the stack. The shape is linear because, as the value of n increases the expansion is linear. Such a process is called a linear recursive process. This can easily be translated to Ruby:

def factorial(n)
  if n == 1
    1
  else
    n * factorial(n - 1)
  end
end

p factorial(6)

Linear Iterative Process

We can use the fact:

n! = 1 * 2 * 3 * 4 ...  * n

directly in code. We need two things, a counter and an accumulator to accumulate the running product of two numbers.

accumulator = 1
1.upto(6) {|n| accumulator *= n}
p accumulator

In this solution, we are using the Ruby's upto method to keep track of counting numbers 1 through 6. We use an accumulator variable to accumulate the running product that eventually has the final computed factorial value for a given value of n.

In computing n!, the number of steps required grows linearly with n. Such a process is called a linear iterative process. This process is executed in constant space, we only need the variables n and accumulator regardless of the value of the input n. I am not showing the Lisp equivalent because it is bit more complicated than the Ruby equivalent.

Tip for Composing Code

Sometimes we can directly map the mathematical statement to code. It is also useful to have names for certain programming language constructs that is independent of any programming language. We can then simply translate the language independent programming construct to a specific language construct using the chosen language's syntax. In this article, we used two such language constructs, namely: counter and accumulator. These are very basic language constructs used to solve coding problems. Your computational thinking becomes more powerful, more the number of language constructs you have in your toolbox. You will able be quickly identify where in your solution these programming elements can be used to code a solution from scratch.

Reference

Structure and Interpretation of Computer Programs Gerald Jay Sussman and Hal Abelson


Related Articles


Ace the Technical Interview

  • Easily find the gaps in your knowledge
  • Get customized lessons based on where you are
  • Take consistent action everyday
  • Builtin accountability to keep you on track
  • You will solve bigger problems over time
  • Get the job of your dreams

Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview

No spam ever. Unsubscribe anytime.