Learning to Write a Recursive Algorithm in Pseudocode

[evinda]

Hi! (Wave)

I want to write a recursive algorithm as a pseudocode.

How can I define the function? Which has to be its structure?

 

[I like Serena]

Hi! (Wave)

I want to write a recursive algorithm as a pseudocode.

How can I define the function? Which has to be its structure?

Hey! (Smile)

The standard example is:

//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}

The structure is:

1. a final condition that makes the recursion stop,
2. a recursive call.

The standard pitfall is that the final condition is not properly set, causing an infinite recursion.

 

[evinda]

The standard example is:

//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}

The structure is:

1. a final condition that makes the recursion stop,
2. a recursive call.

The standard pitfall is that the final condition is not properly set, causing an infinite recursion.

I am asked to find the maximum of an array.

Do I have to define the function as int or something else? (Thinking)

 

[I like Serena]

I am asked to find the maximum of an array.

Do I have to define the function as int or something else? (Thinking)

You can leave out the types, since they won't be relevant for the algorithm. (Mmm)

 

[evinda]

You can leave out the types, since they won't be relevant for the algorithm. (Mmm)

In my notes, there is this algorithm:

Index BinarySearch(Type A[0...N-1], Type value, Index low, Index high){
  if (high<low) return -1
  mid=low+(high-low)/2;
  if (A[mid]>value) return  BinarySearch(A, value, low,mid-1);
  else if (A[mid]<value) return  BinarySearch(A, value, mid+1,high);
  else return mid
}

What does Index represent? (Thinking)

 

[I like Serena]

In my notes, there is this algorithm:

Index BinarySearch(Type A[0...N-1], Type value, Index low, Index high){
  if (high<low) return -1
  mid=low+(high-low)/2;
  if (A[mid]>value) return  BinarySearch(A, value, low,mid-1);
  else if (A[mid]<value) return  BinarySearch(A, value, mid+1,high);
  else return mid
}

What does Index represent? (Thinking)

"Index" is an unspecified type that can be used as an index.
For practical purposes you can assume its an [m]int[/m]. (Nerd)

Btw, it looks more like real C code than pseudo code (except for a couple of syntax errors). (Wait)

 

[evinda]

"Index" is an unspecified type that can be used as an index.
For practical purposes you can assume its an [m]int[/m]. (Nerd)

What is the difference between Index and Type? What does the latter represent? (Worried)

Btw, it looks more like real C code than pseudo code (except for a couple of syntax errors). (Wait)

How could it be otherwise? (Thinking)

 

[evinda]

Also, at the algorithm, I want to use the floor function.

Can I write it like that: $\lfloor x \rfloor$ or do I have to write it like that: $\text{ floor }(x)$ ? (Thinking)

 

[I like Serena]

What is the difference between Index and Type? What does the latter represent? (Worried)

"Type" is an unspecified type for values that are in the array.
It might for instance be a [m]double[/m]. (Smile)

How could it be otherwise? (Thinking)

Well, the following is pseudo code for a binary search algorithm.
It is not C, nor any other actual programming language - it's pseudo code. (Angel)

function binarySearch(a, value, left, right)
    if right < left
        return not found
    mid := floor((right-left)/2)+left
    if a[mid] = value
        return mid
    if value < a[mid]
        return binarySearch(a, value, left, mid-1)
    else
        return binarySearch(a, value, mid+1, right)

Also, at the algorithm, I want to use the floor function.

Can I write it like that: $\lfloor x \rfloor$ or do I have to write it like that: $\text{ floor }(x)$ ? (Thinking)

Both are fine.

Pseudo code is only intended to get the idea of an algorithm across.
It does not have to be syntactically correct according to some formal programming language.
It's a sort of free style language. (Party)

 

[evinda]

"Type" is an unspecified type for values that are in the array.
It might for instance be a [m]double[/m]. (Smile)

Well, the following is pseudo code for a binary search algorithm.
It is not C, nor any other actual programming language - it's pseudo code. (Angel)

function binarySearch(a, value, left, right)
    if right < left
        return not found
    mid := floor((right-left)/2)+left
    if a[mid] = value
        return mid
    if value < a[mid]
        return binarySearch(a, value, left, mid-1)
    else
        return binarySearch(a, value, mid+1, right)

Both are fine.

Pseudo code is only intended to get the idea of an algorithm across.
It does not have to be syntactically correct according to some formal programming language.
It's a sort of free style language. (Party)

I understand! Could I also use the and operator like that:

if (condition1 && condition2)

or is it too C-like? (Wasntme)

 

[I like Serena]

I understand! Could I also use the and operator like that:

if (condition1 && condition2)

or is it too C-like? (Wasntme)

Up to you! (Nod)

Alternatively, you could write:

if condition1 and condition2

Which do you think is easier to read? (Wondering)

 

[evinda]

Up to you! (Nod)

Alternatively, you could write:

if condition1 and condition2

Which do you think is easier to read? (Wondering)

I think the second one is easier to read.. Do you agree? (Blush)

 

[I like Serena]

I think the second one is easier to read.. Do you agree? (Blush)

Yes. (Angel)