Быстрое определение конечного значения, возвращаемого рекурсивной функцией.

Один из вопросов, заданных на экзамене, который я просидел вчера, заставил меня очаровываться.Быстрое определение конечного значения, возвращаемого рекурсивной функцией.

int G(int n) 
{ 
    if(n > 100) 
    { 
    return (n - 10); 
    } 
    else 
    { 
    return (G(G(n + 11)); 
    } 
}

Нам было предложено выбрать правильный результат G (10) из четырех вариантов. Я вернулся домой, написал программу на своем ПК, и она выплюнула 91 как ответ. Действительно, 91 был указан как один из ответов.

Определенный для достижения одного и того же ответа, я вручную написал программу сборки, эквивалентную тому, чтобы получить ответ [Думая, что было бы не более 10-12 фреймов стека, созданных до того, как они все развяжутся).

G: 
CMP R0,#100 [Register R0 has the argument. Also the return value.] 
BLT Label  [Branch if less than] 
SUB R0,#10 
RET 

Label: 
ST R14, [SP] [Store the return address of the caller on stack] 
SUB SP,#4  [Update the stack pointer] 
ADD R0,#11 
BL G   [G(n+11)] Uses value in R0 as argument, Returns value in R0 
BL G   [G(G(n+11))] same comments as above 
ADD SP,#4 
LD R14,[SP] 
RET

Я тогда вручную восстановил фрейм стека для каждого вызова, а рамки только увеличивались. Около 20 кадров стека я сдался.

Подозрившись на мою программу сборки, я пошел вперед и вставил счетчик в программу C, и он указал, что функция была введена 183 раза.

Очевидно, что это был вопрос, который должен был быть разрешен за 5 минут, поэтому должно быть более простое решение, например, правило большого пальца или граф или что-то еще.

Как бы вы получили ответ менее чем за 5 минут?

источник

2015-11-19 Raj

Причина есть не только 10-12 кадры стека в том, что это не является стандартным рекурсивное определение функции, когда он называет себя _once_. Из-за того, что обратная линия является 'return (G (G (n + 11)); каждый вызов на самом деле порождает _2_ последующие вызовы. –

Что такое G (n), если n> 100?

Что такое G (n), если n = 100?

Что такое G (n), если n = 99? (Используйте ответ выше).

Что такое G (n), если n = 98? (Используйте ответ выше).

...

Что такое G (п) при п = 90? (Используйте ответ выше).

Что такое G (n), если n = 89? (Используйте ответы для n = 100 и n = 91).

И так далее. Будет очень, очень очевидная картина.

источник

2015-11-19 12:30:53 gnasher729

Вы сделали это настолько ужасно простым gnasher729. Таким образом, трюк состоял в том, чтобы построить таблицу поиска для n = От 100 до 111. И просто повторите использование этих значений для n = 100 и ниже. Теперь я чувствую себя очень глупым. Большое спасибо. :-) – Raj

Это имеет смысл, поскольку единственный способ для (G (G (n + 11)), чтобы вернуть значение, это если '(G (n + 11))> 100 И n <= 100', но нам нужно (G (n + 11)) вернуть значение, означающее, что' (n + 11-10)> 100', поэтому условие становится 'n + 1> 100 AND n <= 100', где n является целым числом, единственным решением является n = 100, это означает, что единственно возможным возвращаемым значением ветви else является G (G (111)) = 91. –

Обратите внимание, что оптимизирующий компилятор будет переставить код немного и генерировать хвост рекурсивный цикл:

G  proc 
     mov  eax, DWORD PTR [esp+4] ;n 
     add  eax, 11 
     cmp  eax, 100 
     jle  SHORT G0 
     add  eax, -10 
     jmp  SHORT G1 

G0:  push eax 
     call G 
     add  esp, 4 
G1:  cmp  eax, 100 
     jle  SHORT G2 
     add  eax, -10 
     ret  0 

G2:  mov  DWORD PTR [esp+4], eax ;n 
     jmp  G      ;tail recursion 
G  endp

источник

2015-11-19 12:52:56 rcgldr

Быстрое определение конечного значения, возвращаемого рекурсивной функцией.

ответ

Смежные вопросы