 # Recursive implementations of some Maths sequences and series in PHP

Created:28 Jul 2017 17:54:44 , in  Maths

In this article I give a couple of PHP implementations of popular Maths sequences and series. Broadly, each piece of code given returns nth term of a sequence / series. Each of the implementations depends on linear recursion. Each of the functions a is a static methods of class Recursion.

Sequences and series implemented in this article include factorial sequence, harmonic series, Fibonacci sequence and one of Recaman's sequences.

## Factorial sequence

Factorial, denoted n!, is a non-negative integer which is a product of all positive integers from 0 through n!. 0! is 1.

Here is recursive implementation of factorial sequence in PHP:

``````
public static function factorial(\$n){
// 0! is 1
if (\$n === 0){
return 1;
} else {
return \$n * self::factorial(\$n - 1);
}
}
``````

Here are a couple of examples of use:

``````
Recursion::factorial(1)
=> 1

Recursion::factorial(4)
=> 24 // 1 * 2 * 3 * 4
``````

## Harmonic series

Harmonic series is defined as a sum from n = 1 to infinity of 1 / n. Or in other words it is this: 1 + 1 / 2 + 1/3 + ... + 1 / n.

My implementation of harmonic series is very similar to what was seen above for factorial function.

``````
public static function harmonic(\$n){
// series defined for n >= 1
if(\$n < 1){return null;}

if(\$n === 1){
return 1;
}

return (1 / \$n) + self::harmonic(\$n - 1);
}
``````

Example of use:

``````
Recursion::harmonic_recursive(1);
=> 1

Recursion::harmonic_recursive(4);
=> 1+1/2+1/3+1/4
``````

## Fibonacci sequence

The Key to this sequence is the recurrence relation F(n) = F(n-1) + F(n - 2). In other words nth term of the sequence is a sum of the two previous terms.

Method fibonacci below returns an array of two last terms found in the sequence previously. This helps reducing number of recursive calls significantly. Similar technique can be employed successfully for sequences, whose nth term is based on more than two previous terms.

Seed values for my implementation (first two terms) are 0 and 1. Terms are counted from 0.

``````
public static function fibonacci(\$n){
if(\$n < 2){
return array(1,0);
}else{
\$items = self::fibonacci(\$n-1);
// nth + nth -1 number is returned here
return array(\$items + \$items, \$items );
}
}
``````

Examples of use:

``````
Recursion::fibonacci(3);
// 4th term of Fibonacci sequence is 2
=>array(2,1)

Recursion::fibonacci(5)
// 6th term of Fibonacci sequence is 5
=>array(5,3)
``````

## Recaman's sequence

Recaman's sequence is defined for n >= 0. If R(n) stands for nth term of Recaman sequence, then R(0) = 0. Terms of this sequence for n greater than 0 are defined as follows: R(n) = R(n-1) - n if R(n) is positive and not in the sequence yet, otherwise R(n) = R(n -1) + n.

In my implementation of Recaman's sequence an auxiliary variable k is employed. It increases from 0 to n. Previous code examples always relied upon variabale n, which decreased from n to 0 or 1.

Regarding time complexity, before adding a new term the method searches through array or previously added terms to find whether the new term is a duplicate. Clearly, it is not an optimal solution. This behavior can be avoided for example through storing arrays of already found even and odd terms and checking the new term only against one of them.

Intermediate calls to recaman return an array. The last one always returns the nth term of Recaman's sequence.

``````
public static function recaman(\$n,\$k = 0,\$sequence = array()){

// first term
if(\$k === 0){
\$sequence[] = 0;
}

// stop if \$n reached or when n < 0
if(\$n === \$k or \$n < 0){
return \$sequence[\$k];
}

\$last = \$sequence[ \$k ];

if(\$last - (\$k + 1) > 0 and !in_array(\$last - (\$k + 1) ,\$sequence)){
\$sequence[] = \$last - (\$k + 1);
}else{
\$sequence[] = \$last + (\$k + 1);
}

return self::recaman(\$n,\$k + 1,\$sequence);
}
``````

Some code examples:

``````
Recursion::recaman(3);
=> 6

Recursion::recaman(5);
=> 7

Recursion::recaman(6);
=> 13
``````

## Final thoughts

This article contains some nice pieces of recursive code written in PHP. Employing ideas gathered in them makes it possible to program many other Maths series and sequences with little to none effort.

This post was updated on 28 Jul 2017 18:25:24

### Author Author of the this article - Sylwester Wojnowski - is a sWWW web developer. He has been writing computer code for the websites and web applications since 1998.

©Copyright, 2022 Sylwester Wojnowski. This article may not be reproduced or published as a whole or in parts without permission from the author. If you share it, please give author credit and do not remove embedded links.

Computer code, if present in the article, is excluded from the above and licensed under GPLv3.

### Citation

Wojnowski, Sylwester. "Recursive implementations of some Maths sequences and series in PHP." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/recursive-implementations-of-some-maths-sequences-and-series-in-php

## You might also like

• ### Turning OOP class to graph for better code composition and understanding

MATHS

• ### Using arrow functions for recursive post-order tree traversal

MATHS

• ### Transforming range of variable to 0 to 1 and custom ranges

MATHS

• ### Checking trees for sameness with recursion and spaceship operator in PHP

MATHS

• ### Two indispensable formulas for percentages

MATHS

Allowed BB Code - style tags: [b][/b], [i][/i], [code=text][/code],[code=javascript][/code],[code=php][/code],[code=bash][/code],[code=css][/code],[code=html][/code]

I constent to processing my data given through this form for purposes of a reply by the administrator of this website.