16 - Recursive Functions.ipynb

{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"4_recursive_functions.ipynb","version":"0.3.2","provenance":[]},"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"}},"cells":[{"metadata":{"id":"2un6HEflRbVI","colab_type":"text"},"cell_type":"markdown","source":["# Recurison"]},{"metadata":{"id":"pouXX8gWRbVJ","colab_type":"text"},"cell_type":"markdown","source":["We know that in Python, a function can call other functions. It is even possible for the function to call itself. These type of construct are termed as recursive functions."]},{"metadata":{"id":"ZVWIU4QvRbVK","colab_type":"text"},"cell_type":"markdown","source":["# Example:"]},{"metadata":{"id":"mnaRd5dzRbVL","colab_type":"code","outputId":"180bb25b-9f63-42cb-fbc9-e19c6eb88d7a","executionInfo":{"status":"error","timestamp":1547750678182,"user_tz":-330,"elapsed":1197,"user":{"displayName":"Applied AI Course","photoUrl":"https://lh3.googleusercontent.com/-EsJzSyawCkQ/AAAAAAAAAAI/AAAAAAAADag/xYU9KO6AZf4/s64/photo.jpg","userId":"06629147635963609455"}},"colab":{"base_uri":"https://localhost:8080/","height":128}},"cell_type":"code","source":["#python program to print factorial of a number using recurion\n","\n","def factorial(num):\n","    \"\"\"\n","    This is a recursive function to find the factorial of a given number\n","    \"\"\"\n","    return 1 if num == 1 else (num * factorial(num-1))\n","\n","num = 5\n","print \"Factorial of {0} is {1} \".format(num, factorial(num))\n"],"execution_count":1,"outputs":[{"output_type":"error","ename":"SyntaxError","evalue":"ignored","traceback":["\u001b[0;36m  File \u001b[0;32m\"<ipython-input-1-fd7c2b2fd4ce>\"\u001b[0;36m, line \u001b[0;32m9\u001b[0m\n\u001b[0;31m    print \"Factorial of {0} is {1} \".format(num, factorial(num))\u001b[0m\n\u001b[0m                                   ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"]}]},{"metadata":{"id":"s2ewPFszRbVR","colab_type":"text"},"cell_type":"markdown","source":["# Advantages"]},{"metadata":{"id":"Gl6k7MLLRbVR","colab_type":"text"},"cell_type":"markdown","source":["1. Recursive functions make the code look clean and elegant.\n","\n","2. A complex task can be broken down into simpler sub-problems using recursion.\n","\n","3. Sequence generation is easier with recursion than using some nested iteration.\n"]},{"metadata":{"id":"tZh9p_qrRbVS","colab_type":"text"},"cell_type":"markdown","source":["# Disadvantages"]},{"metadata":{"id":"lzJRnnfdRbVT","colab_type":"text"},"cell_type":"markdown","source":["1. Sometimes the logic behind recursion is hard to follow through.\n","\n","2. Recursive calls are expensive (inefficient) as they take up a lot of memory and time.\n","\n","3. Recursive functions are hard to debug.\n"]},{"metadata":{"id":"wSEYBp_BRbVU","colab_type":"text"},"cell_type":"markdown","source":["# Python program to display the fibonacci sequence up to n-th term using recursive function"]},{"metadata":{"id":"598cYHQ3RbVW","colab_type":"code","outputId":"ce16556a-3444-4c1f-8180-478d41583dac","colab":{}},"cell_type":"code","source":["def fibonacci(num):\n","    \"\"\"\n","    Recursive function to print fibonacci sequence\n","    \"\"\"\n","    return num if num <= 1 else fibonacci(num-1) + fibonacci(num-2)\n","\n","nterms = 10\n","print(\"Fibonacci sequence\")\n","for num in range(nterms):\n","    print(fibonacci(num))"],"execution_count":0,"outputs":[{"output_type":"stream","text":["Fibonacci sequence\n","0\n","1\n","1\n","2\n","3\n","5\n","8\n","13\n","21\n","34\n"],"name":"stdout"}]},{"metadata":{"id":"lzigbouGRbVa","colab_type":"code","colab":{}},"cell_type":"code","source":[""],"execution_count":0,"outputs":[]}]}