Skip to content

Instantly share code, notes, and snippets.

@abinoda
Last active June 5, 2023 11:11
  • Star 11 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save abinoda/5593052 to your computer and use it in GitHub Desktop.

Recursion

What is recursion?

A recursive function is a function that makes a call to itself.

To prevent infinite recursion, you need at least one branch (i.e. of an if/else statement) that does not make a recursive call. Branches without recursive calls are called base cases; branches with recursive calls are called recursive cases.

def factorial_recursive(n)
  if n == 0
    # base case
    return 1
  else
    # recursive case
    return n*factorial_recursive(n-1)
  end
end

Functions can also be mutually recursive. For example, function f() can call function g() and function g() can call function f(). This is still considered recursion because a function can eventually call itself. In this case, f() indirectly calls itself.

When to use recursion vs iteration?

In general, recursion should be used when it produces a cleaner, more expressive solution compared to the iterative version, and when you know that an excessive number of recursive calls will either not occur, or not lead to performance issues such as stack overflow.

Keep in mind that "recursion" and "loops" are just what we humans name our code -- what matters for performance is not how we name things, but rather how they are compiled or interpreted. Thus performance depends on the specific programming language and code being used.

In most imperative programming languages (eg. C, Python, Ruby), recursion is generally more expensive than iteration because it requires winding, or pushing new stack frames1 onto the call stack2 each time a recursive function is invoked -- these operations take up time and stack space, which can lead to an error called stack overflow if the stack frames consume all of the memory allocated for the call stack.

Thus the main drawback with recursion is that it has linear, or O(n), stack space requirements while for an iterative function it is constant, or O(1).

Tail Call Optimization

We can eliminate this overhead through tail-call optimization, but only in cases where the compiler/interpreter supports transforming recursive calls into jumps instead of function calls. In Ruby 1.9.2+, tail call optimization is supported natively, though not by default.

To understand how tail call optimization works, let's first examine the execution of the factorial function we defined earlier.

call factorial (3)
 call factorial (2)
  call factorial (1)
    call factorial (0)
    return 1
  return 1     # 1*factorial(0)
 return 2      # 2*factorial(1)
return 6       # 3*factorial(2)

Notice how each time we recurse we build up a deferred operation? Since we can't calculate our result until we have returned from every recursive call, we don't begin unwinding the stack until the deepest recursive call has returned. This is inefficient

Now let's make our recursive function a tail call3, meaning that the function does no additional work after the recursive call is complete, except to return the value of the recursive call.

def factorial_tail_recursive(n, running_total=1)
  if n == 0
    return running_total
  else
    return factorial_tail_recursive(n-1, running_total*n)
  end
end

Because we immediately return after the tail call, we can discard the previous stackframe before invoking the function in tail position, or, in the case of recursive functions, reuse the stackframe as-is. The Ruby interpreter also recognizes the execution of this code differently and optimizes it by transforming recursive method invokations into iteration using a GOTO statement. If we looked at the the compiled code, it'd look similar (or in some cases just about identical) to the iterative version of the method:

def factorial(n)
  running_total = 1

TOP:
  return running_total if n == 0
  running_total = n * running_total
  n = n - 1
  goto TOP
end

We don't need to worry about stack overflow for extremely deep recursions, and our function should be substantially faster than the non-optimized function by a constant factor (the time it took for stack pushes and pops).

Terms:

Stack frame

A data structure containing a non-terminated function call's return address, local data, and parameters. Winding, or adding a stack frame to the call stack, occurs when a function is invoked. Returning from the called function will pop, or unwind the frame off the stack.

Call stack

A call stack is a stack data structure (composed of stack frames) that stores information about the active subroutines of a computer program. There is usually exactly one call stack associated with a running program (or more accurately, with each task or thread of a process)

Tail call

A tail call is a subroutine call that happens inside another procedure as its final action. Tail calls are significant because they can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call. The program can then jump to the called subroutine.

Additional References:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment