Какой будет выход моей рекурсивной функции в C

Question

Рассмотрим следующую рекурсивную функцию C, которая принимает два аргумента.

unsigned int foo(unsigned int n, unsigned int r) 
{ 
    if (n > 0) 
     return (n % r) + foo(n/r, r); 
    else 
     return 0; 
} 

Что такое значение функции Foo, когда она называется Foo (512,2)?

Answer 1

Этот код, фактически является рекурсией.

следовать возвращение произошло:

If n == 0; return 0; 

If n == 1; return 1+foo(0,2) 

If n == 2; return 0 + foo(1,2); 

If n == 4; return 0 + foo(2,2); 

    ... 

if n == 2^n return 0 + foo(0+foo(z^n-1,2)); 


.... 


So foo(512,2) == foo (2^n,2) == 0+f(1,2) == 1 +f(0,2) = 1; 

Он вернется 1.

Answer 2

Ваш результат будет 1. Вот что происходит:

1. Первый вызов: п = 512, r = 2, n% r = 0; звонки foo (256, 2)
2. Второй вызов: n = 256, r = 2, n% r = 0; звонки foo (128, 2)
3. Третий вызов: n = 128, r = 2, n% r = 0; звонки foo (64, 2)
4. Четвертый вызов: n = 64, r = 2, n% r = 0; звонки foo (32, 2)
5. Пятый вызов: n = 32, r = 2, n% r = 0; звонки foo (16, 2)
6. Шестой вызов: n = 16, r = 2, n% r = 0; звонки foo (8, 2)
7. Седьмой вызов: n = 8, r = 2, n% r = 0; звонки foo (4, 2)
8. Восьмой вызов: n = 4, r = 2, n% r = 0; звонки foo (2, 2)
9. Девятый вызов: n = 2, r = 2, n% r = 0; звонки foo (1, 2)
10. Десятый звонок: n = 1, r = 2, n% r = 1; звонки foo (0, 2)
11. Одиннадцатый звонок: n = 0, r = 2; возвращает 0
12. Десятый вызов возвращает 1 + 0 = 1
13. Девятый вызов и последующие вызовы возвращают 0 + 1 = 1

разматывать завершена и функция возвращает 1.