Main content

### Course: Computer science theory > Unit 1

Lesson 6: Recursive algorithms- Recursion
- The factorial function
- Challenge: Iterative factorial
- Recursive factorial
- Challenge: Recursive factorial
- Properties of recursive algorithms
- Using recursion to determine whether a word is a palindrome
- Challenge: is a string a palindrome?
- Computing powers of a number
- Challenge: Recursive powers
- Multiple recursion with the Sierpinski gasket
- Improving efficiency of recursive functions
- Project: Recursive art

© 2024 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# Recursive factorial

For positive values of $n$ , let's write $n!$ as we did before, as a product of numbers starting from $n$ and going down to 1: $n!$ = $n\cdot (n-1)\cdots 2\cdot 1$ . But notice that $(n-1)\cdots 2\cdot 1$ is another way of writing $(n-1)!$ , and so we can say that $n!=n\cdot (n-1)!$ . Did you see what we just did? We wrote $n!$ as a product in which one of the factors is $(n-1)!$ . We said that you can compute $n!$ by computing $(n-1)!$ and then multiplying the result of computing $(n-1)!$ by $n$ . $(n-1)!$ is a $n$ !.

*You can compute the factorial function on*$n$ by first computing the factorial function on $n-1$ .We say that computing**subproblem**that we solve to computeLet's look at an example: computing 5!.

- You can compute 5! as
.$5\cdot 4!$ - Now you need to solve the subproblem of computing 4!, which you can compute as
!.$4\cdot 3$ - Now you need to solve the subproblem of computing 3!, which is
.$3\cdot 2!$ - Now 2!, which is
.$2\cdot 1!$ - Now you need to compute 1!. You could say that 1! equals 1, because it's the product of all the integers from 1 through 1. Or you can apply the formula that
. Let's do it by applying the formula.$1!=1\cdot 0!$ - We defined 0! to equal 1.
- Now you can compute
.$1!=1\cdot 0!=1$ - Having computed
, you can compute$1!=1$ .$2!=2\cdot 1!=2$ - Having computed
, you can compute$2!=2$ .$3!=3\cdot 2!=6$ - Having computed
, you can compute$3!=6$ .$4!=4\cdot 3!=24$ - Finally, having computed
, you can finish up by computing$4!=24$ .$5!=5\cdot 4!=120$

So now we have another way of thinking about how to compute the value of $n!$ , for all nonnegative integers $n$ :

- If
, then declare that$n=0$ .$n!=1$ - Otherwise,
must be positive. Solve the subproblem of computing$n$ , multiply this result by$(n-1)!$ , and declare$n$ equal to the result of this product.$n!$

When we're computing $n!$ in this way, we call the first case, where we immediately know the answer, the

**base case**, and we call the second case, where we have to compute the same function but on a different value, the**recursive case**.This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

## Want to join the conversation?

- Would it be appropriate to understand this implementation as mathematical induction?(24 votes)
- Induction and recursion are closely related.

Induction starts from the base case(s) and works up, while recursion starts from the top and works downwards until it hits a base case.

With induction we know we started on a solid foundation of the base cases, but with recursion we have to be careful when we design the algorithm to make sure that we eventually hit a base case.

Often when we want to prove a recursive algorithm is correct we use induction. (We also need to include a proof that the algorithm terminates)(87 votes)

- var factorial = function(n) {

var result=n-1;

// base case:

if (n === 0 ) {return 1;}

// recursive case:

else if (n >0) {

for (var i =1; i <n-1 ; i++){

result = result*i;

}

return n*result;}

};

why i cant pass the second step of challenge? need some help~~~(7 votes)- It's not working because your solution is an
**iterative**solution, not a**recursive**solution.

