Application Center - Maplesoft

# Maple Programming: 4.13: Recursive procedures

You can switch back to the summary page by clicking here.

4.13.mws

Programming in Maple

Roger Kraft
Department of Mathematics, Computer Science, and Statistics
Purdue University Calumet

roger@calumet.purdue.edu

4.13. Recursive procedures (optional)

In this section we look at an idea that is important to both mathematics and computer science, the idea of recursion . Recursion means defining something in terms of itself. We will see, for example, that many common mathematical ideas can be given recursive definitions. But our main interest will be in recursive procedures. A procedure is recursive if the procedure calls itself somewhere in its body, which would mean that the procedure is defined in terms of itself. Recursive procedures are important in computer programming because they often provide very compact and elegant solutions to a programming problem. But, unfortunately, the compactness and elegance of recursive procedures comes at a steep price. Recursive procedures tend to be slow and they tend to consume massive amounts of computer memory when they execute. We will see this with a couple of our examples.

 >

Here is a famous example of recursion in mathematics. If  is a positive integer, the symbol  (read "n factorial") is defined to be the product of all the positive integers less than or equal to . Using mathematical notation we would write

*( )*( )*...*3*2*1.

So for example  = 3*2*1 = 6, and 5! = 5*4*3*2*1 = 120. There is another way to define , a recursive way. The recursive definition is

.

This recursive definition defines factorials in terms of factorials. The factorial symbol appears on both side of the equal sign in the definition. Here is how we could try to compute  using this definition.

5! = 5*(4!) = 5*(4*(3!)) = 5*(4*(3*(2!))) = 5*(4*(3*(2*(1!)))) = 5*(4*(3*(2*(1*(0!)))))

But how did we know when to stop using the formula ? We certainly do not want to write 5*(4*(3*(2*(1*(0*(-1!)))))) as the next step in the calculation. Besides implying that this calculation will go on for ever, it also seems to imply that the result is zero. We need something to bring the "recursion" to a halt. For the factorial function, that something is the rule that 0!=1. With that rule the calculation of  becomes

5! = 5*(4!) = 5*(4*(3!)) = 5*(4*(3*(2!))) = 5*(4*(3*(2*(1!)))) = 5*(4*(3*(2*(1*(0!)))))=5*4*3*2*1=120.

So the complete recursive definition of the factorial function has two parts

and    .

Now we can take this recursive definition and implement it as a recursive procedure in Maple.

 > recursive_factorial := proc(n::nonnegint)

 > if n=0 then

 > 1

 > else

 > n*recursive_factorial(n-1)

 > fi;

 > end;

Notice how both parts of the recursive definition appear in the recursive procedure. The procedure is recursive because in the 5'th line of the procedure it calls itself, and that is one part of the recursive definition of . The other part of the recursive definition is the conditional statement that checks if the input is zero (we will talk about the details of conditional statements in the next chapter).

Let us compute some factorials using this recursive procedure.

 > recursive_factorial(5);

 > recursive_factorial(85);

There is a factorial function built into Maple so we can check our results.

 > 85!;

 >

Unfortunately, recursion is not always the best way to implement a procedure. For example, the next command does not work because recursion forces Maple to use so much of its computer memory that Maple runs out of space to store results.

 > recursive_factorial(4779);

```Error, (in recursive_factorial) too many levels of recursion

```

But the built in Maple function for computing factorials has no trouble computing this result. It is not a recursive procedure.

 > 4779!:  # Don't display this number.

 > length( % ); # In case you are curious.

 >

Here is a trick that will helps us to visualize the workings of this recursive procedure. In the body of the procedure, use right-quotes to delay the evaluation of the recursive procedure call.

 > recursive_factorial := proc(n)

 > if n=0 then

 > 1

 > else

 > n*'recursive_factorial(n-1)'

 > fi;

 > end;

Now call the procedure and then keep evaluating the output until it is fully evaluated.

 > recursive_factorial(5);

 > %;

 > %;

 > %;

 > %;

 > %;

 >

