Recursion C ++

рекурсия с++, Fibonacci c ++

In C ++ any function except main() can call itself. That is, in the body of the call can be placed the same function. This is called recursion.

When the program executes the code of a recursive function – she will perform it indefinitely, if you do not provide a condition to exit the recursion. This should be remembered, to avoid looping calls. Therefore, in the definition of recursive function must specify the exit condition. For example, You can place it inside the block call if.

In this program function recursionGoDown() will call itself, until it is transferred to a number greater than zero. Every time, function gets the number of, from which is subtracted in the signature unit. As soon as the condition becomes false (the number will be less than zero) – calls to stop and start the output of the recursion.

If we pass in a function number 9, calls will 10. The program as it deepens on 10 levels, performing recursion. To her out of the recursion, We must pass these ten levels back. So the string of code

will run too 10 times, but the value someNumber will change in the opposite order. First, it will conform to, that was passed to the function in the 10 level of recursion, then passed on to the fact that 9 level, etc..

рекурсия с++, Fibonacci c ++

I want to draw attention to an important point. Each recursive call creates a new variable someNumber with the new value. These variables will occupy some space in RAM. If the call 10, as in our example, and it will be stored in the memory 10 with different values ​​of the variables. It is possible to add to the program output to the screen addresses, which stores these values ​​and see this:

Passing in a function number 2: recursionGoDown(2); Levels of recursion is 3.

рекурсия с++, Fibonacci c ++

As seen, each value of a variable someNumber stored in a separate memory segment. During the return to recursion values come from the same addresses but in reverse order.

Almost every task, which can be solved using recursion, can be implemented using iteration loops. You can in fact easy to show on the screen the number of 9 to 0 and by 0 to 9 applying loops. In addition, you should know, that recursion takes more memory and calculation will produce slower, than the iteration.

But, as claimed by experienced programmers and many authors of books, this does not mean, recursion is useless. There are tasks, decide which, using iteration loops, difficult and cumbersome. A recursive solution looks better. For entry-level, until you learn only basics of programming in C ++, you just need to understand, what a recursion is and how it works.

See more videos on the topic of Recursion with 6′ (Author video: Denis Markov).

Newsletter of programming:

Recursion C ++
4.5 (90%) 4 votes

5 thoughts on “Recursion C ++

  1. You're too hard on recursion ;-)

    1. Recursion – a general mathematical formalism, which theoretically express all computable algorithms (I took it from the mat. theory of algorithms).
    2. All tasks of dynamic data structures (lists, queue, trees, counts, …) solved recursively easier, and most importantly clearer, than iteratively (cyclic iterative algorithms work better on arrays – static structures).
    3. There are algorithms, expressed in 2-3 line recursively, but that is very difficult to write without recursion. A beautiful example of this: famous challenge “tower of Hanoi”. Many sorting algorithms (the same array) better expressed in a recursive form.

    Recursion just seems complicated, because it is not taught in the domestic practice and do not know how to use it. And at universities in France, for example, training 1st semester starts with learning recursive algorithms.

    1. Always good, when someone expresses his point of view and my personal opinion, based on experience. Beginners will be useful to read.

      1. Recursion – this is most natural way to handle any dynamic structures (lists, trees, etc.), This exhibit functional programming languages, such as Lisp. This approach is much more effective, than iterative (cycles). But it should be shown on code examples…
        A simple and beautiful example of recursion look at the problem of a number raised to a power:

  2. Hello.
    Объясните пожалуйста следующие моменты, всю голову сломал, can not understand:
    1. Если в массив в процессе деления на подмассивы не длиться ровно на 2, то программа прекратит работу? Ведь в int middle= arr[(l+r)]/2 , где (l+r)/2- integer.

    2. Если в массиве есть повторяющиеся числа, и у опорного элемента будет такое же число, как у числа слева или справа, for example 1,2,3, 5, 6,5,7
    then, не получится что после того, как программа определила центральный элемент =5, и начала его сравнение с элементами правого подмассива , она дойдя до одинакового элемента arr [5]=5 подумает что достигла центрального элемента , перестанет сравнивать более ранние элементы (arr [4}, arr [3]) с центральным, примет этот 5 элемент за центральный, и далее будет считать его крайней левой границей?

    3. В примере рассматривалась попарная смена (слева и справа от центрального) elements, не удовлеторяющих условию:

    while (middle>arr [i]) i ;
    while (middle<arr [j]) j–;

    if (i<=j)
    swap (arr [i], arr [j]);
    i ;


    А что если либо изначально, либо после процесса сортировки остался 1
    подлежащий замене элемент, for example:
    1, 2, 3, 8, 5, 6, 7, 9,10
    то если я правильно понял, он поменяется с центральным элементом,
    i.e.. получится 1,2,3,5, 8, 6,7,9,10 ?


    Значение центрального элемента может поменяется. В то же время после такого изменения центрального элемента, comparison, произведенные с более ранним центральным элементом окажутся неверными, т.к они не пересматриваются, и продолжают идти дальше. В результате сортировка окажется неверной.

    For example:
    исходный массив: 1,2,6,9, 4, 10,11,3, 12 с центральным элементом 4.
    После первой замены (6 on 3) получается: 1,2,3,9, 4, 10,11,6,12.
    После второй замены (9 on 4) получается: 1,2,3,4, 9, 10,11,6,12 и сортировка этого множества заканчиватся. Однако элемент правого подмножества 6 отсортирован неправильно.

Leave a Reply

Your email address will not be published. Required fields are marked *