{ "cells": [ { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "# Recursion\n", "\n", "\n", "```{figure} ../assets/recursion0.jpeg\n", "---\n", "scale: 10%\n", "align: right\n", "---\n", "A visual form of recursion
known as the Droste effect.
Note the image within the image. \n", "```\n", "\n", "In order to understand recursion, one must first understand recursion.\n", "\n", "**Recursion** occurs when the definition of a concept or process depends on (a simpler or previous version of) itself. \n", "\n", "\n", "In the context of modern computer programming, recursion refers to **functions calling themselves**.\n", "\n", "These _\"recursive calls\"_ are often made with **smaller input data**.\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "
\n", "\n", "As you may have gathered from previous sections, a big theme in programming, and problem solving in general, is the idea of **breaking down a problem into smaller, more manageable subproblems**. \n", "\n", "In case of decrease and conquer, we break down the problem into smaller subproblems in a manner that the subproblems are smaller than the original problem by a constant amount i.e. $n_{new} = n_{original} - k$, where k is a constant. In case of divide and conquer, we break down the problem into smaller subproblems in a manner that the subproblems are smaller than the original problem by a constant factor i.e. $n_{~new} = n_{~original} / k$, where k is a constant.\n", "\n", "```{figure} https://i.ibb.co/HrdMFr7/decrease-conquer.png\n", "---\n", "scale: 50%\n", "align: center\n", "---\n", "Decrease and conquer: Problem is broken down in a manner that the subproblems are smaller than the original problem by a constant amount i.e. $n_{~new} = n_{~original} - k$, where k is a constant.\n", "```\n", "\n", "\n", "```{figure} https://i.ibb.co/8Nj32P2/divide-conquer.png\n", "---\n", "scale: 50%\n", "align: center\n", "---\n", "Divide and conquer: Problem is broken down in a manner that the subproblems are smaller than the original problem by a constant factor i.e. $n_{~new} = n_{~original} / k$, where k is a constant.\n", "```\n", "\n", "This process is **repeated until the problem cannot be broken down any further**, at which point the solutions to the subproblems are combined to solve the original problem.\n", "\n", "In the context of lists, we reach this stage when the list is empty or has only one element.\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## ATM Example\n", "\n", "Let's understand recursion with the help of an analogy.\n", "\n", "Imagine you need some cash. You go to the ATM and see a long queue. The queue is so long that you can't see the end of it. \n", "\n", "

\n", "\n", "\n", "\n", "

\n", "\n", "You decide to find out how many people are there in the queue in a recursive manner. So you ask the person in front of you what number are they. The person in front of you asks the person in front of them and so on. In recursion, this is known as the **recursive step**.\n", "\n", "
\n", "\n", "\n", "

\n", "\n", "This process continues until the person at the end of the queue is asked. This is known as the **base case** in recursion. The base case is the condition that stops the recursion. In this case, the base case is when the person at the end of the queue is asked.\n", "\n", "

\n", "\n", "

\n", "\n", "The person at the end of the queue is asked and they reply that they are the first person in the queue.\n", "\n", "

\n", "\n", "

\n", "\n", "The person in front of them adds 1 to the number and tells the person in front of them. This process continues until the person in front of you tells you the number." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def count(queue):\n", " \n", " # BASE CASE: if there is only one person in the queue\n", " if queue == [\"person\"]: \n", " return 1\n", " else:\n", " \n", " # remove the first element\n", " subset = queue[1:]\n", " \n", " # RECURSIVE STEP: count the number of people ahead\n", " count_ahead = count(subset)\n", "\n", " # return 1 plus the number of people ahead\n", " return 1 + count_ahead\n", " \n", "data = [\"person\", \"person\", \"person\", \"person\", \"person\"]\n", "count(data)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## Key Terms \n", "\n", "\n", "\n", "In summary, recursion involves two key components:\n", "\n", "1. **Recursive Step**: The step where the function calls itself, breaking down the input data into smaller subset(s). \n", "\n", " The number of times the function calls itself is known as the **depth of recursion**.\n", "\n", "2. **Base Case**: The case where the input data cannot be broken down any further. This is the condition that stops the recursion. \n", "\n", " Without a base case, the function would continue to call itself indefinitely, leading to an infinite loop. This is known as **infinite recursion**. \n", "\n", "3. **Descending down, towards base case**: The process of breaking down the input data into smaller subset(s) is sometimes referred to as descending down recursion chain/tree. Other terms used are unfolding or decomposing the problem.\n", "\n", "4. **Ascending up, away from base case**: The process of combining the solutions of the subproblems to solve the original problem is sometimes referred to as ascending up recursion. Other terms used are combining or unwinding the problem.\n", "\n", "## Pros and Cons of Recursion\n", "\n", "Recursion is a powerful tool, but it's not always the best tool for the job. Here are some pros and cons of using recursion.\n", "\n", "✅ **Readable and Elegant**: Recursive solutions are often more readable and elegant than their iterative counterparts.\n", "\n", "✅ **Mathematical**: Many mathematical ideas are naturally recursive, so recursion can be a more organic way to express these ideas in code. For example, the Fibonacci sequence is defined recursively i.e. $F(n) = F(n-1) + F(n-2)$. Similarly, the factorial of a number is defined recursively i.e. $n! = n \\times (n-1)!$.\n", "\n", "✅ **Divide and Conquer and Tree Structures**: Recursive solutions are often well-suited for problems involving trees and graphs, which are ubiqutous in nature, sciences and particularly in computational problems. Since divide and conquer strategies yield a tree like structure, recursion is a natural fit for such problems.\n", "\n", "❌ **Performance**: Recursive solutions are often less efficient than iterative solutions due to the overhead of function calls and the potential for repeated work.\n", "\n", "❌ **Debugging**: Recursive solutions are often harder to debug than iterative solutions. This is because the state of the program is spread across many function calls, making it harder to reason about the program's behavior.\n", "\n", "❌ **Memory**: Recursive solutions often require more memory than iterative solutions. This is because each function call requires memory to store the function's state, and the depth of recursion can be quite large.\n", "\n", "❌ **Convoluted**: Recursive solutions can be harder to understand than iterative solutions, especially for people who are new to programming.\n", "\n", "
\n", "
\n", "
" ] } ], "metadata": { "language_info": { "name": "python" }, "orig_nbformat": 4 }, "nbformat": 4, "nbformat_minor": 2 }