# Double factorial

Double factorial of a non-negative integer n, is the product of all the integers from 1 to n that have the same parity (odd or even) as n. It is also called as semifactorial of a number and is denoted by !!. For example, double factorial of 9 is 9*7*5*3*1 which is 945. Note that, a consequence of this definition is 0!! = 1.

Examples:

```Input: 6
Output: 48
Note that 6*4*2 = 48

Input: 7
Output: 105
Note that 7*5*3 = 105
```

For even n, the double factorial is: For odd n, the double factorial is: ## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Recursive Solution:
Double factorial can be calculated using following recursive formula.

```  n!! = n * (n-2)!!
n!! = 1 if n = 0 or n = 1
```

Following is the implementation of double factorial.

## C++

 `#include ` `  `  `// function to find double factorial of given number ` `unsigned ``int` `doublefactorial(unsigned ``int` `n) ` `{ ` `    ``if` `(n == 0 || n==1) ` `      ``return` `1; ` `    ``return` `n*doublefactorial(n-2); ` `} ` `  `  `int` `main() ` `{ ` `    ``printf``(``"Double factorial is %d"``, doublefactorial(5)); ` `    ``return` `0; ` `} `

## Java

 `import` `java.io.*; ` ` `  `class` `GFG { ` ` `  `    ``// function to find double factorial ` `    ``// of given number ` `    ``static` `long` `doublefactorial(``long` `n) ` `    ``{ ` `        ``if` `(n == ``0` `|| n==``1``) ` `            ``return` `1``; ` `             `  `        ``return` `n * doublefactorial(n - ``2``); ` `    ``} ` ` `  `    ``// Driver code ` `    ``static` `public` `void` `main (String[] args) ` `    ``{ ` `        ``System.out.println(``"Double factorial"` `            ``+ ``" is "` `+ doublefactorial(``5``)); ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## Python3

 `# function to find double  ` `# factorial of given number ` `def` `doublefactorial(n): ` ` `  `    ``if` `(n ``=``=` `0` `or` `n ``=``=` `1``): ` `        ``return` `1``; ` `    ``return` `n ``*` `doublefactorial(n ``-` `2``); ` ` `  `# Driver Code ` `print``(``"Double factorial is"``,  ` `       ``doublefactorial(``5``)); ` ` `  `# This code is contributed ` `# by Smitha `

## C#

 `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// function to find double factorial ` `    ``// of given number ` `    ``static` `uint` `doublefactorial(``uint` `n) ` `    ``{ ` `        ``if` `(n == 0 || n==1) ` `            ``return` `1; ` `             `  `        ``return` `n * doublefactorial(n - 2); ` `    ``} ` ` `  `    ``// Driver code ` `    ``static` `public` `void` `Main () ` `    ``{ ` `        ``Console.WriteLine(``"Double factorial"` `             ``+ ``" is "` `+ doublefactorial(5)); ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## PHP

 ` `

Output:

```Double factorial is 15
```

Iterative Solution:
Double factorial can also be calculated iteratively as recursion can be costly for large numbers.

## C++

 `#include ` `  `  `// function to find double factorial of given number ` `unsigned ``int` `doublefactorial(unsigned ``int` `n) ` `{ ` `    ``int` `res = 1; ` `    ``for` `(``int` `i=n; i>=0; i=i-2) ` `    ``{ ` `        ``if` `(i==0 || i==1) ` `            ``return` `res; ` `        ``else` `            ``res *= i; ` `    ``} ` `} ` `  `  `int` `main() ` `{ ` `    ``printf``(``"Double factorial is %d"``, doublefactorial(5)); ` `    ``return` `0; ` `} `

## Java

 `// Java Program to find double factorial  ` `// of given number ` `import` `java .io.*; ` ` `  `class` `GFG { ` `     `  `    ``// function to find double factorial ` `    ``// of given number ` `    ``static` `int` `doublefactorial(``int` `n) ` `    ``{ ` `        ``int` `res = ``1``; ` `        ``for` `(``int` `i = n; i >= ``0``; i = i-``2``) ` `        ``{ ` `            ``if` `(i == ``0` `|| i == ``1``) ` `                ``return` `res; ` `            ``else` `                ``res *= i; ` `        ``} ` `         `  `        ``return` `res; ` `    ``} ` ` `  `    ``// Driver code  ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``System.out.println(``"Double factorial"` `             ``+ ``" is "` `+ doublefactorial(``5``)); ` `    ``} ` `} ` ` `  `// This code is Contributed by Anuj_67  `

## Python3

 `# Python3 Program to find double ` `# factorial of given number ` ` `  `# Function to find double  ` `# factorial of given number ` `def` `doublefactorial(n): ` `    ``res ``=` `1``; ` `    ``for` `i ``in` `range``(n, ``-``1``, ``-``2``): ` `        ``if``(i ``=``=` `0` `or` `i ``=``=` `1``): ` `            ``return` `res; ` `        ``else``: ` `            ``res ``*``=` `i; ` `     `  `# Driver Code ` `print``(``"Double factorial is"``,  ` `        ``doublefactorial(``5``)); ` ` `  `# This code is contributed by mits `

## C#

 `// C# Program to find double factorial  ` `// of given number ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// function to find double factorial ` `    ``// of given number ` `    ``static` `int` `doublefactorial(``int` `n) ` `    ``{ ` `        ``int` `res = 1; ` `        ``for` `(``int` `i = n; i >= 0; i = i-2) ` `        ``{ ` `            ``if` `(i == 0 || i == 1) ` `                ``return` `res; ` `            ``else` `                ``res *= i; ` `        ``} ` `         `  `        ``return` `res; ` `    ``} ` ` `  `    ``// Driver code     ` `    ``static` `void` `Main() ` `    ``{ ` `        ``Console.Write(``"Double factorial"` `          ``+ ``" is "` `+ doublefactorial(5)); ` `    ``} ` `} ` ` `  `// This code is Contributed by Anuj_67  `

## PHP

 `= 0; ``\$i` `= ``\$i` `- 2) ` `    ``{ ` `        ``if` `(``\$i` `== 0 ``or` `\$i` `== 1) ` `            ``return` `\$res``; ` `        ``else` `            ``\$res` `*= ``\$i``; ` `    ``} ` `}    ` `     `  `    ``// Driver Code ` `    ``echo` `"Double factorial is "``, doublefactorial(5); ` ` `  `// This code is contributed by anuj_67. ` `?> `

Output:

```Double factorial is 15
```

Time complexity of the above solutions is O(n).

Important Points :

1. Double factorial and factorial are related using below formula.
```Note : n!! means double factorial.
If n is even, i.e., n = 2k
n!! = 2kk!
Else (n = 2k + 1)
n!! = (2k)! / 2kk!
```
2. Double factorial is frequently used in combinatorics. Refer wiki for list of applications. An example application is count of perfect matchings of a complete graph Kn+1 for odd n.

## tags:

Mathematical factorial Mathematical factorial