#### Partitions

"""
partitions_recursive(n)

Finds partitions of an integer using recursion.

A partition of a positive integer n, also called an integer partition,
is a way of writing n as a sum of positive integers.

There are 7 partitions of 5:
5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Partitions of n is equal to the sum of partitions of n with k parts.

P \\left ( n \\right ) = \\sum_{k=1}^{n} P_{k} \\left ( n \\right )

Partitions of n with k parts is the sum of
partitions of n-1 with k-1 parts and,
partitions of n-k with k parts.

P_{k}\\left ( n \\right ) =
P_{k-1}\\left ( n - 1 \\right ) + P_{k}\\left ( n - k \\right )

# Example
julia
partitions_recursive(0)      # returns 1
partitions_recursive(1)      # returns 1
partitions_recursive(10)     # returns 42
partitions_recursive(-1)     # returns DomainError

# References
- Partitions of a positive integer -- https://en.wikipedia.org/wiki/Partition_function_(number_theory)
- Partitions of a positive integer -- https://www.whitman.edu/mathematics/cgt_online/book/section03.03.html

# Contributor
- [Vaishakh C R](https://github.com/Whiteshark-314)
"""
function partitions_recursive(n::N)::BigInt where {N<:Integer}
n < 0 && throw(
DomainError(
"partitions_recursive() only accepts positive integral values",
),
)
if n == 0
return one(BigInt)
end
k = collect(1:n)
return sum(partitions_k_parts.(n, k))
end

function partitions_k_parts(n, k)
n < 0 ||
k < 0 && throw(
DomainError(
"partitions_k_parts() only accepts positive integral values",
),
)
if (n == 0 && k == 0) || (n > 0 && k == 1) || n == k
return one(BigInt)
elseif k == 0 || k > n
return zero(BigInt)
end
return partitions_k_parts(n - 1, k - 1) + partitions_k_parts(n - k, k)
end
{"ft_lang_label":"__label__en","ft_lang_prob":0.51520306,"math_prob":0.99406093,"size":1704,"snap":"2022-27-2022-33","text_gpt3_token_len":545,"char_repetition_ratio":0.19647059,"word_repetition_ratio":0.094736844,"special_character_ratio":0.36150235,"punctuation_ratio":0.108552635,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9996574,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-07-02T11:33:32Z\",\"WARC-Record-ID\":\"<urn:uuid:a1c78298-76cb-49af-85d5-511144dde694>\",\"Content-Length\":\"87162\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:542b0d86-1883-4ca9-b835-6ab6f55976e2>\",\"WARC-Concurrent-To\":\"<urn:uuid:2c35d494-7b9e-41e9-9aed-e170e5ba651e>\",\"WARC-IP-Address\":\"76.76.21.21\",\"WARC-Target-URI\":\"https://the-algorithms.com/algorithm/partitions\",\"WARC-Payload-Digest\":\"sha1:2ISTKSS5WBFK3JZGDKXKJSNOE4U3I7OO\",\"WARC-Block-Digest\":\"sha1:DY4VO3ACTJHG3A6CFDT6BLJ65S4WDGNC\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-27/CC-MAIN-2022-27_segments_1656104054564.59_warc_CC-MAIN-20220702101738-20220702131738-00245.warc.gz\"}"}