Top-Down Thinking to Solve Problems - Recursion

---

Recursion is a lot like a for loop (iterative method) in that both go through a loop to accomplish something.

butA recursive structure designed using Top-Down thinking will again have a few more different capabilities than for.More what capacity?

The Basics of Recursion

First, review recursion, definition of recursion: recursion (English: recursion), also translated as recursion, in mathematics and computer science, is the use of a function's own method in the definition of the function.

The essence of recursion is in:pass on，return In two processes. Beginners just contact will be a little abstract, the following through some cases to recognize.

Suppose you are required to implement a function to compute the factorial.
Definition of factorial:
The factorial of 5 is 5*4*3*2*1=120

def factorial(number):
    if number == 1:
        return 1
    else:
        return number * factorial(number - 1)

print(factorial(5))
// 120

Recursion requires three conditions to be considered:

1. Split the problem into a reused subproblem;
2. Note that this subproblem is independent of the size of the problem;
3. Must contain a termination condition (the termination condition is the initial state).

The underlying implementation of recursion (not the point)

The underlying implementation of recursion is not the focus of this article, just understand it.

The underlying implementation of recursion in a programming language usually relies on a call stack:

• callstack：

  • Each time a function is called, the program presses information about the function's arguments, local variables, and return address into the stack frame.
  • When the recursive function calls itself, a new stack frame is created and pressed onto the stack.
  • When the function has finished executing, the stack frame is popped and control is returned to the caller.

• Baseline conditions：

  • Recursion must have a termination condition, otherwise it will result in a stack overflow.
  • Each recursive call should move closer to the baseline condition.

• memory management：

  • The call stack is usually allocated in the "stack area" of memory. There is a limit to the size of the stack, and too many recursive calls can result in a stack overflow.
  • Some languages provide mechanisms to increase the size of the stack, but relying on deep recursion is generally not recommended.

Summary:

• The efficiency and safety of recursive implementations are closely related to specific language features and compiler optimizations.

• The bottom of the recursive implementation, that is, the relevant variable data (cache) processing, layer by layer into the stack, until after the benchmark conditions, in the layer by layer out of the processing.

Recursion in the eyes of a computer:
Computers use a stack to keep track of the function being called, called thecallstack。

There is a local variable, number, which records the current value.

Recursive application scenarios

• Scenarios that deal with arbitrarily many layers of things can be considered with recursion.

• When the problem and sub-problems have recursive relationships, e.g., Yang Hui triangles, computing factorials.

• Data structures with recursive properties, such as chained lists, trees, and graphs.

• Inversion problems, such as fetch-inverse operations.

Two types of problem-solving thinking in programming

That's what this article is focused on learning.

Consider using using top-down problem-solving thinking when faced with an unknown future.

Two ways to write a calculation function.

• Bottom - Up
  loop-like
• Top - Down
  recursive thinking

The difference between the two?
Bottom-up and top-down are two different ways of thinking and implementation strategies when computing functions:

When computing functions, especially recursive functions like factorials, there are two main implementations of recursive computation that can be used:bottom-up(bottom-up) andtop-down(top-down). Each of these approaches has its own advantages and disadvantages, and understanding them can help in choosing the right implementation to solve a particular problem. The following is an explanation of these two implementations:

Bottom-Up (Bottom-Up)

bottom-upmethod, also known asiterative method maybeDynamic programming methods, which means building the solution incrementally starting from the smallest subproblem until the original problem is solved. This approach is usually used in dynamic programming algorithms, but can also be used for some simple recursive problems.

Realization Ideas:

1. Defining the Minimum Problem:: Start with the smallest subproblem of the problem. For example, when calculating the factorial, one can start with the0! maybe1! Start.
2. construct sth. step by step: Calculate the solution to a larger problem step-by-step using iterations or loops.
3. Updates and storage: Store the solution to each subproblem for subsequent use.

Still going over the case of computing factorials, the bottom-up implementation approach:

def factorial_bottom_up(n):
    if n < 0:
        raise ValueError("Factorial is not defined for negative numbers")
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Sample usage
print(factorial_bottom_up(5))  # exports 120

Explanation:

• Compute the factorial from 2 to n iteratively starting from 1.
• Updating the result by incrementally multiplying each digit, we end up withn!。

Top-Down

top-downThe method is also known asrecursive method, is to start at the top of the problem and recursively solve smaller subproblems. This approach is very natural when dealing with recursive problems (but there may be sub-problems that are double-counted, some of which can be optimized).

Realization Ideas:

1. Define the main problem:: Address the problem from the top of the hierarchy.
2. recursive decomposition: Decompose the main problem recursively into smaller subproblems.
3. Basics: Define the base case of recursion to stop recursion.

Still using the case of computing factorials to demonstrate top-down implementation:

def factorial_top_down(n):
    if n < 0:
        raise ValueError("Factorial is not defined for negative numbers")
    if n == 0 or n == 1:
        return 1
    return n * factorial_top_down(n - 1)

# Sample usage
print(factorial_top_down(5))  # exports 120

Explanation:

• through (a gap)n Starting with a recursive call tofactorial_top_down(n - 1), until the base case is reached.
• Returns in the base case1, returning the product result layer by layer.

summarize

• bottom-up: Usually an iterative approach, building the solution step-by-step, suitable for dynamic planning and for situations where repeated computations need to be avoided. It is usually more efficient, especially when solving subproblems with repeated computations.

• top-down: Usually a recursive approach that solves problems intuitively, but may have high time complexity and space complexity, especially when dealing with large-scale problems. (Performance can be optimized by memoization)

Top-down thinking process - the case of summation

In general, the bottom-up implementation process is better understood, so here are some more top-down examples to help with the thinking.

Top-down programming thought process:

1. Think of the function you are writing as a function that someone else has implemented.
2. Identify sub-problems.
3. See what happens when you call the function on a sub-problem and continue from there.

The case for peacemaking
Suppose we want to write a sum function that calculates the sum of all the numbers in an array. If the function is passed the array [1, 2, 3, 4, 5], then it will return the sum of these numbers 15.

The first thing we need to do isvisualizeSomeone has already implemented the sum function. (Of course, you might find this a little hard to accept; after all, it's up to us to write the function, so how can we assume that someone else has done it? But try to forget about that and pretend for a moment that the sum function has already been implemented.)

Next, to identify the sub-problems.The process is more of an art than a science, and you can improve if you practice more. In this example, the subproblem can be thought of as the array [2, 3, 4, 5], i.e., the elements of the original array other than the first number.

Finally, what happens when you call the sum function on a subproblem ?
If the sum function is "correctly implemented" and the subproblem is [2, 3, 4, 5], what happens when sum([2, 3, 4, 5]) is called? You get the sum of 2+3+4+5, which is 14.

And to ask for the sum of [1, 2, 3, 4, 5], simply add 1 to the result of sum([2, 3, 4, 5]).

Please implement it using a programming language:

mylist = [1, 2, 3, 4, 5]
def mysum(alist):

    if len(alist) == 1:
        return alist[0]
    else:
		# alist[-1] = alist[len(alist)-1]
        alist[0] += alist[-1]

    return mysum(alist[0:len(alist) - 1])

print(mysum(mylist))
# 15

Step Problems Cases

Why do I need to use recursion?

Please write the code:

todo

Transpositional word formation Cases

This is a very useful case, I've encountered this dilemma before when I wanted to combine multiple pyloads in different positions to form a whole.

Please write the code:

todo