Recursive Functions

A definition that defines an object in terms of itself is said to be recursive. In computer science, recursion refers to a function or subroutine that calls itself, and it is a fundamental paradigm in programming. A recursive program is used for solving problems that can be broken down into sub-problems of the same type, doing so until the problem is easy enough to solve directly.

Examples

Fibonacci Numbers

A common recursive function that you’ve probably encountered is the Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, and so on. That is, you get the next Fibonacci number by adding together the previous two. Mathematically, this is written as

\$\$f(N)=f(N-1)+f(N-2)\$\$

Try finding f(10). No doubt, you have the correct answer, because you intuitively stopped when you reach \$f(1)\$ and \$f(0)\$. To be formal about this, we need to define when the recursion stops, called the base cases. The base cases for the Fibonacci function is \$f(0)=1\$, and \$f(1)=1\$. The typical way to write this function is as follows: \$\$f(N)=\cases{1 & if \$N=0\$\cr 1 & if \$N=1\$\cr f(N-1)+f(N-2) & if \$N > 1\$}\$\$

Here is a Python implementation of the Fibonacci function:

def Fibonacci(x):
if (x == 0) return 0
if (x == 1) return 1
return Fibonacci(x-1) + Fibonacci(x-2)

(As a challenge to the reader: How could you implement the Fibonacci function without using recursion?)

Factorial Function

Consider the factorial function, \$n! = N * (N-1) * ... * 1\$, with 0! defined as have a value of 1. We can define this recursively as follows:

\$\$f(x)=\cases{x*f(x-1) & if \$x\gt 0\$\cr 1 & if \$x=0\$}\$\$

WIth this definition, the factorial of a negative number is not defined.

Here is a Python implementation of the factorial function:

def Factorial(x):
if (x<=0) return 1
return x*Factorial(x-1)

In the implementation above, the base case is listed as

x <= 0

rather than

x < 0

to return a value 1 when called with a negative number. Had the implementation been coded with <, then calling it with a negative number would lead the function never returning. This is called infinite recursion.

Some Definitions

A few definitions: Indirection recursion is when a function calls another function which eventually calls the original function. For example, A calls B, and then, before function B exits, function A is called (either by B or by a function that B calls). Single recursion is recursion with a single reference to itself, such as the factorial example above. Multiple recursion, illustrated by the Fibonacci number function, is when a function has multiple self references.

Many beginning programmers have a tough time writing recursive programs. So if this is confusing to you, not to worry!

This ACSL category focuses on mathematical recursive functions rather than programming procedures; but you’ll see some of the latter.

Online Resources

ACSL

The following videos show the solution to problems that have appeared in previous ACSL contests.

 Recursion Example 1 (CalculusNguyenify) The video walks through the solution to a straight-forward single-variable recursive function, that is, \$f(x)=\cases{....}\$ The problem appeared in ACSL Senior Division Contest #1, 2014-2015. Recursion Example 2 (CalculusNguyenify) The video walks through the solution to a 2-variable recursive function, that is, \$f(x,y)=\cases{....}\$ . The problem appeared in ACSL Senior Division Contest #1, 2014-2015. Recursive Functions ACSL Example Problem (Tangerine Code) The video walks through the solution to a 2-variable recursive function, that is, \$f(x,y)=\cases{....}\$ .

Other Videos

The follow YouTube videos cover various aspects of this topic; they were created by authors who are not involved (or aware) of ACSL, to the best of our knowledge. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.