> For the complete documentation index, see [llms.txt](https://jona-projects.gitbook.io/kiwicalc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jona-projects.gitbook.io/kiwicalc/sequences/recursive-sequences.md).

# Recursive Sequences

Recursive sequences are sequences where each item is recursively defined by previous items. The most known example of a recursive sequence is the Fibonacci sequence, named after the famous italian mathematician Fibonacci (11-12th centuries). The first two items in the Fibonacci sequence are \`1, 1\` and each element later is equal to the sum of the two previous items: 

$$
1, 1, 2, 3, 5, 8, 13, 21, 34...
$$

The sequence has been discovered to possess many intriguing qualities, and even take place in natural phenomena. Using this class, one may declare his own Fibonacci sequence, and actually almost any recursive sequence he/she had in mind. You can define and work with the `RecursiveSeq` class.

#### How to create a new recursive sequences

The constructor for the `RecursiveSeq` class requires a string and an Iterable of the first elements of the sequence. The string should represent the recursive sequence, and must follow a specific syntax; The current value of the sequence is written as `a_n`, previous items can be written as `a_{n-1}, a_{n-2} ...` and the next items can be written as `a_{n+1}, a_{n+2} ...`

A recursive sequence is defined by the the definition of the `a_n`. Therefore, the string must always begin with the definition of `a_n`:

```
"a_n = ....."
```

For example, this string represents the Fibonacci sequence, where the initial values of the sequence are $$1,1,2$$:

```python
"a_n = a_{n-1} + a_{n-2}"       
```

And this is a recursive definition for [factorial](https://en.wikipedia.org/wiki/Factorial), where the first elements are 1 and 2.

```python
a_n = a_{n-1} * n
```

There is one key concept one has to remember when entering the first elements of a recursive sequence to this interface; For each previous item you refer to in the string, you have to add one more initial value. For example, if only refer to `a_n` in the string, you need to enter at least 1 initial value, but if you also refer to `a_{n-1}`, you need to enter at least 2 initial values, and so on. That's why factorial requires 2 starting values, and Fibonacci takes 3 starting values. Here is how these sequences will actually look in the code:

```python
fibonacci = RecursiveSeq("a_n = a_{n-1} + a_{n-2}", (1, 1, 2))
my_factorial = RecursiveSeq("a_n = a_{n-1} * n", (1, 2))
```

You can also use more advanced calculations in order to define your own recursive sequence. Here are some examples:

```python
# An example of a custom recursive method.
custom_recursion = RecursiveSeq("a_n = a_{n-1}^2 + 0.5*ln(a_{n-2})", [e, 1, 1.5])
print(f"The custom recursive method is {custom_recursion.at_n(4)} at place 4")
```

#### Fetching the item on the nth place

Declaring the sequence is the most difficult part. Once you manage to that, you can use all the features effortlessly. One of the most important of these features is finding the item on given place. The only thing that one needs to remember here is that unlike arrays, sequences start from the index $$1$$. Thus, index $$1$$ represents the first item, index $$2$$ to represents the second, etc. There are two syntactic approaches to fetch the item in the nth place

1. Use the method `at_n()`
2. `Use indexers ([ ])`

#### Iterating on a sequence

You can iterate on elements of a sequence within a given range using a `for` loop, in two main approaches.

1. Use the `range()` method.
2. Use slicing, in a `([start:stop:step])` format