Created: 2023-01-11 17:00
Status: #concept
Subject: Programming
Tags: C Function

Recursion

A Function is "recursive" when it calls itself.

It iteratively reduces the calculation into smaller parts until the base case is met: Divide & Conquer.

It often starts with a Base Case conditional statement, then a Recursive Call if it fails to meet the base case.

  • the Base Case (aka Termination Condition) prevents the recursive function to do a stack overflow after infinitely calling new function instances.

Factorial Function

/* function that computes the factorial of {n} */
int fact(int n)
{
	if (n <= 1) // Base Case
		return 1;
	else
		return n * fact(n-1); // Recursive Call
}

Power Function

/* function that computes {x} raised to {n} */
int power(int x, int n)
{
	if (n == 0) // Base Case
		return 1;
	else
		return x * power(x, n - 1); // Recursive Call
}

C Recursive Power Function.png

References