рекурсивное вычисление числа
Код:
function a(n:integer):integer;
begin
if n:=1 then a:=1 else
a:=a(n div 2)+1;
end;
begin
readln(n);
writeln(rec(n));
readln;
end.
begin
if n:=1 then a:=1 else
a:=a(n div 2)+1;
end;
begin
readln(n);
writeln(rec(n));
readln;
end.
степень числа 2 в которую нужно его возвести
чтобы было выполнено неравенство
2^a-1<=n<2^a
вопрос следующий:не могу понять как вычисляется
эта степень какой результат конкретно записывается
в стек при каждом цикле рекурсии
например если вводим цифру 6 программа
выдает результат 3 ,это верный рез.т.к.
2^3-1<=6<2^3 но как он вычисляется
для меня загадка
Стек устроен сложнее (там несколько стеков). В стек вызовов кладется информация о том, что эта функция должна быть вызвана с параметрами хранящимися на следующей ячейке стека результатов. А на стек результатов значение помещается только тогда, когда функция может быть вычислена. С этого момента (когда n=1) можно последовательно вычислить значения на верхних уровнях рекурсии. И в условии if n:=1, имхо, должна быть проверка на равенство, а не присваивание.
Цитата: Meander
Стек устроен сложнее (там несколько стеков). В стек вызовов кладется информация о том, что эта функция должна быть вызвана с параметрами хранящимися на следующей ячейке стека результатов. А на стек результатов значение помещается только тогда, когда функция может быть вычислена. С этого момента (когда n=1) можно последовательно вычислить значения на верхних уровнях рекурсии. И в условии if n:=1, имхо, должна быть проверка на равенство, а не присваивание.
я уточню вопрос:мне важно наглядно понять,как происходит вычисление результата,
если у Вас есть немного времени поясните пожалуйста,
if n=1 да здесь я был невнимателен
у меня просьба к тем ,кто решит мне ответить
на заданный вопрос а именно:"как происходит
вычисление результата в приведенной программе"
не нужно меня отфутболивать в википедию и иже
с ними просто напишите -результат возникает так-то
и так-то то есть на конкретно и наглядно написанном
примере
например так :берем цифру 6 ,при 1 цикле рекурсии
в стеке цифра 3 при втором цифра 1 по условию дошли до
конца .ответ программы =3 откуда он взялся ?если к какому-то
результату (не знаю откуда он)нужно прибавить еще +1(a(n div 2)+1;
c цифрой 4 тот же ответ программы =3 при этом при работе рекурсии
получается при 1-м цикле 2 при последнем =1 ...откуда берется результат =3???
на заданный вопрос а именно:"как происходит
вычисление результата в приведенной программе"
не нужно меня отфутболивать в википедию и иже
с ними просто напишите -результат возникает так-то
и так-то то есть на конкретно и наглядно написанном
примере
например так :берем цифру 6 ,при 1 цикле рекурсии
в стеке цифра 3 при втором цифра 1 по условию дошли до
конца .ответ программы =3 откуда он взялся ?если к какому-то
результату (не знаю откуда он)нужно прибавить еще +1(a(n div 2)+1;
c цифрой 4 тот же ответ программы =3 при этом при работе рекурсии
получается при 1-м цикле 2 при последнем =1 ...откуда берется результат =3???
Так примерно:
Вызовов a(6): 6 равно 1 -> нет -> в стек пишем команды: вызвать a(6 div 2) к результату прибавить 1 и вернуться к a(6);
Вызовов a(3): 3 равно 1 -> нет -> в стек пишем команды: вызвать a(3 div 2) к результату прибавить 1 и вернуться к a(3);
Вызовов a(1): 1 равно 1 -> да -> в стек пишем a(1):=1, и передаем управление на a(3);
Внутри a(3): a(3):=a(1)+1 или в стек пишем a(3):=2, и передаем управление на a(6);
Внутри a(6): a(6):=a(3)+1 или в стек пишем a(6):=3, и передаем управление внешним функциям;
Вызовов a(6): 6 равно 1 -> нет -> в стек пишем команды: вызвать a(6 div 2) к результату прибавить 1 и вернуться к a(6);
Вызовов a(3): 3 равно 1 -> нет -> в стек пишем команды: вызвать a(3 div 2) к результату прибавить 1 и вернуться к a(3);
Вызовов a(1): 1 равно 1 -> да -> в стек пишем a(1):=1, и передаем управление на a(3);
Внутри a(3): a(3):=a(1)+1 или в стек пишем a(3):=2, и передаем управление на a(6);
Внутри a(6): a(6):=a(3)+1 или в стек пишем a(6):=3, и передаем управление внешним функциям;
спасибо преогромное за подробное объяснение