Here is another way in which we can kind of watch the recursion take place We put in our procedure the line option trace . This causes Maple to "trace" all the steps that the procedure goes through as it calculates. (The option trace  line should go in a procedure body after any local and global variable declarations.)

 > recursive_factorial := proc(n)

 > option trace;

 > if n=0 then

 > 1

 > else

 > n*recursive_factorial(n-1)

 > fi;

 > end;

Now call the procedure and study the output.

 > recursive_factorial(5);

`{--> enter recursive_factorial, args = 5`

`{--> enter recursive_factorial, args = 4`

`{--> enter recursive_factorial, args = 3`

`{--> enter recursive_factorial, args = 2`

`{--> enter recursive_factorial, args = 1`

`{--> enter recursive_factorial, args = 0`

`<-- exit recursive_factorial (now in recursive_factorial) = 1}`

`<-- exit recursive_factorial (now in recursive_factorial) = 1}`

`<-- exit recursive_factorial (now in recursive_factorial) = 2}`

`<-- exit recursive_factorial (now in recursive_factorial) = 6}`

`<-- exit recursive_factorial (now in recursive_factorial) = 24}`

`<-- exit recursive_factorial (now at top level) = 120}`

 >

Here is a non-mathematical, non-programming example of recursion, a recursive acronym. Let the acronym CALC stand for Can Anyone Like CALC.  If we continue to expand the acronym, it will grow forever, since the acronym refers to itself. This infinite regress has to be avoided in mathematical or programming examples of recursion. In fact, we saw in an earlier chapter an example in Maple of recursion with an infinite regress when we did the following:

 > x := 'x';  # Unassign x.

 > x := x+1;  # Give x a recursive (i.e., self-referential) definition.

```Error, recursive assignment

```

 >

When we write recursive procedures, we always have to do something to avoid infinite recursion. For example, if we take this definition of factorial, , too literally, then we end up with the following procedure.

 > recursive_factorial := proc(n)

 > n*recursive_factorial(n-1)

 > end;

Let us try this version out.

 > recursive_factorial(5);

```Error, (in recursive_factorial) too many levels of recursion

```

It does not work. Why is the mathematical definition of factorial not infinitely recursive? Because we also have the rule that 0!=1, and that definition stops the recursion after a finite number of steps.

 >

Exercise : Lots of simple mathematical ideas can be given recursive definitions. For example, if  is a real number and  is a positive integer, then  and  can be given the following recursive definitions.

and

What are the proper "terminating" conditions for these definitions?

 >

Here is another simple recursive procedure. This procedure adds up all the numbers in a list. Notice how we avoid the problem of infinite recursion by using an if-then-else-fi statement to check for a "terminating" condition.

 > if nops(x)=0  # This check prevents infinite regress;

 > then          # if there is nothing in the list,

 > 0           # then we return 0.

 > else

 > x[1] + add_list(x[2..-1])  # Here's the recursion.

 > fi;

 > end;

Give it a try.

In the next chapter we will see how to write a non recursive procedure for adding up a list of numbers.

 >

Here is add_list  with delayed evaluation of the recursive procedure call.

 > if nops(x)=0  # This check prevents infinite regress;

 > then          # if there is nothing in the list,

 > 0           # then we return 0.

 > else

 > ''''''x[1]'''''' + 'add_list(x[2..-1])'  # Here's the recursion.

 > fi;

 > end;

Notice that we also added a lot of delayed evaluation to the x[1]  term in front of the recursive call. This is there to make the output from the following procedure call more illustrative of what is going on.

 > %;

 > %;

 > %;

 > %;

 > %;

 > %; %; %; %; %;

Here is add_list  with option trace .

 > option trace;

 > if nops(x)=0

 > then

 > 0

 > else

 > fi;

 > end;

Look carefully at the following output. Notice how it shows that the addition gets done from right to left in the list, not from left to right.

`{--> enter add_list, args = [1, 2, 3, 4, 5]`

`{--> enter add_list, args = [2, 3, 4, 5]`

`{--> enter add_list, args = [3, 4, 5]`

`{--> enter add_list, args = [4, 5]`

`{--> enter add_list, args = [5]`

`{--> enter add_list, args = []`

