It is required to implement a recursive division of a segment in half. My version of the algorithm (pseudocode, for simplicity, comments in {} ):

 proc divide(B, E) {B - начало отрезка, E - конец отрезка} M = (B + E) div 2 {M - очередная искомая середина} ata(M) {процедура добавления в массив} if M = 1 then exit divide(B, M) {рекурсивный поиск следующей середины отрезка, начало-середина} divide(M, E) {рекурсивный поиск следующей середины отрезка, середина-конец}

The procedure is called in the program body as follows:

 divide(X1,X2)

The ata(M) procedure simply adds the M value to the array.

The procedure should divide the segment with the initial coordinates on the X axis equal to X1 and X2 in half, the halves still in half and so on, until the length is 1 . The problem must be solved precisely by recursion. Help to deal with the problem, because only the extreme halves are taken as it seemed to me. Is recursion implemented correctly?

  • "Please help me deal with the problem, because only the extreme halves are taken as it seemed to me" - maybe it seemed to you all the same, and the task displays the correct result? - Andrew Bystrov
  • What is your M? Cut length or middle? - Duck Learns to Take Cover
  • unfortunately not, recursion does not cover all segments - Denis Leonov
  • M - the middle of a segment - Denis Leonov
  • @Denis, aha, condition if M = 1 then exit then why? - Duck Learns to Take Cover

1 answer 1

There are several problems with this code.

  1. if M = 1 then exit - wrong, more logical if B + 1 == E or if B == E I personally prefer option 1 (see below).
  2. E should not be included in the segment. Those. if the segment [2,4] E must be equal to 5. Otherwise, on the segment [2,3] you divide into [2,2] and [2,3] and eternal recursion. Well or +1 add to 2 branches.
  3. (On the rights of a bore) He (B + E) div 2 and B + (E - B) div 2 - to avoid overflowing the number.
  • on the fourth point - if you are looking for the coordinates of all the centers, then with this recursive solution you need both halves, or you need to think out how to calculate the shifts for the second half - Sugar
  • yes, precisely all centers - Denis Leonov
  • @Denis, so any number is the center of itself ... If the centers of a segment of length 2, then any even / odd. The task is strange, therefore, and wrote. What can be the answer without starting to say it is suspicious. - pavel
  • @pavel we are talking about something like a Koch curve, where each segment is divided in half, then in half and so on with the required depth of a fractal tree - Denis Leonov
  • @pavel and how non-recursively to implement this? - Denis Leonov