{"id":2713,"date":"2017-08-02T12:31:01","date_gmt":"2017-08-02T11:31:01","guid":{"rendered":"http:\/\/www.nivas.hr\/blog\/?p=2713"},"modified":"2017-08-02T14:11:24","modified_gmt":"2017-08-02T13:11:24","slug":"recursions-and-php","status":"publish","type":"post","link":"https:\/\/www.nivas.hr\/blog\/2017\/08\/02\/recursions-and-php\/","title":{"rendered":"Recursions and PHP"},"content":{"rendered":"

Introduction<\/h4>\n

Recursion occurs when something uses a similar version of itself. Recursive procedure is one where at least one of its\u2019 steps calls for a new instance of that very same procedure (broadly speaking we say that function calls itself). It is similar to iteration, with one major difference \u2013 iteration requires predefined number of repetitions, and with recursion one doesn\u2019t need to know in advance how many repetitions there will be. In order to limit the number of repetitions and to avoid or stack overflow there must be a terminating scenario defined, so that the procedure can complete.<\/p>\n

\"\"<\/a><\/p>\n

PHP limits the number of recursive calls and but it’s possible to expand this limit in php.ini file options.<\/p>\n

\"\"<\/a><\/p>\n

http:\/\/php.net\/manual\/en\/pcre.configuration.php<\/a><\/p>\n

All recursive algorithms must have the following:<\/p>\n

1. Base Case – end condition which is the solution to the “simplest” possible problem<\/p>\n

2. Work toward Base Case – making the problem simpler<\/p>\n

3. Recursive Call – using the same algorithm to solve a simpler instance of the problem<\/p>\n

In order to show on a simple example how recursion works we will use the factorials. In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example: 5! = 5 * 4 * 3 * 2 * 1 = 120. Let\u2019s write two simple algorithms to calculate the factorial value of given integer.<\/p>\n

The first example will use iterative approach:<\/p>\n

\r\n$number = 5;\r\nfunction iterativeFactorial($number)\r\n{\r\n if ($number < 0) {\r\n return -1; \/\/initial condition, if number is negative exit the program\r\n }\r\n else if ($number === 0) {\r\n return 1; \/\/factorial of 0 is 1\r\n }\r\n\r\n $factorial = 1;\r\n\r\n if ($number <= 1) return $factorial;\r\n while ($number > 1) {\r\n $factorial *= $number;\r\n $number--;\r\n }\r\n return $factorial;\r\n\r\n}\r\n<\/pre>\n
The second example will use recursive approach:<\/p>\n
\r\n$number = 5;\r\n\r\nfunction recursiveFactorial($number)\r\n{\r\n if($number < 0) {\r\n return -1; \/\/initial condition, if number is negative exit the program\r\n }\r\n else if($number === 0) {\r\n return 1; \/\/base case to exit the recursion\r\n } else {\r\n return $number * recursiveFactorial($number-1); \/\/ recursive call\r\n }\r\n}\r\n<\/pre>\n
How It works<\/h4>\n
Phase One – creating new instances and saving them on stack<\/h5>\n
This phase is characterized by creating new instances of function calls and storing them on stack together with their addresses. In the first call the variable equals to 5 ($number = 5). It goes through initial condition – number must be positive in order to continue down the function. Then the base condition in which if number equals to zero the function will exit recursion. If this doesn\u2019t happen ($number > 0), the function will call itself recursively to derive new instance of itself – 5 * recursiveFactorial( 5 – 1 ). The first instance of the function will wait on stack while the new instance repeats the process, this time $number variable will be equal to 5 \u2013 1, which is 4 and it will compute 4 * recursiveFactorial (3). The process will continue until the $number variable is zero, in which case the function will return 1 and won\u2019t call for the new instance of itself (base condition). At this point all created instances are waiting on stack, together with their return addresses.<\/p>\n
Phase Two – Computing and deleting created instances from stack<\/h5>\n
The returning of 1 wakes up the last created instance of the function on stack (the one that called It – $number = 1), which accepts the return value of 1 and uses it to compute 1 * recursiveFactorial(1-1). This returns 1, the called instance is being deleted from stack and the next instance on stack is being called ($number = 2). After computing 2 * recursiveFactorial(2-1), 2 is returned, the called instance is being deleted from stack and next instance on stack is being called. The process continues until the \u201coldest\u201d instance of function (the first one to be stored on stack, $number = 5) is computed and the final value of 120 returned.<\/p>\n
\"\"<\/a><\/p>\n
Simple test<\/h4>\n
Both functions were ran as php files from command line, using Ubuntu on my laptop. The $number variable was set to 150 and each function was ran 3 times. \u00a0The results showed that on average recursive approach needed approximately 3.7 times more time than iterative.<\/p>\n
Conclusion<\/h4>\n
The main disadvantage of recursive approach is that the algorithm may require large amounts of memory if the recursion goes very deep. This is because when the function is called, a new instance is created in memory. \u00a0Also, it will most likely consume more time than iterative. Both disadvantages can be minimized with tail optimization which is not supported in PHP.<\/p>\n
However there are pros to using recursive approach. It is more elegant and makes code more readable. Because of that it can reduce time needed to write and debug code. This approach is more suitable for\u00a0solving specific problems, when problem can be broken down into smaller pieces (such as sorting algorithms).<\/p>\n
The ultimate goal should always be to get as close as possible to achieving \u2018low memory consumption and short execution time\u2019. It\u2019s up to a programmer to decide which approach works better for a specific problem in a specific development environment.<\/p>\n
<\/h4>\n","protected":false},"excerpt":{"rendered":"
Introduction Recursion occurs when something uses a similar version of itself. Recursive procedure is one where at least one of its\u2019 steps calls for a new instance of that very same procedure (broadly speaking we say that function calls itself). It is similar to iteration, with one major difference \u2013 iteration requires predefined number of…<\/p>\n","protected":false},"author":10,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[7],"tags":[],"_links":{"self":[{"href":"https:\/\/www.nivas.hr\/blog\/wp-json\/wp\/v2\/posts\/2713"}],"collection":[{"href":"https:\/\/www.nivas.hr\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.nivas.hr\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.nivas.hr\/blog\/wp-json\/wp\/v2\/users\/10"}],"replies":[{"embeddable":true,"href":"https:\/\/www.nivas.hr\/blog\/wp-json\/wp\/v2\/comments?post=2713"}],"version-history":[{"count":55,"href":"https:\/\/www.nivas.hr\/blog\/wp-json\/wp\/v2\/posts\/2713\/revisions"}],"predecessor-version":[{"id":2777,"href":"https:\/\/www.nivas.hr\/blog\/wp-json\/wp\/v2\/posts\/2713\/revisions\/2777"}],"wp:attachment":[{"href":"https:\/\/www.nivas.hr\/blog\/wp-json\/wp\/v2\/media?parent=2713"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.nivas.hr\/blog\/wp-json\/wp\/v2\/categories?post=2713"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.nivas.hr\/blog\/wp-json\/wp\/v2\/tags?post=2713"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}