`<-- exit add_list (now in add_list) = 0}`

`<-- exit add_list (now in add_list) = 5}`

`<-- exit add_list (now in add_list) = 9}`

`<-- exit add_list (now in add_list) = 12}`

`<-- exit add_list (now in add_list) = 14}`

`<-- exit add_list (now at top level) = 15}`

 >

Exercise : The definition of add_list  with delayed evaluation seems to imply that the addition is done from left to right in the list. The definition of add_list  with option trace  seems to imply that the addition is done from right to left in the list. Which is correct? Explain why one of these procedures gives an incorrect impression.

 >

Exercise : Consider the following recursive version of add_list .

 > if nops(x)=1

 > then

 > x[1]

 > else

 > x[1] + add_list(x[2..-1])  # Here's the recursion.

 > fi;

 > end;

Explain how it is different from the previous version. Which is better and why?

 >

Exercise : Write a recursive procedure call prod_list  that computes the product of a list of numbers.

 >

In the next chapter, in the section on conditional statements, we will write a procedure biggest  that finds the largest number in a list of numbers. Here we write a recursive version of this procedure. First, we need a procedure that finds the larger of just two numbers.

 > bigger := proc(a,b)

 > if a >= b then a else b fi;

 > end;

Now we can use bigger  to write a version of biggest  that is recursive. The procedure biggest  will take in only one input, a list (which can be arbitrarily long). The recursive idea behind biggest  is contained in the following sentence:

The biggest  number in the list [17, 3, 23, 45, 87, 67] can be defined as the bigger  of 17 and the biggest  number from the list [3, 23, 45, 87, 67].

This definition of biggest  was self-referential since biggest  appeared in the definition of biggest . But the first appearance of biggest  was referring to a list with six numbers in it and the second appearance of biggest  was referring to a list with five numbers in it (the first list with the first number deleted from it). The following procedure implements this recursive definition of biggest .

 > biggest := proc(x::list)

 > if nops(x)=1 then   # This check prevents infinite recursion.

 > x[1]

 > else

 > bigger(x[1], biggest(x[2..-1]))

 > fi;

 > end;

Let us test it on a short list of numbers.

 > biggest( [17, 3, 23, 45, 87, 67] );

Let us test biggest  on a list of randomly chosen integers. The following command creates the list (change the colon to a semicolon to see the list). If the list is much longer, then we get a "too many levels of recursion" error from Maple when we call biggest . (At least I did on my computer. The maximum size of the list depends on how much memory your computer has.) This is because recursive procedures are very inefficient and they almost always run slower and use more memory than non-recursive procedures. You can check this by testing the non-recursive version of biggest  from the next chapter. Test that version of biggest  with any size list of randomly chosen integers.

 > random_list_of_integers := [ seq( rand(), i=1..520 ) ]:

 > biggest( random_list_of_integers );

 >

Exercise : Use long lists of random numbers to find out how long a list of numbers the recursive add_list  can add. After you have seen how to add a list of numbers non recursively in the next chapter, see how long a list of numbers the non recursive add_list  can add.

 >

Let us define biggest  with delayed evaluation of the recursive procedure call.

 > biggest := proc(x::list)

 > if nops(x)=1 then   # This check prevents infinite recursion.

 > x[1]

 > else

 > bigger(x[1], 'biggest'(x[2..-1]))

 > fi;

 > end;

Let us try this version.

 > biggest( [17, 3, 23, 45, 87, 67] );

```Error, (in bigger) cannot determine if this expression is true or false: biggest([3, 23, 45, 87, 67])-17 <= 0

```

We can fix this problem by modifying the definition of bigger . The following version of bigger  will "return unevaluated" when it is called with non numeric operands. This technique is discussed in the next chapter.

 > bigger := proc(a,b)

 > if type( a, numeric ) and type( b, numeric ) then

 > if a >= b then a else b fi;

 > else

 > RETURN( 'procname(args)' )

 > fi;

 > end;

Now we can call the version of biggest  with delayed evaluation of the recursive procedure call.

 > biggest( [17, 3, 23, 45, 87, 67] );

 > %; %; %; %; %;

 >

