{"id":1128,"date":"2012-11-09T17:53:13","date_gmt":"2012-11-09T17:53:13","guid":{"rendered":"http:\/\/beta.robertprice.co.uk\/robblog\/?p=1128"},"modified":"2012-11-09T17:53:13","modified_gmt":"2012-11-09T17:53:13","slug":"recursive-functions-in-php","status":"publish","type":"post","link":"http:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/","title":{"rendered":"Recursive Functions In PHP"},"content":{"rendered":"

Recursive functions can be very useful when developing in PHP. <\/p>\n

A recursive function is simply a function that calls itself, but why would you want your function to be able to call itself? <\/p>\n

They are best used when a problem needs to be solved by breaking it up into a smaller instance of itself. Examples of this would be calculation a factorial or the Fibonacci Series<\/a>.<\/p>\n

Let’s take a look at the Fibonacci Series as an example. The series looks like this…<\/p>\n

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …<\/p>\n

It can be described using the following formula, <\/p>\n

Fn<\/sub> = Fn-1<\/sub> + Fn-2<\/sub><\/p>\n

with the seed values, <\/p>\n

F0<\/sub> = 0, F1<\/sub> = 1<\/p>\n

As you can see in the formula’s definition, it has to call itself for n-1 and n-2 to work out the current value for n.<\/p>\n

So how would we write this in PHP?<\/p>\n

A simple function like this should do the trick.<\/p>\n

function fib($n) {\n\tif ($n < 0) {\n\t\treturn NULL;\n\t} elseif ($n === 0) {\n\t\treturn 0;\n\t} elseif ($n === 1 || $n === 2) {\n\t\treturn 1;\n\t} else {\n\t\treturn fib($n-1) + fib($n-2);\n\t}\t \n}<\/pre>\n
As you can see I have added some guard statements, so if $n is 0, we return NULL (as the Fibonacci series starts at 0 and works up from there), for 0 we know the seed value is 0 and for 1 and 2 we know the seed values are 1. As we now know the start of the series, we can call our function to work out any part of the series.<\/p>\n
For very large values of $n, there will be a lot of recursion, and this could use a lot of computer resources. Each call to fib (apart from to values 0, 1 & 2) costs us at least two more calls to fib, and these calls could be making more calls as it recurses. For example, when $n is 19, there would be 8361 calls made to the fib function to calculate the result, and when $n is 29, there would be 1028457 calls. It’s easy to see that although this is a very simple formula, it can end up being very expensive to use.<\/p>\n
However, we can optimise the code and make things easier. We are constantly calculating the same values multiple times, so this should be telling you that this is an ideal candidate for caching.<\/p>\n
Let’s modify our function to keep already calculated values of $n in an array and return those if possible rather than recalculating each call.<\/p>\n
function fib($n) {\n\tstatic $cache;\n\n\tif ($n < 0) {\n\t\treturn NULL;\n\t} elseif ($n === 0) {\n\t\treturn 0;\n\t} elseif ($n === 1 || $n === 2) {\n\t\treturn 1;\n\t} else {\n\t\tif (!(!is_null($cache) && array_key_exists($n, $cache))) {\n\t\t\t$cache[$n] = fib($n-1) + fib($n-2);\n\t\t}\n\t\treturn $cache[$n]; \n\t} \t\n}<\/pre>\n
Here we are using a static variable to persist the $cache between calls. Then before recursively calling the fib function we check if the $cache isn’t null and if the $cache has data stored with the key value of $n. If it doesn’t we calculate the can cache the data. Finally we return the value from the cache.<\/p>\n
Now when we call the function for when $n = 19, our function is only called 35 times, and for $n = 29, our function is only called 55 times. That’s saved us 1028402 calls!<\/p>\n
I hope this has been a useful quick look at recursive functions using PHP.<\/p>\n","protected":false},"excerpt":{"rendered":"
Recursive functions can be very useful when developing in PHP. A recursive function is simply a function that calls itself, but why would you want your function to be able to call itself? They are best used when a problem needs to be solved by breaking it up into a smaller instance of itself. Examples … Continue reading “Recursive Functions In PHP”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[2],"tags":[50],"class_list":["post-1128","post","type-post","status-publish","format-standard","hentry","category-dev","tag-php"],"yoast_head":"\nRecursive Functions In PHP - Robert Price<\/title>\n<meta name=\"description\" content=\"Recursive functions are very useful with writing PHP. This is an overview on how to write and use them, using the Fibonacci series as an example.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/\" \/>\n<meta property=\"og:locale\" content=\"en_GB\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Recursive Functions In PHP - Robert Price\" \/>\n<meta property=\"og:description\" content=\"Recursive functions are very useful with writing PHP. This is an overview on how to write and use them, using the Fibonacci series as an example.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/\" \/>\n<meta property=\"og:site_name\" content=\"Robert Price\" \/>\n<meta property=\"article:published_time\" content=\"2012-11-09T17:53:13+00:00\" \/>\n<meta name=\"author\" content=\"rob\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"rob\" \/>\n\t<meta name=\"twitter:label2\" content=\"Estimated reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/\"},\"author\":{\"name\":\"rob\",\"@id\":\"http:\/\/www.robertprice.co.uk\/robblog\/#\/schema\/person\/fac6d5b076e0e14e1fb13e15b542a6c5\"},\"headline\":\"Recursive Functions In PHP\",\"datePublished\":\"2012-11-09T17:53:13+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/\"},\"wordCount\":472,\"keywords\":[\"PHP\"],\"articleSection\":[\"Dev\"],\"inLanguage\":\"en-GB\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/\",\"url\":\"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/\",\"name\":\"Recursive Functions In PHP - Robert Price\",\"isPartOf\":{\"@id\":\"http:\/\/www.robertprice.co.uk\/robblog\/#website\"},\"datePublished\":\"2012-11-09T17:53:13+00:00\",\"author\":{\"@id\":\"http:\/\/www.robertprice.co.uk\/robblog\/#\/schema\/person\/fac6d5b076e0e14e1fb13e15b542a6c5\"},\"description\":\"Recursive functions are very useful with writing PHP. This is an overview on how to write and use them, using the Fibonacci series as an example.\",\"breadcrumb\":{\"@id\":\"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/#breadcrumb\"},\"inLanguage\":\"en-GB\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/www.robertprice.co.uk\/robblog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Recursive Functions In PHP\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/www.robertprice.co.uk\/robblog\/#website\",\"url\":\"http:\/\/www.robertprice.co.uk\/robblog\/\",\"name\":\"Robert Price\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/www.robertprice.co.uk\/robblog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-GB\"},{\"@type\":\"Person\",\"@id\":\"http:\/\/www.robertprice.co.uk\/robblog\/#\/schema\/person\/fac6d5b076e0e14e1fb13e15b542a6c5\",\"name\":\"rob\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-GB\",\"@id\":\"http:\/\/www.robertprice.co.uk\/robblog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/6f0eb511179100a4e968abc70403e33686e6ab3e992e392bedd2ccac01da666c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/6f0eb511179100a4e968abc70403e33686e6ab3e992e392bedd2ccac01da666c?s=96&d=mm&r=g\",\"caption\":\"rob\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Recursive Functions In PHP - Robert Price","description":"Recursive functions are very useful with writing PHP. This is an overview on how to write and use them, using the Fibonacci series as an example.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/","og_locale":"en_GB","og_type":"article","og_title":"Recursive Functions In PHP - Robert Price","og_description":"Recursive functions are very useful with writing PHP. This is an overview on how to write and use them, using the Fibonacci series as an example.","og_url":"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/","og_site_name":"Robert Price","article_published_time":"2012-11-09T17:53:13+00:00","author":"rob","twitter_card":"summary_large_image","twitter_misc":{"Written by":"rob","Estimated reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/#article","isPartOf":{"@id":"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/"},"author":{"name":"rob","@id":"http:\/\/www.robertprice.co.uk\/robblog\/#\/schema\/person\/fac6d5b076e0e14e1fb13e15b542a6c5"},"headline":"Recursive Functions In PHP","datePublished":"2012-11-09T17:53:13+00:00","mainEntityOfPage":{"@id":"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/"},"wordCount":472,"keywords":["PHP"],"articleSection":["Dev"],"inLanguage":"en-GB"},{"@type":"WebPage","@id":"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/","url":"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/","name":"Recursive Functions In PHP - Robert Price","isPartOf":{"@id":"http:\/\/www.robertprice.co.uk\/robblog\/#website"},"datePublished":"2012-11-09T17:53:13+00:00","author":{"@id":"http:\/\/www.robertprice.co.uk\/robblog\/#\/schema\/person\/fac6d5b076e0e14e1fb13e15b542a6c5"},"description":"Recursive functions are very useful with writing PHP. This is an overview on how to write and use them, using the Fibonacci series as an example.","breadcrumb":{"@id":"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/#breadcrumb"},"inLanguage":"en-GB","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.robertprice.co.uk\/robblog\/recursive-functions-in-php\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/www.robertprice.co.uk\/robblog\/"},{"@type":"ListItem","position":2,"name":"Recursive Functions In PHP"}]},{"@type":"WebSite","@id":"http:\/\/www.robertprice.co.uk\/robblog\/#website","url":"http:\/\/www.robertprice.co.uk\/robblog\/","name":"Robert Price","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/www.robertprice.co.uk\/robblog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-GB"},{"@type":"Person","@id":"http:\/\/www.robertprice.co.uk\/robblog\/#\/schema\/person\/fac6d5b076e0e14e1fb13e15b542a6c5","name":"rob","image":{"@type":"ImageObject","inLanguage":"en-GB","@id":"http:\/\/www.robertprice.co.uk\/robblog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/6f0eb511179100a4e968abc70403e33686e6ab3e992e392bedd2ccac01da666c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/6f0eb511179100a4e968abc70403e33686e6ab3e992e392bedd2ccac01da666c?s=96&d=mm&r=g","caption":"rob"}}]}},"_links":{"self":[{"href":"http:\/\/www.robertprice.co.uk\/robblog\/wp-json\/wp\/v2\/posts\/1128","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.robertprice.co.uk\/robblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.robertprice.co.uk\/robblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.robertprice.co.uk\/robblog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.robertprice.co.uk\/robblog\/wp-json\/wp\/v2\/comments?post=1128"}],"version-history":[{"count":0,"href":"http:\/\/www.robertprice.co.uk\/robblog\/wp-json\/wp\/v2\/posts\/1128\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.robertprice.co.uk\/robblog\/wp-json\/wp\/v2\/media?parent=1128"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.robertprice.co.uk\/robblog\/wp-json\/wp\/v2\/categories?post=1128"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.robertprice.co.uk\/robblog\/wp-json\/wp\/v2\/tags?post=1128"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}