Data structures and algorithms · Lesson 25 of 60 · Code lesson, JavaScript or Python · Optional
Recursion
Recursion means a function calls itself to solve a smaller version of the same problem.
Every recursive function needs a base case that stops the calls, and a recursive case that moves toward it.
Without a base case it would call itself forever.
Worked example
In JavaScript, a function can call itself by name inside its own body.
function countdown(n) {
if (n === 0) return;
console.log(n);
countdown(n - 1);
}
countdown(3);Output:
3 2 1
In Python, a function can call itself by name inside its own body.
def countdown(n):
if n == 0:
return
print(n)
countdown(n - 1)
countdown(3)Output:
3 2 1
Your turn
factorial(n) multiplies n by every whole number below it, so factorial(5) is 120. The base case is done, but the recursive case just returns 0. Replace it with a call to factorial on a smaller number.
Your program is checked with these 3 inputs:
Input:
5
Expected output:
120
Input:
0
Expected output:
1
Input:
3
Expected output:
6
Loading your practice…
Preparing your workspace…