Concept

How can you implement ordinary and tail-recursive summation functions in PHP?

ComputerScienceOne / Recursion

"As another example that actually does something useful, consider the following recursive summation function that takes an array, its size and an index variable. The recursion works as follows: if the index variable has reached the size of the array, it stops and returns zero (the base case). Otherwise, it makes a recursive call to recSum(), incrementing the index variable by 1. When the function returns, it adds the result to the i-th element in the array. To invoke this function we would call it with an initial value of 0 for the index variable: recSum($arr, 0).\n\n1 function recSum($arr, $i) {\n\n2 if($i === count($arr)) {\n\n3 return 0;\n\n4 } else {\n\n5 return recSum($arr, $i+1) + $arr[$i];\n\n6 }\n\n7 }\n\nThis example was not tail-recursive as the recursive call was not the final operation (the sum was the final operation). To make this function tail recursive, we can carry the summation through to each function call ensuring that the summation is done prior to the recursive function call.\n\n1 function recSumTail($arr, $i, $sum) {\n\n2 if($i === count($arr)) {\n\n3 return $sum;\n\n4 } else {\n\n5 return recSumTail($arr, $i+1, $sum + $arr[$i]);\n\n6 }\n\n7 }"

Related Ideas

How can you implement ordinary and tail-recursive summation functions in PHP? | ComputerScienceOne | Bifalgorithm | Bifalgorithm