How to develop recursive thinking to a level at which one could easily solve problems like outputting only those elements of a binary tree that are visible from the top, and it is easy to write other recursive algorithms, for example, dynamic programming?

Googling is either just nonsense, or a primitive explanation about "Karach recursion, this kada function calls itself)))". Less common is information about how the stack is used when recursive procedures are used, but this knowledge does not increase the ability to write recursive algorithms.

Solutions of several tasks for recursion with a hackerran came to me intuitively, and I want to develop the ability to solve an arbitrary task for recursion consciously. How to achieve this?

Examples of the type:

def f(n): if(n == 0) return print n f(n - 1)

primitive, too easy, and their understanding does not develop the ability to solve a given task recursively.

  • programming contests read parses or decide on your own. You can codeforces.com here. - pavel
  • Well I wrote that I solve problems with a hacker, there are abstract problems for understanding algorithms, data structures and programming methods. Including recursion. How to skill something to pump, if I can solve only the most simple tasks? - typemoon
  • Only training, no tricks here. The more tasks you solve, the faster you will understand the solution of new ones. - iksuy
  • one
    @typemoon, you say that you move from programming to a mathematical description. Recursion is the same as the principle of mathematical induction. One to one. - Dmitriy Simushev
  • 2
    However, mathematical induction will not help me now to solve the top view problem. It seems everyone misunderstood the essence of the problem. I assume that the advisers create the illusion of understanding recursion, because they can write a sort of merge from memory. But on any unfamiliar task, they are likely to merge, because they can only write a solution to the problems known to them. I want to learn how to solve any problem recursively and to represent the process of performing a recursive function. - typemoon

3 answers 3

You can imagine that the recursive function has already been written. When solving a problem, use it as already written. After that, make sure that there are boundary conditions under which the recursion stops.

For example, suppose we have the following task: we need to find the number of possible ways of exchanging 100 rubles in coins of 10 rubles, 5 rubles, 2 rubles and 1 ruble.

That is, we need to write a function f (sum, coin_set), which we can call like this: result = f (100, [10, 5, 2, 1]). The first argument is the amount we need to exchange, and the second is a list of unique coins with which you can submit this amount.

Imagine that the function f has already been written. How can we use it now? Key point: think up a way to separate the possible options, preferably simple.

For example, note that 100 rubles can be exchanged either using a ten-ruble coin or without using a ten-ruble coin. This idea, one might say, is the solution to the problem.

The sum of these options will be equal to the desired number. Then the implementation of the function f can be written as the sum of recursive calls to itself with the "shortened" arguments: f (90, [1, 2, 5, 10]) + f (100, [1, 2, 5]).

f (90, [1, 2, 5, 10]) - we kind of "took" a ten-ruble coin out of 100, but do not limit the further selection of coins;

f (100, [1, 2, 5]) - we did not take anything from the sum, but limited the set of coins.

Both terms are called recursively. It is clear that the number of options will decrease with each recursive call.

It remains to add boundary conditions so that the function is not called infinitely. To do this, it is necessary to determine for which arguments to return 1, and for which to return 0.

    Practice. You can of course display Y-Combinator , but also solve daily tasks in your favorite language with higher-order functions ( Javascript, Python, etc. ) without using variables . This will reduce the mutagenicity and entropy of your programs, to the same. If possible, write to Scheme (practical applications: Guile, lambdanative ), but also without set! and of course on Haskell . Because what you have called “productive thinking” is essentially a practice of applying lambda calculus; then it is easiest to perceive it from the already existing infrastructure of a purely functional language.

    • which means: higher-order functions (Javascript, Python, etc.) without using variables. How to apply it in js for example? - spectre_it
    • one
      const instead of var ? The technician has a lot: map/reduce instead of for , pure functions, immutable finite automata (eg redux), unidirection data flow , flows, generators ... - 11111000000

    To solve problems (in any field) knowledge and practice are necessary.
    In this case, you need to master the course of the foundations of algorithms: read (or listen to) and solve more than one problem.

    As such a course you can recommend the book Sedgwick. Algorithms in C ++. Fundamental algorithms and data structures. (there are also versions of this book for C and Java). In it, in particular, there is a chapter devoted to recursion, and quite a lot of exercises.

    And after studying the basics, the ability to choose more optimal solutions comes with experience.

    • "In this case, it is required to master the course of the fundamentals of algorithms" I studied and implemented many algorithms, I can write several types of trees by memory, sorting, a system of disjoint subsets, sqrt-decomposition, etc., and I can’t decide top view. - typemoon pm
    • @typemoon - Don't worry. This is a poorly defined task. - Igor
    • No, the essence of the problem is clear, but how to apply recursion here is not clear. Some of my decisions do not deduce what is needed, or derive all elements of the tree. - typemoon
    • You need two different recursive functions. One - for the left side of the tree, the other - for the right. They will differ only in the place where the value of the vertex is displayed. In one case, the print will be after the recursive call, in the other - before. - zverkov
    • one
      @typemoon Then, if you think that you have enough knowledge, then I see only one way: to pause in the solution of the problem - not all problems can be solved immediately. - Konstantin Les