C проблемы с рекурсией

Question

У меня есть запрос относительно рекурсивной функции. Это моя программа.

#include <stdio.h> 

int fun(int); 

int main(void) 
{ 
    int x; 
    int k=3; 
    x = fun(k); 
    printf("%d\n",x); 
    return 0; 
} 

int fun(int a) 
{ 
    int f; 
    if(a == 1) return (1); 
    f = 2 + fun(a-1); 
    return (f); 
} 

, где у меня есть значение K=3 в STEP-6. В STEP-7 функция fun(k) передает значение K вызываемой функции в STEP-11int fun(int a). В вызываемой функции fun(int a) рекурсия произошла 2 раза, т.е. (3,2), делая значение a=1. Позднее в STEP-14 значение f равно 3, так как f = 2 + (fun (1) = 1). В STEP-16 он возвращается к вызываемой функции i.e fun(int a)=3. Который должен напечатать значение x is 3, маловероятно, что это не так. Это x = 5

Answer 1

Давайте проверим вызывающую последовательность fun(), не так ли?

С значением аргумента 3, начиная с main()

• x = fun(3)
  • f = 2 + fun(2);
    • f = 2 + fun(1);

Теперь давайте проверим возвращаемые значения только в обратном порядке.

1. Последний звонок, fun(1) возвращается 1,
2. Так второй вызов, fun(2), возвращает 2 + 1 или 3,
3. Последний звонок, fun(3) возвращает 2 + 3 или 5

и что является звонок сделан от main(). Итак, в main(), x получает значение 5.

Answer 2

evalution из fun(3) выглядит следующим образом:

fun(3) 
2 + fun(3-1) 
2 + fun(2) 
2 + 2 + fun(2-1) 
2 + 2 + fun(1) 
2 + 2 + 1 
5 

Из вашего описания, я думаю у вас есть какие-то неправильные представления о областях в C (и рекурсии в целом). Тот факт, что f присваивается значение 3 внутри fun(2), делает не означает, что значение f изменяется в пределах fun(3) изменений - они являются полностью отдельными переменными.

Answer 3

Я вижу, что уже есть много хорошего ответа. Тем не менее я отправляю этот ответ, который может помочь вам в будущем, когда вы будете заниматься более сложной рекурсией.

Всякий раз, когда вы обнаружите что-либо о рекурсии, попробуйте сначала решить ее математически в своем ноутбуке. Хороший подход начинается с базового случая.

Функциональный базовый футляр fun(k): fun(1), который возвращает 1. Так что начните с нижеследующим:

fun(1) = 1 // let's read this, function fun(1) returns 1 

Теперь fun(2) что будет случится?

fun(2) = 2 + fun(1) 
     = 2 + 1 // we already calculated fun(1) =1 
     = 3 
fun(3) = 2 + fun(2) 
     = 2 + 3 // we already calculated fun(2) = 3 
     = 5 

Думаю, теперь это имеет смысл, почему x = 5!

Answer 4

Для рекурсивных функций, как правило, рекомендуется рисовать дерево рекурсии, чтобы лучше визуализировать происходящее.

• f (3) будет называть f (2), f (2) дополнительно называет f (1), который является базовым.

• F (1) вернет 1. Теперь F (2) вернет 2 + 1 = 3.

• F (3) теперь будет возвращать 2 + 3 = 5.

Проверьте дерево рекурсии ниже:

 |------> returns (2 + 3) = 5 
    | 
    f(3)<--- 
    |  | 
    |  | returns (2 + 1) = 3 
    f(2)<--- 
    |  | returns 1 
    |  | 
    f(1)---- 
    (This is the base case. No further recursion. It returns 1).