Now let use option trace  to watch biggest  and bigger  do their work.

 > bigger := proc(a,b)

 > option trace;

 > if a >= b then a else b fi;

 > end;

 > biggest := proc(x::list)

 > option trace;

 > if nops(x)=1 then

 > x[1]

 > else

 > bigger(x[1], biggest(x[2..-1]))

 > fi;

 > end;

 > biggest( [17, 3, 23, 45, 87, 67] );

`{--> enter biggest, args = [17, 3, 23, 45, 87, 67]`

`{--> enter biggest, args = [3, 23, 45, 87, 67]`

`{--> enter biggest, args = [23, 45, 87, 67]`

`{--> enter biggest, args = [45, 87, 67]`

`{--> enter biggest, args = [87, 67]`

`{--> enter biggest, args = [67]`

`<-- exit biggest (now in biggest) = 67}`

`{--> enter bigger, args = 87, 67`

`<-- exit bigger (now in biggest) = 87}`

`<-- exit biggest (now in biggest) = 87}`

`{--> enter bigger, args = 45, 87`

`<-- exit bigger (now in biggest) = 87}`

`<-- exit biggest (now in biggest) = 87}`

`{--> enter bigger, args = 23, 87`

`<-- exit bigger (now in biggest) = 87}`

`<-- exit biggest (now in biggest) = 87}`

`{--> enter bigger, args = 3, 87`

`<-- exit bigger (now in biggest) = 87}`

`<-- exit biggest (now in biggest) = 87}`

`{--> enter bigger, args = 17, 87`

`<-- exit bigger (now in biggest) = 87}`

`<-- exit biggest (now at top level) = 87}`

 >

Here is still another way to visualize what is going on as biggest  executes recursively. We keep option trace  in biggest  and remove it from bigger , and we prevent the evaluation of bigger  in the body of biggest .

 > bigger := proc(a,b)

 > if a >= b then a else b fi;

 > end;

 > biggest := proc(x::list)

 > option trace;

 > if nops(x)=1 then

 > x[1]

 > else

 > 'bigger'(x[1], biggest(x[2..-1]))

 > fi;

 > end;

Now call this version of biggest . If you carefully study and think about all of this output, it should help you build up a sense of how recursive procedures really execute.

 > biggest( [17, 3, 23, 45, 87, 67] );

`{--> enter biggest, args = [17, 3, 23, 45, 87, 67]`

`{--> enter biggest, args = [3, 23, 45, 87, 67]`

`{--> enter biggest, args = [23, 45, 87, 67]`

`{--> enter biggest, args = [45, 87, 67]`

`{--> enter biggest, args = [87, 67]`

`{--> enter biggest, args = [67]`

`<-- exit biggest (now in biggest) = 67}`

`<-- exit biggest (now in biggest) = bigger(87,67)}`

`<-- exit biggest (now in biggest) = bigger(45,bigger(87,67))}`

`<-- exit biggest (now in biggest) = bigger(23,bigger(45,bigger(87,67)))}`

`<-- exit biggest (now in biggest) = bigger(3,bigger(23,bigger(45,bigger(87,67))))}`

`<-- exit biggest (now at top level) = bigger(17,bigger(3,bigger(23,bigger(45,bigger(87,67)))))}`

Now we can execute all these calls to bigger .

 > %;

 >

Exercise : Write a self-contained version of biggest  that does not need the procedure bigger .

 >

Exercise : Notice that the definition of biggest  does not work with an empty list.

 > biggest( [] );

`{--> enter biggest, args = []`

`<-- ERROR in biggest (now at top level) = "invalid subscript selector"}`

```Error, (in biggest) invalid subscript selector

```

The proper definition of biggest  is that it should return the smallest number that is greater than or equal to every number in the list. By this definition, the value of biggest  for an empty list is negative infinity. Write a version of biggest  that returns this value for an empty list.

 >

A famous example of recursion in mathematics is the definition of the Fibonacci numbers which are defined by , , and  for . Here is a recursive procedure that computes these numbers.

 > Fib := proc(n::posint)

 > if n = 1 then 1

 > elif n = 2 then 1

 > else Fib(n-1) + Fib(n-2)

 > fi

 > end;

