Definition

Recursive functions are functions that call themselves, each time dealing with a smaller version of the problem they are trying to solve. Once they reach the smallest version of the problem, they return a value instead of calling the function again.

Base case

A base case is when the function returns a value without calling itself; it deals with the smallest version of the problem. Ideally, this provides the solution to the problem.

Recursive call

A recursive call deals with a function call that deals with a smaller version of the problem. Each recursive call, if the recursive function is correct, should bring you closer to the base case.

Issues with Recursive Functions

Unfortunately, recursive functions are very memory intensive. Each recursive call is stored on the heap, and calls are made repeatedly until a solution is found. Thus, the amount of memory a recursive function takes is dependent on the number of recursive calls required to find the solution.

For this reason, recursive functions are typically avoided in the real world wherever possible.

Example: Euclidean GCD Algorithm

You can use recursion to calculate the Euclidean Algorithm.

• Your recursive call should call the GCD function using:
  • $|a-b|$ and $b$ (if $a>b$), or
  • $b$ and $a$, if ($b>a$)
• Your base step should occur if $a=b$. In this case, return $a$ and do not make a recursive call. This is the GCD of the original function.

That is represented by the following:

Code

#include <stdio.h>

int gcd(int a, int b) {
	if (a == b) {
		// base case
		return a;
	} else if (a > b) {
		// recursive step if a > b
		return gcd(b, a - b);
	} else {
		// recursive step if b > a
		return gcd(b, a);
	}
}

int main(void) {
	int a = 20;
	int b = 8;
	int gcdAnswer = gcd(a, b);
	printf("The greatest common denominator of %d and %d is %d\n", a, b, gcdAnswer);
	return 0;
}

Example: Factorial of a Number

You can find the factorial of a number using recursion. I'm not sure why you wouldn't just do this iteratively, but whatever. Here's the logic:

• At each recursive step, multiply $n$ by the factorial of the $n-1$ term.
• The base step should just be $1$, and at that point, don't multiply by $1-1$ because obviously that gives $0$.

Code

#include <stdio.h>

int fact(int n) {
	if (n == 1) {
		// base step
		return n;
	} else {
		// recursive step
		return n * fact(n-1);
	}
}

int main(void) {
	int n = 4;
	printf("The factorial of %d is %d.\n", n, fact(n));
	return 0;
}