<jupyter_start><jupyter_text>RecursionIn computer science Recursion is a technique for solving problems where the solution to a particular problem depends on the solution to a smaller instance of the same problem.- [GeeksforGeeks](https://www.geeksforgeeks.org/recursion/)Algorithmically- We can think that Recursion is a way to design solutions to problems by **divide and conquer** or **decrease and conquer**- Reduce a problem to simpler versions of the same problemSemantically- A programming technique where a **function calls itself**- Goal is to NOT have infinite recursion- Must have 1 or more base cases that are easy to solve  Recursion works really well with recursive structures like tress and graphs| Pros | Cons || ---- | ---- || Bridges the gap between elegance and complexity | Slowness due CPU overhead | | Reduces the need for complex loops and auxiliary data sctructures | Can lead to out of memory erros || Can reduce time complexity easily with memoization | Can be unnecessarily complex if poorly constructed |  Power of 2Consider the problem of calculating $\mathtt{2^5}$. Let's assume to calculate this, you need to do one multiplication after another. That's $2 * 2 * 2 * 2 * 2$. We know that $2^5 = 2 * 2^4$. If we know the value of $2^4$, we can easily calculate $2^5$.We can use recursion to solve this problem, since the solution to the original problem ($2^n$) depends on the solution to a smaller instance ($2^{n-1}$) of the same problem. The recursive solution is to calculate $2 * 2^{n-1}$ for all n that is greater than 0. If n is 0, return 1. We'll ignore all negative numbers.Let's look at what the recursive steps would be for calculating $2^5$.$2^5 = 2 * 2^4$$2^5 = 2 * 2 * 2^3$$2^5 = 2 * 2 * 2 * 2^2$$2^5 = 2 * 2 * 2 * 2 * 2^1$$2^5 = 2 * 2 * 2 * 2 * 2 * 2^0$<jupyter_code>def power2(n):
    if n <= 0:
        return 1
    else:
        return 2 * power2(n - 1)
power2(5)<jupyter_output><empty_output><jupyter_text>Sum of integersImplement `sum_integers(n)` to  calculate the sum of all integers from $1$ to $n$ using recursion.<jupyter_code>def sum_integers(n):
    if n <= 1:
        return 1
    else:
        output = n + sum_integers(n - 1)
        return output
sum_integers(10)<jupyter_output><empty_output><jupyter_text>Sum of elements of arrayImplement `sum_array(n)` to  calculate the sum of all elements in the array from $0$ to $n$ using recursion.<jupyter_code>def sum_array(array):
    
    if len(array) == 1:
        return array[0]
    
    return array[0] + sum_array(array[1:])

arr = [1, 2, 3, 4, 5, 6, 7, 8 , 9, 10]
sum_array(arr)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09961832061068703, 'fraction_numerical': 0.03587786259541985, 'mean_word_length': 3.9082397003745317, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 13, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '609577', 'license': 'MIT', 'n_tokens_mistral': 869, 'n_tokens_neox': 789, 'n_words': 358, 'path': 'src/recursion/intro_recursion.ipynb', 'repo_name': 'joaomh/Python-Data-Structures-and-Algorithms', 'size': '2620'}