Simple Recursion?

0
votes

I'm new to programming and have had a hard time understanding recursion. There's a problem I've been working on but can't figure out. I really just don't understand how they are solvable.

"Define a procedure plus that takes two non-negative integers and returns their sum. The only procedures (other than recursive calls to plus) that you may use are: zero?, sub1, and add1.

I know that this is a built in functions in scheme, so I know they're possible to solve, I just don't understand how. Recursion is so tricky!

Any help would be greatly appreciated! =] Thanks

I'm working in Petite Chez Scheme (with the SWL editor)

3
recursionscheme
See: stackoverflow.com/questions/5037281/simple-recursion - Maxpm
@Maxpm not so simple, you'd get caught in an infinite recursion with that one, eventually devouring all your memory!!! - Endophage
@Endophage Which would, of course, result in the programmer posting a question about it here on Stack Overflow. But then we're right back where we started... ;) - Maxpm
@Maxpm See: stackoverflow.com/questions/5037281/simple-recursion - Endophage
lol, hey IRC buddy. :] office hours are killing me. i'm there like all day every wednesday - mdegges

3 Answers

4
votes

Recursion is a very important concept in software development. I don't know (petit chez) scheme so I will approach this from a general angle.

The concept of a recursive function is to repeat the same task over and over again until you reach some limiting boundary. Taking your first question, you have two numbers and you need to add them together. However, you only have the ability to add 1 to a number or subtract 1 from a number. You also have the literal value zero.

So. consider you numbers as two buckets. They each have 10 stones in them. You want to "add" those two buckets together. You are only permitted to move one stone at a time (i.e. you can't grab a handful or tip one bucket into the other).

Lets say you want to move everything from the left bucket into the right bucket, one stone at a time. What are you going to have to do?

First, you have to take 1 stone from the left bucket, i.e. you are using sub1 to remove one stone from the bucket. You then add that same stone to the right bucket, i.e. you add1 to the right bucket.

Now you could do this in a loop, but you don't know how many stones there will be in any given solution. What you really want to do is say "Take one stone from the left bucket, put it in the right bucket and repeat until there are no stones in the left bucket.' This case of there being no stones in the left bucket is called you "Base Case". It's the point at which you say OK, I'm done now.

A pseudocode example of this situation would be (using your plus, add1, sub1 and zero):

plus(leftBucket, rightBucket)
{
  if(leftBucket == zero) // check if the left bucket is empty yet
  {
    // the left bucket is empty, we've moved all the stones
    return rightBucket; // the right bucket must be full
  }
  else 
  {
    // we still have stones in the left bucket, remove 1, 
    // put it in the right bucket, repeat.
    return plus(sub1(leftBucket), add1(rightBucket)); 
  }
}

If you still need more help, let me know, I can run through other examples but this looks like it's probably a homework problem for you and recursion is incredibly important to understand so I don't want to just give you all the answers.

2
votes

Recursion is simply a function that calls itself. The most common, easily understood examples of recursion is walking a data structure that looks like a tree.

How would you visit each branch of a tree? You would start at the trunk and call visit(branch), passing the trunk of the tree as the first branch. Visit() calls itself for each branch of each branch, and so on.

public void visit(Branch branch)
{
    // do something with this branch here

    // visit the branches of this branch
    foreach(var subbranch in branch.branches)
    {
        visit(subbranch)
    }
}
2
votes

Recursion is closely related to induction - first you solve (or prove) a base case, and then you assume your solution is correct for some value n, and use that to solve (or prove) it for n + 1.

So the first step here is to look at the first problem. What would be a good base case for adding two numbers together?

Alright, so we have our base case: when one of the numbers is zero.

For simplicity's sake, we'll assume that the second number is zero, just to make things a little easier.

So we know that (+ n 0) is equal to n. So now for our recursive step, we want to take an arbitrary call (+ x y), and turn that into a call which is closer to our ideal (+ n 0). That way we'll have made some progress and will eventually solve our problem.

So how are we going to do this?

(+ x y) is of course equivalent to (+ (add1 x) (sub1 y)) - which takes us closer to our base case of (zero? y).

This gives us our final solution:

(define (+ x y)
  (if (zero? y)
    (x)
    (+ (add1 x) (sub1 y))
))

(you can, of course, swap the order of the arguments and it will still be equivalent).

A similar mechanism can be used to solve the other two problems.