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[0] + $items[1], $items[0] );
  }
}

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

Tags:  php ,  recursion