{"id":196,"date":"2021-03-03T20:16:35","date_gmt":"2021-03-03T20:16:35","guid":{"rendered":"https:\/\/gnikesh.com\/?p=196"},"modified":"2021-03-05T19:28:48","modified_gmt":"2021-03-05T19:28:48","slug":"tail-recursive-nth-fibonacci-number","status":"publish","type":"post","link":"https:\/\/gnikesh.com\/index.php\/2021\/03\/03\/tail-recursive-nth-fibonacci-number\/","title":{"rendered":"Tail Recursive nth Fibonacci Number"},"content":{"rendered":"\n

<\/p>\n\n\n\n

When a function is called, it gets it’s own stack to store the parameters, and it’s local variables. So, an implementation of recursive function that stores a local variable and waits for the values returned from another recursive call to the function and so on would require stack to store the results. Let’s see an example of a recursive function implemented in Standard ML<\/a> (SML), a general-purpose functional programming language,<\/p>\n\n\n\n\n\n\n\n

fun factorial n = \n\tif n = 0 then 1\n\telse n * (factorial (n - 1))<\/code><\/pre>\n\n\n\n
I will base my writing for a functional programming language and will use SML as my language of choice. Python, however, does not optimize tail recursive calls by default. And we are still bounded by default maximum recursion depth of 1000 (we can manually increase this limit). However, I will also write python equivalent code.<\/p>\n\n\n\nPython equivalent code<\/span>
\n
\ndef factorial(n):\n    if n == 0:\n        return 1\n    else:\n        return n * factorial(n - 1)\n<\/code><\/pre>\n<\/div>\n\n\n\n
<\/p>\n\n\n\n
The above code that calculates the factorial of a given number n, requires stack to store all values of n unless base condition is met. So, if n is really big, we can see how stack space grows linearly with n. One way of solving this is to write the above recursive function using tail recursion. We call a function tail recursive if  no computation happens after a recursive call. In our case the above factorial()<\/em> function would look like<\/p>\n\n\n\n
(* HELPER FUNCTION TO CALCULATE FACTORIAL *)\nfun calculate_fact r n =  \n\tif n = 0 then r\n\telse calculate_fact (r * n) (n - 1)\n\n(* MAIN FUNCTION *)\nfun factorial n = calculate_fact 1 n <\/code><\/pre>\n\n\n\nPython equivalent code<\/span>
\n
def factorial(n, r=1):\n    if n == 0:\n        return r\n    else:\n        return factorial(n - 1, r * n)\n<\/code><\/pre>\n<\/div>\n\n\n\n
<\/p>\n\n\n\n
In this above program, we do not need to save the local variables as we did in the first program because they are not referenced after the recursive call. Hence, compiler can optimize the tail recursion and there’s no use of saving the current function’s stack frame. One way of thinking tail recursion would be as an iteration in disguise as used in imperative language. For example, this above tail recursion could be coded as<\/p>\n\n\n\n
def factorial(n):\n    r = 1\n    while n != 0:\n        r = r * n\n        n = n - 1\n    return r<\/code><\/pre>\n\n\n\n
One thing to note is, ideally we would want tail recursion not to be bounded by maximum recursion depth. However, python has a default recursion depth of 1000 and we cannot go past this limit without increasing it. But functional languages do not have this limit.<\/p>\n\n\n\n
Now let’s look into these concept in case of Fibonacci sequence.<\/p>\n\n\n\n
Fibonacci sequence<\/strong> is generated by Fibonacci numbers where each number is the sum of two preceding ones, starting from 0 and 1. The sequence goes like 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ….. and so on. So, \"F_0 = 0, F_1 = 1\" and for \"n > 1\", \"F_n = F_{n-1} + F_{n-2}\". Some implementation ignores 0 and, \"F_1 = F_2 = 1\" is taken as starting of the sequence. We will use the  convention that 1 is the first element in the sequence.<\/p>\n\n\n\n
We can see that numbers can get really big quickly. Hence, to generate \"n^{th}\" Fibonacci number, we might want to evaluate the performance of our algorithm even if it gives correct results for smaller value of \"n\". Let’s see some approaches, their pitfalls, and improvements we could make.<\/p>\n\n\n\n
A straight forward solution to calculate \"n^{th}\" Fibonacci number is to recursively calculate sum of \"(n - 1)^{th}\" and \"(n - 2)^{th}\" Fibonacci numbers.<\/p>\n\n\n\n
fun fibonacci n =\n\tif n = 0 then 0\n \telse if n = 1 then 1\n\t\telse (fibonacci (n - 1)) + (fibonacci (n - 2));<\/code><\/pre>\n\n\n\nPython equivalent code<\/span>
\n
def fibonacci(n):\n    if n == 0:\n        return 0\n    elif n == 1:\n        return 1\n    else:\n        return fibonacci(n - 1) + fibonacci (n - 2)<\/code><\/pre>\n<\/div>\n\n\n\n
<\/p>\n\n\n\n
Running this python equivalent function fibonacci(35)<\/em> took 4.0823 seconds in my computer.
If we analyze this function, we can see two main drawbacks of this implementation, <\/p>\n\n\n\n
  1. It is not tail recursive and so requires stack space to run.<\/li>
  2. It repeatedly calls the fibonacci<\/em> function on smaller numbers i.e. recomputing previously computed results. For example,
         fibonacci (7)
    => fibonacci (6) + fibonacci (5)
    => fibonacci (5) + fibonacci (4) + fibonacci (5)
    => fibonacci (4) + fibonacci (3) + fibonacci (4) + fibonacci (5) … and so on<\/em>
    <\/li><\/ol>\n\n\n\n
    Time complexity: Exponential
    Space complexity: \"O(n)\" (stack usage)<\/p>\n\n\n\n
    Let’s write this fibonacci<\/em> function using tail recursion.  <\/p>\n\n\n\n
    (* HELPER FUNCTION TO CALCULATE FIBONACCI NUMBER *)\nfun fib_calculate prev curr n =\n\tif n = 0 orelse n = 1 then curr\n\telse fib_calculate curr (prev + curr) (n - 1);\n\n(* MAIN FUNCTION TO ABSTRACT prev AND curr VALUES *)\nfun fibonacci n = fib_calculate 0 1 n;<\/code><\/pre>\n\n\n\nPython equivalent code<\/span>
    \n
    def fibonacci(n, prev=0, curr=1):\n    if n == 0 or n == 1:\n        return curr\n    else:\n        return fibonacci(n - 1, curr, prev + curr)<\/code><\/pre>\n<\/div>\n\n\n\n
    <\/p>\n\n\n\n
    Running this function fibonacci(35)<\/em> took \"0.0000\" seconds in my computer. Here, we do not recompute previously computed results and also, stack space is constant and does not grow with the size of input n. For this implementation,<\/p>\n\n\n\n
    Time complexity: \"O(n)\"
    Space complexity: \"O(1)\"<\/p>\n\n\n\n
    So, we reduced the exponential time complexity to linear and stack space complexity from linear to constant by using tail recursion and preventing duplicate computations. <\/p>\n\n\n\n
    Fun Fact: There exists mathematical formula we can calculate \"n^{th}\" Fibonacci number with constant time and space complexity. It’s called Binet’s Formula<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
    When a function is called, it gets it’s own stack to store the parameters, and it’s local variables. So, an implementation of recursive function that stores a local variable and waits for the values returned from another recursive call to the function and so on would require stack to store the results. Let’s see an […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[7,12],"tags":[19,20],"class_list":["post-196","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-functional-programming","tag-computer","tag-programming"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/posts\/196","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/comments?post=196"}],"version-history":[{"count":50,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/posts\/196\/revisions"}],"predecessor-version":[{"id":471,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/posts\/196\/revisions\/471"}],"wp:attachment":[{"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/media?parent=196"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/categories?post=196"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/gnikesh.com\/index.php\/wp-json\/wp\/v2\/tags?post=196"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}