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 a recursive method sum the elements of an array?ComputerScienceOne · Recursion
- How can a for loop compute a generalized summation in PHP?ComputerScienceOne · Summation
- How can recursion be made tail-recursive in C?ComputerScienceOne · Recursion
- How can recursive functions be written in C?ComputerScienceOne · Recursion
- What happens when a function calls itself?ComputerScienceOne · Recursion
- How is recursion implemented in Java?ComputerScienceOne · Recursion
- How can a summation loop be generalized to sum up to a variable n?ComputerScienceOne · Summation
- How are arrays passed to functions in C?ComputerScienceOne · Using Arrays with Functions