An interesting feature of this procedure is that it is wildly inefficient. This procedure has trouble computing even fairly small Fibonacci numbers. For example, the following calculation takes quite a while.

 > Fib(30);

Here is an explanation of why this procedure is so inefficient. To compute Fib(30)  we need to compute Fib(29)  and Fib(28) . To compute Fib(29)  we need to compute Fib(28)  (again) and Fib(27) . To compute Fib(28)  we need to compute Fib(27)  and Fib(26) . Notice that to compute Fib(30)  we need to compute Fib(27)  three distinct times and we need to compute Fib(26)  five distinct times. We can show this better with a tree diagram.

The following calculation shows that just one computation of Fib(27)  takes quite a while.

 > Fib(27);

So we can conclude that this recursive procedure is so inefficient because it is forced to recalculate the same results over and over again. But we have an elagant way to prevent a Maple procedures from recalculating a result. Let us redefine Fib  with option remember .

 > Fib := proc(n::posint)

 > option remember;

 > if n = 1 then 1

 > elif n = 2 then 1

 > else Fib(n-1) + Fib(n-2)

 > fi

 > end;

Now the calculation of Fib(30)  is practically instantaneous.

 > Fib(30);

If we look at the remember table, we can see the intermediate values calculated by Fib .

 > op( 4, eval(Fib) );

This is a very dramatic example of something we mentioned in the section on remember tables, that we can often increase a calculation's speed by using more memory space. In this example, the trade off between time and memory space is very dramatic. It can be shown that the time it takes to compute Fib(n)  (without the remember table) grows quadratically with n . So if we double n  we should expect the calculation time to quadruple. But with a remember table, the size of the remember table only grows linearly with n .

Exercise : In the version of Fib  that does not have option remember, how many times must Fib(2)  be calculated in the calculation of Fib(30) . Hint: Try to think of a simple way to have Maple figure this out for you.

 >

Here is an interesting application of recursion to periodic functions. We say that a function f from the real line to the real line is periodic with period  if  and  for all real numbers . Notice that this is almost a recursive definition since it defines f in terms of itself. But this definition is not recursive because it does not contain any kind of a terminating condition. As it stands, this definition defines the notion of being periodic for any function, but it does not define any specific periodic function. Here is how we adapt this definition to give a recursive definition of a specific periodic function. Let g be a function defined on the interval from  to , where  and . Here is a recursive definition of a function f which is a periodic extension of g to the whole real line.

Notice that this definition of f is recursive because f is defined in terms of f, and g plays the role of the terminating condition in this recursive definition. Let us use a specific example to see how this definition works. Let , , and . Let g be defined by

for .

Define the periodic function f using the recursive definition above. Now consider how we evaluate . According to the definition of f we would do the following

=  =  = 0.

How would we evaluate f(-3.5)?

 >

