Отображение моделирования рекурсии с учетом алгоритма рекурсии

#c #recursion

#c #рекурсия

Вопрос:

Следующая программа на C принимает n в качестве входных данных и находит сумму ряда до n-го члена, используя рекурсию. Ниже приведен ряд: (1 x 3) (2 x 5) (4 x 7) (8 x 9) … n-й член

Вот мой код:

 #include <stdio.h>
#include <math.h>
int addNumbers(int n);
int main(){
    int n;
    printf("Enter a positive integer n: ");
    scanf("%d", amp;n);
    printf("Sum = %d", addNumbers(n));
    return 0;
}

int addNumbers(int n){
    if (n>0)
        return pow (2, n-1)*(2*n 1) addNumbers(n-1);
    else
        return n;
}

Как я могу показать моделирование рекурсии для n = 5 в моем коде?

1. Показать это каким образом? Может быть, просто добавить printf() вызовы функции?

2. Вам нужно переписать функцию, чтобы она была более подробной, например a=pow(); b=2*n 1; c=addNumbers(); result=a*b c; , тогда вы можете печатать все, что хотите, прежде чем возвращать результат.

Ответ №1:

Перед возвратом pow(2, n-1)*(2*n 1) addNumbers(n-1) операции вы можете распечатать, чтобы получить симуляцию. Поскольку здесь используется процесс рекурсии сверху вниз, поэтому ваше моделирование также влияет на метод сверху вниз.

 #include <stdio.h>
#include <math.h>
int addNumbers(int n)
{
    if (n>0){
        int a=pow(2,n-1);
        int b=2*n 1;
        if(n>1)
            printf("(%d x %d)   ",a,b);
        else
            printf("(%d x %d)n",a,b);
        return pow(2, n-1)*(2*n 1) addNumbers(n-1);

    }
    else
        return n;
}
int main()
{
    int n;
    printf("Enter a positive integer n: ");
    scanf("%d", amp;n);
    printf("Sum = %d", addNumbers(n));
    return 0;
}

Выходной сигнал

 Enter a positive integer n: 5
(16 x 11)   (8 x 9)   (4 x 7)   (2 x 5)   (1 x 3)
Sum = 289

Если вы хотите получить моделирование подхода снизу вверх, выполните эту операцию.

 int sum=0,tmp;
int addNumbers(int n)
{
    if (n>0){
        sum =pow(2, n-1)*(2*n 1) addNumbers(n-1);
        int a=pow(2,n-1);
        int b=2*n 1;
        if(tmp==n)
            printf("(%d x %d)n",a,b);
        else
            printf("(%d x %d)  ",a,b);
    }
    return sum;
}
int main()
{
    int n;
    printf("Enter a positive integer n: ");
    scanf("%d", amp;n);
    tmp=n;
    printf("Sum = %dn", addNumbers(n));
    return 0;
}

Вывод

 Enter a positive integer n: 5
(1 x 3)  (2 x 5)  (4 x 7)  (8 x 9)  (16 x 11)
Sum = 289

1. Ваше моделирование подхода снизу вверх не выдает 289 в качестве выходных данных, когда я ввожу n = 5

2. Оба кода дают мне тот же результат 289. Не могли бы вы проверить еще раз? В то время как логика кода также одинакова

Ответ №2:

Самый простой способ отследить рекурсию — вставить несколько printf операторов.

 int addNumbers(int n){
    if (n > 0)
    {
        int term = pow(2, n - 1) * (2 * n   1);  // = (1 << (n - 1)) * (2 * n   1) 
        int sum = term   addNumbers(n - 1);
        printf("  %d = %dn", term, sum);        //    
        return sum;
    }
    else
    {
        printf("= %dn", n);                     //    
        return n;
    }
}

Вывод с n = 5 :

Вы также можете избавиться от pow вызова (который является опасным, дорогостоящим и использует плавающую точку без необходимости), используя вариант рекурсии, который вычисляет степени по ходу выполнения.

 int addMulNumbers(int n, int *p){
    if (n > 0)
    {
        int mul = addMulNumbers(n - 1, p);
        int term = *p * (2 * n   1); 
        int sum = term   mul;
        printf("  %d = %dn", term, sum);        //    
        *p *= 2;
        return sum;
    }
    else
    {
        printf("= %dn", n);                     //    
        return n;
    }
}

int addNumbers(int n){
    int p = 1;
    return addMulNumbers(n, amp;p); 
}