Week 4 - Day 8 - Recursive Functions

recursion.php

<?php
/**
 * Recursive Functions
 **/
 
/** Solving a Factorial **/

// Non Recursively
function factorial_NoRecursion($x){
    $y = 1;
    for($i = 1; $i <= $x; $i++){
        $y *= $i;
    }
    return $y;
}

echo factorial_NoRecursion(5); // 120

// Recursively
function factorial_Recursion($x){
    if($x <= 1){
        return 1;
    }
    return $x * factorial_Recursion($x - 1);
}

echo factorial_Recursion(5); // 120

// One Line (not suggested for readability)
function factorial_OneLine($x){
    return ($x <= 1) ? 1 : $x * factorial_OneLine($x - 1);
}

echo factorial_OneLine(5); // 120

/** The Fibonacci Sequence **/

// Non Recursively
function fibonacci_NoRecursion($x){
    $previous = -1;
    $result = 1;
    $sum = 0;
    
    for($i = 0; $i <= $x; $i++){
        $sum = $previous + $result;
        $previous = $result;
        $result = $sum;
    }
    
    return $result;
}

echo fibonacci_NoRecursion(10); // 55

// Recursively
function fibonacci_Recursion($x){
    if($x <= 2){
        return 1;
    }
    return fibonacci_Recursion($x - 1) + fibonacci_Recursion($x - 2);
}

echo fibonacci_Recursion(10); // 55

// One Line (VERY VERY UGLY)
function fibonacci_OneLine($x){
    return ($x <= 2) ? 1: fibonacci_OneLine($x - 1) + fibonacci_OneLine($x - 2);
}

echo fibonacci_OneLine(10); // 55

/** Solving Greatest Common Divisor (Euclidean algorithm) **/

// Non Recursively
function gcd_NoRecursion($x, $y){
    while($y != 0){
        $temp = $y;
        $y = $x % $y;
        $x = $temp;
    }
    return $x;
}

echo gcd_NoRecursion(63, 12); // 3

// Recursively
function gcd_Recursion($x, $y){
    if($y == 0){
        return $x;
    }
    return gcd_Recursion($y, $x % $y);
}

echo gcd_Recursion(63, 12); // 3

// One Line
function gcd_OneLine($x, $y){
    return ($y == 0) ? $x : gcd_OneLine($y, $x % $y);
}

echo gcd_OneLine(63, 12); // 3
?>