CODEWITHSUNDEEP
javadiscrete-mathematics
Dino Panagos
Dino Panagos

Reputation: 11

how can i write a recursive function of my pseudocode?

Actual code is easier but I'm having trouble finding the base case as well. I was able to write pretty decent pseudocode, but I'm having trouble. I don't know if I'm allowed to ask homework questions on here, but this was a question I could not answer:

Let f(n) be the number of additions performed by this computation. Write a recurrence equation for f(n). (Note that the number of addition steps should be exactly the same for both the non-recursive and recursive versions. In fact, they both should make exactly the same sequence of addition steps.)

Any help would be great, if I'm not allowed to ask the homework question that's okay.

   int sum(int A[], int n ):
     T=A[0];
      for i = 1; to n-1
       T=T+A[i];
        return T;}

Upvotes: 0

Views: 1624

Answers (2)

Sergii Zagriichuk
Sergii Zagriichuk

Reputation: 5399

Just re-wrote your variant

   int sum(int A[], int n ):
      if (n > 1){
       T=A[n-1] + A[n-2];
       T += sum(A, n-2) 
      }else{
       if (n > 0) { return A[n -1];}
      }
     return T;
    }

Upvotes: 0

Erik
Erik

Reputation: 909

Use the following property of your sum function:

   sum(A[], n) == sum(A[], n-1) + A[n]

and take into account that:

   sum(A[], 1) == A[1]

Upvotes: 1

Related Questions