Let us implement these definitions using Maple. First define a , b , p  and g .

 > a := 0; b := 1;

 > p := 'b'-'a';

 > g := x -> piecewise( a<=x and x

Here is what g  looks like as an expression.

 > g(x);

Now define f .

 > f := proc(x)

 > if a<=x and x

 > g(x)

 > elif b<=x then

 > f(x-p)

 > elif x

 > f(x+p)

 > fi

 > end;

We can evaluate f .

 > f(5.5), f(-3.5), f(127.8);

But because f  is defined recursively, there is a limit to how large of a value we can plug into it.

 > f(10027.8);

```Error, (in f) too many levels of recursion

```

Here are graphs of g  and its periodic extension f .

 > plot( g, -2..2, scaling=constrained, discont=true, color=red );

 > plot( f, -2..2, scaling=constrained );

 >

Let us try using f  with a couple of well known periodic functions for g .

 > a := 0; b := 2*Pi;

 > g := x -> piecewise( a<=x and x

 > plot( g, -4*Pi..4*Pi, scaling=constrained, discont=true, color=red );

 > plot( f, -4*Pi..4*Pi, scaling=constrained );

 > a := 0; b := 2*Pi;

 > g := x -> piecewise( a<=x and x

 > plot( g, -4*Pi..4*Pi, scaling=constrained, discont=true, color=red );

 > plot( f, -4*Pi..4*Pi, scaling=constrained );

Notice that we do not need to redefine f . We just need to redefine a , b , and g , and then f  will automatically be the periodic extension of g  with period p=b-a .

 >

Exercise : With a , b , and g  defined as in the last example, try to figure out what causes the following error.

 > f(2);

```Error, (in f) cannot determine if this expression is true or false: -2*Pi < -2

```

 >

Exercise : Suppose we make a=0 , b=p>0 , and we define g  on the interval from 0  to p . What conditions on g  would make f  a continuous function? What conditions on g  would make f  an even function? What conditions on g  would make f  an odd function?

 >

Exercise : The following definition for the periodic extension of g  would seem reasonable enough (everything that is inside the piecewise  function is exactly like the conditional statement inside the body of f ). But it does not work.

 > f_wrong := x -> piecewise( a<=x and x

 > b<=x, f_wrong(x-p),

 > x

Let us try it. Define a function g  to extend.

 > a := 0; b := 1; p := 'b' - 'a';

 > g := x -> piecewise( a<=x and x

Now try to evaluate the extension.

 > f_wrong(1/2);

The problem is that piecewise  uses full evaluation so it always tries to evaluate every expression inside its parentheses. Figure out why this causes the infinite recursion.

 >

However, here is something very strange. The plot  command can graph f_wrong , even using this incorrect definition! How does the plot  command manage to evaluate f_wrong  when Maple cannot evaluate f_wrong  at the top level? I have no idea.

 > plot( f_wrong, -2..2, scaling=constrained );

 >

Exercise : Suppose we have a=0  and b=p>0  and we define g  for x  between 0  and p . Then the periodic extension f  may be an even function or an odd function or it may be neither even nor odd. There is a way to define a 2*p  periodic extension of g  that is always even, no matter what g  is. Consider the following recursive definition of f_even .

 > f_even := proc(x)

 > if 0<=x and x

 > g(x)

 > elif -p<=x and x<0 then

 > g(-x)

 > elif p<=x then

 > f_even(x-2*p)

 > elif x<-p then

 > f_even(x+2*p)

 > fi

 > end;

Let us try it with a particular p  and g .

 > p:=3*Pi/4;

 > g := x-> piecewise( x>0 and x

Here are graphs of g  and it 2*p  periodic even extension.

 > plot( g, -4*Pi..4*Pi, scaling=constrained, discont=true, color=red );

 > plot( f_even, -4*Pi..4*Pi, scaling=constrained );

Here is what the graph of f , the p  periodic extension of g , would look like for the same g .

 > a:=0: b:=p:

 > plot( f, -4*Pi..4*Pi, scaling=constrained, discont=true, color=red );

The function f_even  is called the "even periodic extension of g  with period 2*p ". Explain how f_even  creates the even, 2*p  periodic version of g .

 >

Write a recursive procedure f_odd  that defines a 2*p  periodic extension of g  that is odd for any g  defined on the interval from 0  to p .

 >

Exercise : The following recursively defined function seems OK.

 > saw := proc(t) if   frac(abs(t)) < 1/4  then 4*frac(abs(t))

 > elif frac(abs(t)) < 1/2  then saw(1/2-abs(t))

 > elif frac(abs(t)) <= 1   then saw(1-abs(t))

 > fi

 > end;

We can graph the function.

 > plot( saw, 0..1 );

 > plot( saw, -2..2 );

But not always.

 > plot( saw, 0..1/2 );

```Error, (in plot/adaptive) too many levels of recursion

```

 > plot( t->saw(t-1/4), 0..1 );

```Error, (in plot/adaptive) too many levels of recursion

```

Figure out what is wrong with the definition of saw . Why can plot  sometimes graph saw  and sometimes it can't? Fix the definition of saw  so that it always works.

Hint:

 > saw(1/4);

```Error, (in frac) too many levels of recursion

```

 >

 >

 >