Showing simulation of the recursion, given the recursion algorithm

user_14987401 0
Viewed 103

The following program in C takes n as an input and finds the sum of the series up to nth term using recursion. The series is given below: (1 x 3) + (2 x 5) + (4 x 7) + (8 x 9) + ... + nth term

Here is my code:

#include <stdio.h>
#include <math.h>
int addNumbers(int n);
int main(){
    int n;
    printf("Enter a positive integer n: ");
    scanf("%d", &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;
}

How can I show the simulation of the recursion for n=5 in my code?

recursion c
2 Answers

Easiest way to trace the recursion is to insert some printf statements.

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 = %d\n", term, sum);        // +++
        return sum;
    }
    else
    {
        printf("= %d\n", n);                     // +++
        return n;
    }
}

Output with n = 5:

= 0
+ 3 = 3
+ 10 = 13
+ 28 = 41
+ 72 = 113
+ 176 = 289

Sum = 289

You could also get rid of the pow call (which is dangerous, expensive and uses floating point unnecessarily) by using a variation of the recursion that calculates the powers as it goes.

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 = %d\n", term, sum);        // +++
        *p *= 2;
        return sum;
    }
    else
    {
        printf("= %d\n", n);                     // +++
        return n;
    }
}

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

Before returning the pow(2, n-1)*(2*n+1)+addNumbers(n-1) operation you can print to get the simulation. Since the recursion is used here top down process so your simulation also effect to top down method.

#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", &n);
    printf("Sum = %d", addNumbers(n));
    return 0;
}

Output

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

If you want to get the bottom to top approach simulation then follow this operation.

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", &n);
    tmp=n;
    printf("Sum = %d\n", addNumbers(n));
    return 0;
}

Output

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