A**recursive**solution would involve the function calling itself (Hint: your**recursive**case should fit on one line, and shouldn't have a for loop)(23 votes)

- This is a very clear explanation, but I wonder if you might want to include some cautionary language about using recursion in the real world. In Steve McConnell's book
*Code Complete*, he says this (p. 397) about recursion and factorials:

"One problem with computer-science textbooks is that they present silly examples of recursion. The typical examples are computing a factorial or computing a Fibonacci sequence. Recursion is a powerful tool, and it's really dumb to use it in either of those cases.*If a programmer who worked for me used recursion to compute a factorial, I'd hire someone else.*. . . In addition to being slow and making the use of run-time memory unpredictable, the recursive version of [a factorial-computing] routine is harder to understand than the iterative version . . . ."

Now, I understand that factorials are a pretty easy way to teach recursion, and I understand that*Code Complete*is very opinionated. But wouldn't it be worth alerting the learner to the possibility of criticism like McConnell's? Food for thought.(11 votes) - in the next challenge you refer to "base case", what is "base case"?(5 votes)
- Base case is where the value of the function is specified in one or more values of the parameter. It is where you ask yourself: Is there a non-recursive way out of the function?

Trivial cases of the function.

Example:

In factorial if n = 0 then n! =1 // non-recursive part or base case

otherwise if n>0 ---> n! = (n-1)! // recursive case(7 votes)

- Is it possible to find the factorial value of a negative number? Or is it always 1?(5 votes)
- What would a negative factorial be? It would just be -(5!), or

-( 5 x 4 x 3 x 2 x 1)

So you could just ignore the negative symbol, and add it at the end.(4 votes)

- Wait, what makes this any more efficient than the simple algorithm we wrote in the last challenge? This seems unnecessarily complicated.(4 votes)
- You will find that the implementation is quite simple. This is just a basic example to introduce you to the idea of recursion. In practice you really should not compute factorials recursively.(7 votes)

- Could someone please help me.

I made a program for factorial by using C++.

At first I did it using the recursion method.But found that the factorial function gives wrong answer for input values of 13, 14 and so on. It works perfectly until 12 as the input.

To make sure my program is correct I used iteration method using the "while loop". But that also gave me the same result; incorrect answer after 12.

I crosschecked with my calculator (CASIO fx-991MS).

But with javascript the function runs perfectly.

Here is my program using C++ in codeBlocks:

#include <iostream>

using namespace std;

//using recursion

int factorial(int x){

if(x == 0){

return 1;

}else{

return x*factorial(x-1);

}

}

//using iteration

int Factorial(int x){

int factorialValue = 1;

while(x > 0){

factorialValue *= x;

x--;

}

cout << factorialValue << endl;

}

int main()

{

//calling for the recursion function

cout << factorial(13) << endl;

//Calling for the iteration function

Factorial(13);

return 0;

}(3 votes)- The problem is the code above uses the
`int`

type. The`int`

type in C++ is 32 bits, so it only has a range of:

-2^31 to 2^31-1

Since 13! is larger than that it starts to overflow and gives crazy answers. Try using the`long long`

or`long long int`

type which uses 64 bits so it can store numbers from:

-2^63 to 2^63-1(3 votes)

- How could you simplify this process with larger numbers? For example if I had to calculate 100! ,

Could I multiply 5! by 20! How do you divide as well?(3 votes)- You could store some of the calculations in an array and access the values when needed.

Google dynamic programming if you're interested in optimization.(2 votes)

- I'm trying to figure out the results of a python code problem that could be a math problem but if a user inputs a random value of how they want to calculate factorial. Say they put in 11. then after you have dealt with the < 0 and if it == 1 then you have to go thru a range like this;

for i in range(1, num + 1):

if 5%2 == 0:

print("even")

else:

print("odd")

# Python program to find the factorial of a number provided by the user.

# change the value for a different result

num = 7

# uncomment to take input from the user

#num = int(input("Enter a number: "))

factorial = 1

# check if the number is negative, positive or zero

if num < 0:

print("Sorry, factorial does not exist for negative numbers")

elif num == 0:

print("The factorial of 0 is 1")

else:

for i in range(1,num + 1):

factorial = factorial*i

print("The factorial of",num,"is",factorial)

Does this always come out even or is it odd every other one?

I am missing something. Please help me to unerstand(2 votes)- All factorials >= 2! are even since they all contain 2 as a factor. Remember that:

n! = n * (n-1) * ... * 2 * 1(2 votes)