recursion

this is something that programmers deal with on a regular basis when faced with a problem were some set of tasks needs to be performed repeatedly on a set of data as well as that data’s subsets. many recursive functions can also be carried out with cunning use of loops, which is often better in the long run (as far as big-o-notation is concerned) but when the only way to do something (or the most efficient way) is to do it recursively, then writing a recursive function is the way to go. consider this: you have an array that contains either integers or other arrays, who contain integers or other arrays, and so on. you need to find the highest integer contained by the parent array, regardless of how deep the internal arrays may go. a loop would be a rather difficult way to achieve this considering you have no idea how many tiers to traverse. so recursion is a great way to do it. first write a function that just returns the highest value in the array (for the purposes of this article ill use php but this applies to almost all languages):

function highestVal ($array) {
    $curHigh = 0;
    if (is_array($array)) {
        foreach($array as $val) {
            if ($val > $curHigh) {
                $curHigh = $val;
            }
        }
    } else
        // return some error for incorrect data type
    }
    return $curHigh;
}

passing an array that contains only integers such as array(3,4,8,12,9,8,1) would return 12 in this case. but what if the array was array(3,2,8,9,4,array(12,3),1)? this function might return an error or at the very least not catch the 12 inside the internal array. so modifying the function to check if the $val is an array and recursively calling itself would then return the highest value of the inner array (and if that contained any inner arrays, they would also be assessed):

function highestVal ($array) {
    $curHigh = 0;
    if (is_array($array)) {
        foreach($array as $val) {
            if (is_array($val)) {
                $val = highestVal($val);
            }
            if ($val > $curHigh) {
                $curHigh = $val;
            }
        }
    } else {
        // return some error for incorrect data type
    }
    return $curHigh;
}

there you have it, a function that would return the highest value if an array containing any number of integers or arrays. recursion can have a high cost as far as resources are concerned but this function still maintainss a big-o value of O(n) because it only evaluates each member of each array one time.