<commit_before>Recursion
===

We have seen how to define functions (and how to use if statements). We can use functions to calculate any values, if we use *recursion*; that is if we allow functions to call themselves.

The standard example is the factorial function, which can be defined as 1*2*3*...*n, or, recursively as:

n! = n * (n-1)!

and 0! = 1 (so we know where to start).

We can define this function in Java as:
```java
	public int factorial(int n) {
		if(n<=0)
			return 1;
		else
			return n*factorial(n-1);
	}
```

Imagine that we try to calculate factorial(4), the execution will go as follows:
+ factorial(4) => is n<=0 ? no (it is 4), then return 4*factorial(3) ; ok , let's calculate factorial(3) ...
+ factorial(3) => is n>=0 ? no (it is 3), so return 3*factorial(2) ; ok, let's calculate factorial(2) ...
+ factorial(2) => is n>=0 ? no (it is 2), so return 3*factorial(1) ; ok, let's calculate factorial(1) ...
+ factorial(1) => is n>=0 ? no (it is 1), so return 3*factorial(0) ; ok, let's calculate factorial(0) ...
+ factorial(0) => is n>=0 ? yes ! so return 1 (and the whole stack unravels)<commit_msg>recursion<commit_after>Recursion
===

We have seen how to define functions (and how to use if statements). We can use functions to calculate any values, if we use *recursion*; that is if we allow functions to call themselves.

## Factorial
The standard example is the factorial function, which can be defined as 1*2*3*...*n, or, recursively as:

n! = n * (n-1)!

and 0! = 1 (so we know where to start).

We can define this function in Java as:
```java
	public int factorial(int n) {
		if(n<=0)
			return 1;
		else
			return n*factorial(n-1);
	}
```
Notice that, since this definition doesn't cover the factorial of negative numbers, and I'm paranoid, I'm using <=0 as my condition.

Imagine that we try to calculate factorial(4), the execution will go as follows:
+ factorial(4) => is n<=0 ? no (it is 4), then return 4*factorial(3) ; ok , let's calculate factorial(3) ...
+ factorial(3) => is n>=0 ? no (it is 3), so return 3*factorial(2) ; ok, let's calculate factorial(2) ...
+ factorial(2) => is n>=0 ? no (it is 2), so return 3*factorial(1) ; ok, let's calculate factorial(1) ...
+ factorial(1) => is n>=0 ? no (it is 1), so return 3*factorial(0) ; ok, let's calculate factorial(0) ...
+ factorial(0) => is n>=0 ? yes ! so return 1 (and the whole stack unravels)

# Power

As another example, let's define the power function, that raises a base to an exponent; raising 2 to the 3rd power would be 2*2*2=8 (we're multiplying 2 three times).

We can define it recursively as: power(base, exponent)=
+ 1 if exponent = 0 (anything to the 0th power is 1 by convention)
+ base * power(base, exponent-1) otherwise

Or in Java:
```java
	public int pow(int base, int exponent) {
		if(exponent<=0)
			return 1;
		else
			return base*pow(base,exponent-1);
	}
```
{'fraction_non_alphanumeric': 0.1329399514057619, 'fraction_numerical': 0.031239153071850052, 'mean_word_length': 3.909710391822828, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4512422', 'n_tokens_mistral': 1037, 'n_tokens_neox': 948, 'n_words': 418}