<jupyter_start><jupyter_text>Abstract Data Structures: Thinking recursively 5.1.1 Identify a situation that requires the use of recursive thinkingWhat is this recursive thing? It's a very practical way of establishing an abstract pattern in our thinking. There are a class of problems that require thinking in a more abstract manner, and trying to identify this pattern of thinking is the subject of this section.First, let's talk about **non-recursive** or **iterative** way of thinking. That's like a procedure, such as brushing your teeth, or the sequence of events on any given day in history.We'll start with this previous function that we wrote that continuously asks the user for valid input<jupyter_code>// We'll generate 5 integers, finally returning "Y" on the fifth attempt
QUEUE = Queue.from_x_characters(4, min="A", max="X")
QUEUE.enqueue("Y")

sub input(PROMPT)
    out PROMPT

    // pop off the stack and if it's a 10, we finally got a yes
    VALUE = QUEUE.dequeue()
    if VALUE = 1 then
        return "Y"
    else
        return VALUE
    end if
end sub

sub ask_until_valid_nonrecursive(PROMPT, POSSIBLES)
    // loop infinitely until "break"
    loop while true
        RESPONSE = input(PROMPT)
        if RESPONSE in POSSIBLES then
            // valid response
            break  // loop stops
        else
            // invalid response
            output RESPONSE, " is not valid!"
        end if
    output RESPONSE, " Aahhhhh"
    return RESPONSE
end sub

ask_until_valid_nonrecursive("Yes?: ", ["Y"])<jupyter_output><empty_output><jupyter_text>This function works just fine. However, there is a way to write this function in a recursive manner. It's a simple example that does not have much use, but we just need to understand what is meant when we say to solve something with recursion. It's basically a function calling itself. Consider this code:<jupyter_code>def ask_until_valid_recursive(prompt: str, possible_answers: list):
    response = input(prompt)
    if response in possible_answers:
        # valid
        return response
    # invalid: recurse!
    ask_until_valid_recursive(prompt, possible_answers)
    
ask_until_valid_recursive("Get it?", ['Y', 'N'])<jupyter_output><empty_output><jupyter_text>Basically this function "falls back" on itself. Instead of going in a loop, the code continues the same way a loop does, by further calling itself, and repeating this process until something valid is found.Right, so let's discover a limit to this recursion thing by seeing what happens when nothing valid is every found.<jupyter_code>ask_until_valid_recursive('Nothing you type will be valid: ', [])  # infinite loop<jupyter_output><empty_output><jupyter_text>In the above call, we have not defined anything as being valid, and so this program will go on forever constantly prompting you to type something. Actually … not quite forever. Although it is technically an infinite loop, the fact of the matter is that there are resource limitations, and it will eventually fail. Let's see it fail by typing a recursive function that never ends:<jupyter_code>def recurse_forever(prompt):
    recurse_forever(prompt)

recurse_forever("Error")<jupyter_output><empty_output><jupyter_text>Run the above, and it displays `RecursionError: maximum recursion depth exceeded`. This means that the code we ran failed, and in this case it's because of something called a "stack overflow" which is to say that Python doesn't have enough memory to continue keep doing the same thing over and over again, and so fails.But this `ask_until_valid` example is not really an example that requires recursive thinking, because the version that we had worked just fine with an interative approach (and maybe was easier to understand). So what kind of problem does require recursion? It's in a case in which the problem breaks down into an algorthim that depends on previous steps being completed, and depending on **base cases** where the recursion will inevidibly end up.For that, we'll take another loop at making the fibinocci sequence. We need to understand what this sequence of numbers is, which is provided in this formula:      ↓ pattern            ↓ base cases$F_n = F_{n-1} + F_{n-2}$, where $F_1 = 1$, and $F_0 = 0$.That is to say that a number `n` is defined as the "F of (n-1) plus F of (n-2)", but "F of 1 is 1" and F of 0 is 0"The solution to calculate this in a procedural way is this:<jupyter_code>def fibonnoci_iterative(how_many):
    """ return the how_many-th number of fibonocci numbers """
    
    # base cases:
    result = [0, 1]
    
    for n in range(2, how_many):  # we already have the first two
        
        # pattern:
        new = result[n-2] + result[n-1]
        result.append(new)
        
    return result

for result in fibonnoci_iterative(10):
    print(result, end=" ")
def fibonnoci_recurse(n):
    """ return the fibonocci numbers at index n """    
    
    # base cases:
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    # pattern
    return fibonnoci_recurse(n - 1) + fibonnoci_recurse(n - 2)

def fibonnoci_recurse_n_terms(how_many):
    result = []
    for i in range(how_many):
        value = fibonnoci_recurse(i)
        result.append(value)
    return result

for item in fibonnoci_recurse_n_terms(10):
    print(item, end=" ")<jupyter_output><empty_output><jupyter_text>Okay, so we have some of the theory down. We can see that recusion can be used to solve problems when the problem can be described in terms of itself. We have also seen the case where base cases are required to ensure that we don't have an infinite loop.  5.1.2 Identify recursive thinking in a specified problem solutionBut let's get more specific in understanding the kinds of problems that recursion is great at solving. Above, there were two solutions presented, one that was iterative and the other that was recursive. One could argue that the iterative solution is simpler and more understandable. There is no doubt, however, that the recursive solution is far slower.<jupyter_code>%%timeit
list(fibonnoci_iterative(10))
%%timeit
list(fibonnoci_recurse_n_terms(10))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.06628849270664505, 'fraction_numerical': 0.006807131280388979, 'mean_word_length': 3.8590551181102364, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '4530', 'license': 'MIT', 'n_tokens_mistral': 1797, 'n_tokens_neox': 1704, 'n_words': 802, 'path': 'Topic 5 Abstract data structures/Untitled3.ipynb', 'repo_name': 'classroomtechtools/ib_dp_course', 'size': '6170'}