Help on thinking recursively?

C

Celeritas

n00b
Joined
Dec 5, 2011
Messages
1
I know this is a very vague question but I just started programming and I've been using python for the past few months. The major problem I've always encountered while programming is thinking recursively. I just can't seem to write a recursive function easily. Do you guys have any tips that helped you write these functions much easier?
 
One way my CS teacher explained it was just to look at it one part at a time. If you write the code to handle the base case, and one simple case, it should work for every case.

The simplest example he used was printing a string... if you think about it in the simplest terms... you'll print one character, then move to the next element and print that one. Well one way to write that recursively is just like this.

Code: 
void PrintString( char const* str ) 
{
  if( str ) 
  {
    putchar( *str );
    PrintString( str + 1 );
  }
}

So you can see right here it has the base case of checking the pointer is valid ( c-style are null-terminated ). And then printing the character and moving to the next one.

The order in which you "do work" compared to calling the recursive function makes a difference...

Code: 
void PrintStringRev( char const* str ) 
{
  if( str ) 
  {
    PrintStringRev( str + 1 );
    putchar( *str );
  }
}

This will print the string in reverse. I didn't have to change anything other than the ordering of the function calls. If you write it out on paper what would happen it can help it make more sense. The 2nd function will go until it reaches the end of the string ( the base case ). Then it will start returning from all those function calls and begin printing the string. But because it's at the end of the string it will be printing those characters before it prints the starting characters.

So I figure there are ~3 basic steps to recursive functions. Base case(s), Work, Calling recursive function... the last 2 can be in different orders but the base case is pretty much always the first thing you check.

Binary Trees are trivial to traverse because of recursion. Doesn't matter how many elements or how balanced it is, you can traverse the entire tree with a few lines of code...

Hope that helps. I still have issues trying to wrap my head around recursion in more complex cases. It always ends up being simpler than I made it out to be. As you can see though, printing a string in reverse with recursion is actually simpler than the iterative version. The iterative version you would have to find out the length of the string, or where the end of the string is before you could start printing.
 
^^^ yeah, fibonacci is one of the most famous recursive functions. if you aren't familiar, the value of fib(x) is equal to the sum of fib(x-1) and fib(x-2).

the sequence goes: 0,1,1,2,3,5,8,13,21,35, ...

so, you could write this something like:

Code: 
int fib (int x) {
  if (x == 0) { return 0; }
  if (x == 1) { return 1; }
  if (x > 1) { return fib(x-1) + fib(x-2); }
}

print fib (7);

# result is 13.
 
berky said:
^^^ yeah, fibonacci is one of the most famous recursive functions.
Click to expand...
It's also one of the best examples of how recursion can be terribly inefficient. In your example, how many times is fib() called for fib(300)

Blazestorm said:
One way my CS teacher explained it was just to look at it one part at a time. If you write the code to handle the base case, and one simple case, it should work for every case.
Click to expand...
I agree -- that's mostly how I try to think of recursion. More specifically, I try to think of how I'd solve the simplest cases. Once I do that, I have a simple case, and if I can define how the next case goes in terms of a simpler case, I've got the problem in a state where I can use recursion to solve it.

While it's important to understand, recursion is generally eschewed because it involves stack space, which is unpredictably available when it runs out it's impossible to recover from the problem. Professional developers prefer non-recursive solutions as a result.
 
one of my favorite recursive functions

Code: 
void int2bin(int x)
{
  if (x > 0){
    int2bin(x/2);
  }
  cout << x % 2;
}
 
Think about a stack of bills due.

You pay bills

which involves taking a bill off the stack
taking the money out of your pocket
sending the money and the bill away

then, if you have money left and there are bills left you pay bills
if not you can return the value of whatever money you have left.


So the process will continue until an end condition is met.
Either you're out of money or you have no more bills.

You might also think of it like this:

While (My_Money > 0 && Bills.Any())
{
My_Money = Amount_Remaining_After_Paying_Bill(Bills.Pop, My_Money)
}

But that is a stinky form, imho, because the principle of your money and your stack of bills are too far abstracted from what you're doing with them.
 
You must think of your problem in terms of dividing it into smaller identical problems.

An important thing you must do in recursion is make sure you have a base case or cases and that it will be hit to prevent infinite recursion which would likely cause a stack overflow.

For example in tree traversal, say I have a binary sorted tree of items. (notice child nodes to the left of a node are less than it, and to the right are greater)

e.g.

Code: 
              8
           /      \
         6         20
       /   \       /   \
     2     7    13  40

If I want to print the items out in numerical order, consider each node is in itself a sub-tree with a value and left and right node.

For a simple case..

Code: 
   6
 /    \
2      7

You would need to do:

Print node's left child (2)
Print node's value (6)
Print node's right child (7)

or in other words:
print values less than the current node
print the value of the current node
print values greater than the current node

The important point is making sure the recursive function will terminate. In this case the base case could be if the current node is null

function InOrderTraversal(node)
{

if (node == null)
return;
Print(node.Left)
Print(node.Value)
Print(node.Right)

}

Notice to prevent this thing from either infinitely calling itself, or in this case trying to use null nodes that don't exist, the base case is important to check first (whether the current node is null),
 
Recursion is a tough concept to grasp. You will learn it and think you know it (second order incompetence), and it is not until you realize that you didn't understand it the first time that you will actually comprehend it.

Like anything else working with it will help you learn it.

One thing which may help you get a grasp on it is that this is always true:
Whatever you expect as a result must always be passed down the stack. This is also what you start out with. So this object that is your initial input parameter must be passed down to the bottom of the call stack and then returned back up. The bottom of the call stack is where you do your last computation, the end of the recursion.

What goes down must come up.
 
CC_Pirate said:
One thing which may help you get a grasp on it is that this is always true:
Whatever you expect as a result must always be passed down the stack. This is also what you start out with. So this object that is your initial input parameter must be passed down to the bottom of the call stack and then returned back up. The bottom of the call stack is where you do your last computation, the end of the recursion.
Click to expand...

Your assertions aren't always true.

The deepest call nesting might be where you do your first computation. The Fibonacci example posted earlier here demonstrates that.

The initial input parameter isn't always passed down the call nesting, as well. Both recursion examples in this thread don't do that. Instead, they modify the initial argument and pass it along to the next layer of calls.
 
mikeblas said:
Your assertions aren't always true.

The deepest call nesting might be where you do your first computation. The Fibonacci example posted earlier here demonstrates that.
Click to expand...

OK, but I was just trying to illustrate what the "bottom" of the stack is.

they modify the initial argument and pass it along to the next layer of calls.
Click to expand...
That was what I meant.
 
I had profs who described recursion in a variety of ways. My two favourite were from profs who described recursion in a variety of ways. My two favourite.. (and so forth).

Anyway, my two favourite were clones and magic.

Lets consider a function which sums the items in a list of numbers:
Code: 
(define (sum-list lon)
  (cond [(empty? lon) 0]
        [else (+ (first lon) (sum-list (rest lon)))]))

This function will function such that
Code: 
> (sum-list (list 1 2 3))
6


So, clones. All of your clones are -incredibly- nearsighted and are only capable of seeing what is directly in front of them.

You are presented with a list of numbers ( 1 2 3 ) and are told to report back with the sum. Being unsure of how to do this, you hold on to the 1, and clone yourself. You ask your clone what the sum of the list ( 2 3 ) is, knowing that once you find that out, you can add 1 to it. Your clone, like yourself, doesn't know how, and similarly holds onto the 2, clones himself, and asks it to tell it the sum of the list ( 3 ). This clone holds onto the 3, clones himself, and asks it to tell it the sum of the list ( ) [the empty list].

At this point this last clone exclaims "I know the answer to this! It is empty! There is nothing and the answer is 0!". He tells this to the clone before him, and proceeds to shoot himself in the head.

With this information, the second clone as easily able to add 3 + 0. He tells the clone before him: "The sum of this list is 3!" and shoots himself in the head.

Similarly, your initial clone takes this sum and adds it to his 2. "The answer to your question is 5 you dashingly handsome fellow!". He shoots himself in the head.

Finally, with your 1, and the knowledge that the rest of the list sums to 5, you're able to complete your task, having summed the list to 6.

The process illustrated as such:
Code: 
(sum? ( 1 2 3 ))
1 + (sum? ( 2 3 ))
1 + 2 + (sum? ( 3 ))
1 + 2 + 3 + (sum? ( ))
1 + 2 + 3 + 0
1 + 2 + 3
1 + 5
6

The important part here, is knowing your base case, where the empty list has a sum of zero.


So how did I write this function?
Code: 
(define (sum-list lon)
  (cond [(empty? lon) 0]
        [else (+ (first lon) (sum-list (rest lon)))]))

I proceed as such.

I start off my function
Code: 
(define (sum-list lon)

Now, I know I need a base case. I think to myself that the empty list is empty, and thus has a sum of 0, and write this in.

Code: 
(define (sum-list lon)
  (cond [(empty? lon) 0]

I also know, that to find the sum of a list, I can add the first item, to the sum of the remainder of the list.

Code: 
(define (sum-list lon)
  (cond [(empty? lon) 0]
        [else (+ (first lon) ...)]))

But I need a function which finds the sum of a list in order to do this. Aha! I'm writing one right now!

Code: 
(define (sum-list lon)
  (cond [(empty? lon) 0]
        [else (+ (first lon) (sum-list (rest lon)))]))

And there we go. Magic.


Apologies if this appears quite dumbed down. Hope it helps.
 
mikeblas said:
It's also one of the best examples of how recursion can be terribly inefficient. In your example, how many times is fib() called for fib(300)
Click to expand...

absolutely. which is also one of the reasons you learn how to take a recursive function and make it non-recursive. in some cases, it may not be possible, but sometimes a function can be written using both algorithms.

fib() could also be written like this for efficiency (taken from another site):

Code: 
int fib (int x) {
  int result = 1;
  int prev = -1;
  int sum = 0;
  for (int i = 0; i < x; i++) {
    sum = result + prev;
    prev = result;
    result = sum;
  }
  return result;
}

print fib (7);

# result is 13.
 
berky said:
absolutely. which is also one of the reasons you learn how to take a recursive function and make it non-recursive. in some cases, it may not be possible, but sometimes a function can be written using both algorithms.
Click to expand...
The answer I was looking for was that it's exponential; something like O(phi ^ n) calls. At n=300, that is about 1.72 x 10^61 calls, which means the program won't finish any time soon. The linear approach does something like O(n) additions.

berky said:
fib() could also be written like this for efficiency (taken from another site):
Click to expand...
This version actually does something sensible for negative numbers and is universes faster.
 
Celeritas said:
I know this is a very vague question but I just started programming and I've been using python for the past few months. The major problem I've always encountered while programming is thinking recursively. I just can't seem to write a recursive function easily. Do you guys have any tips that helped you write these functions much easier?
Click to expand...

Back when I was taking Java classes, this threw me too. We had to write a program for a game, where the two sides were setup using a recursive method. So they would play each other and there would be a winner. Big PITA.

You have to break it down to a very basic level of what is actually being asked of the method. It really does play in to the entire high level atmosphere of object oriented languages of simplifying methods (idea here is to reuse methods on other programs)
 
berky said:
fib() could also be written like this for efficiency (taken from another site):

Code: 
int fib (int x) {
  int result = 1;
  int prev = -1;
  int sum = 0;
  for (int i = 0; i < x; i++) {
    sum = result + prev;
    prev = result;
    result = sum;
  }
  return result;
}

print fib (7);

# result is 13.
Click to expand...

That solution is more efficient. However, I just wanted to mention that the Fibonacci sequence does have a closed form solution that does not require any iteration or recursion.

http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression
 
That closed-form solution doesn't teach us anything about recursion.
 
As a fellow young developer, here's two things that I've learned that helped me better understand recursion.

Recursion is (obviously) used when you need a solve a problem that repeats. An easy example to consider is if you wanted to write a program to traverse a nested folder structure on your computer.

For example, create a folder on your desktop and call it "A". Open A and create a new folder, "B". Open B, and create a new folder, "C".

You could write some recursive code to walk through any directory structure, and I'll use that example.

Without writing syntax, consider the problem:

In any given directory, for each directory you find, call yourself. Otherwise, exit.

Call your function and give it "A" as the argument. For each directory you find, call the function with the new directory.

From A, your function will call itself for B, and from B, it will call itself for C, and from C, the function will do nothing because there is no folder beneath C.

As an exercise, you could write a recursive function to accept a directory path, write out all of the files and sub-directories for that path, and call itself recursively for each path it contains--which (obviously) will print out all found files and directories in each sub-directory, etc.

One Key Point:

Recursive functions should always behave the same. If you need to do something special, like for example you need to print some dialog on the first call to your function, or you need to print something else when the function ends, write a containing function to call the recursive function.

For example, if you have "WalkAndLogAllDirectories()", which does what I mentioned above, and you need to do something special with it before it starts and after it ends, you should perhaps rename it to "DoWalkAndLogAllDirectories()", and create a new function called "WalkAndLogAllDirectories". The new function will write out your initial output, call "DoWalkAndLogAllDirectories()", and then write some closing output.

Hope that helps some.
 
The best way that helped me understand recursion is that the "Base" case is the "Stopping" case. Once you get to the base case, your stack unwinds and you end up with the result you were seeking.

BTW, recursion is terribly inefficient for most real-world duties for very large values of N. I wrote an algorithm to traverse directories and subdirectories recursively. After about 5 minutes the program crashed. I re-wrote it as a loop.
 
Buckus said:
BTW, recursion is terribly inefficient for most real-world duties for very large values of N. I wrote an algorithm to traverse directories and subdirectories recursively. After about 5 minutes the program crashed. I re-wrote it as a loop.
Click to expand...

Really?

I wrote a recursive function to walk a directory structure, log each directory and each file, and copy all files and directories (calling itself recursively for each directory it found) from the source to the target destination, and I've copied thousands of files and directories with it successfully (15k?).
 
Buckus said:
BTW, recursion is terribly inefficient for most real-world duties for very large values of N. I wrote an algorithm to traverse directories and subdirectories recursively. After about 5 minutes the program crashed. I re-wrote it as a loop.
Click to expand...
Walking directory trees is a trivial impact. What else was going on in your method/function? Still have the code?
 
Buckus said:
The best way that helped me understand recursion is that the "Base" case is the "Stopping" case. Once you get to the base case, your stack unwinds and you end up with the result you were seeking.
Click to expand...
Right. You need to know the stopping case and understand how to make the stopping case plus the next most complicated case work out. It's a little like proof by mathematical induction, really.

Buckus said:
BTW, recursion is terribly inefficient for most real-world duties for very large values of N. I wrote an algorithm to traverse directories and subdirectories recursively. After about 5 minutes the program crashed. I re-wrote it as a loop.
Click to expand...
How deep was your deepest directory? I'd expect such a procedure to be I/O bound, not held back by recursion. What in your code caused the crash? Was the problem that you were repeatedly following dot and dot-dot around, or that you found a similar loop because of symbolic links, or that you had too much on each frame of the program stack?
 
PTNL said:
Walking directory trees is a trivial impact. What else was going on in your method/function? Still have the code?
Click to expand...
In this case, I had thousands and thousands of directories and subdirectories (not sure of the exact number, I just know the root directories had thousands of subdirectories).
 
mikeblas said:
That closed-form solution doesn't teach us anything about recursion.
Click to expand...

mhmm of course not... which was sort of my point commenting on the comment about the efficiency of using recursion to generate fibonacci sequence numbers versus a loop
 
Usin a closed form formula teaches us nothing about the contrast between loops and recursion.
 
It's unlikely you had a path depth of several thousand though, especially if on windows which I know enforces a maximum path depth of 250-something characters. Even if you had a ton of nested directories each one letter long, the overhead in stack space is not going to be significant.

You must have had something else going on that was causing slowness.

Buckus said:
In this case, I had thousands and thousands of directories and subdirectories (not sure of the exact number, I just know the root directories had thousands of subdirectories).
Click to expand...
 
Whatsisname said:
the overhead in stack space is not going to be significant.
Click to expand...
Depends on what the program puts on the stack. Local variables count, and it can be tempting to declare large local char arrays to hold strings.

Windows doesn't enforce a path depth of 250 characters. Many applications do, but that's because of bugs in the application.
 
Whatsisname said:
It's unlikely you had a path depth of several thousand though, especially if on windows which I know enforces a maximum path depth of 250-something characters. Even if you had a ton of nested directories each one letter long, the overhead in stack space is not going to be significant.

You must have had something else going on that was causing slowness.
Click to expand...

No, it's absolutely possible, because it includes breadth, not just depth. Basically, the recursive code goes something like:

Function recursiveDirectorySearch(string root)
{
for every (directory) in (root) call recursiveDirectorySearch(directory)
}

So, if the first directory had, at level N+1, 500 directories, my stack now has 500 directories on it. Then, if each of those 500 directories has 500 directories...there are now 500^2 directories on the stack waiting to be executed.
 
Buckus said:
So, if the first directory had, at level N+1, 500 directories, my stack now has 500 directories on it. Then, if each of those 500 directories has 500 directories...there are now 500^2 directories on the stack waiting to be executed.
Click to expand...
You'd only have 500^2 directories on the stack if you had your 500 loop iterations and 500 recursive calls (each with 500 more loop iterations) all executing at the same time.

In reality, your directory variable is only assigned to one thing at a time, and you only have one active recursive call. Even if, for whatever reason, you had to load your whole subdirectory list onto the stack during each call, that's still only 1000 directories at once.
 
Breadth shouldn't be on the stack. If it is, you've done a bad job of implementing the algorithm. (You might have been coerced into doing a bad job of implementing the algorithm by your environment, but it's a bad job just the same.) Your function should be processing this node, and calling to process downward. There's no reason to have siblings on the stack.
 
Last edited:
If your path is only two levels deep, then you should only have two calls on the stack beyond the root.

You first call is on the root, which will then call on the first directory. Then it will recursively call on the first subdirectory. Then it will do its thing, then pop. Then it will be called on the second subdirectory. Then it will pop. Do that for all 500 subdirectories, then the stack pops again. Whether there are 2 or 2 million subdirectories in that first directory, your stack would just constantly push pop as the operation recurses.

The stack size with recursion should only scale with depth, unless, as mikeblas mentioned, you did a bad job of implementing your search. Perhaps it was implemented similarly to the naive implementation of the Fibonacci sequence as mentioned early in the thread.

Buckus said:
No, it's absolutely possible, because it includes breadth, not just depth. Basically, the recursive code goes something like:


Function recursiveDirectorySearch(string root)
{
for every (directory) in (root) call recursiveDirectorySearch(directory)
}

So, if the first directory had, at level N+1, 500 directories, my stack now has 500 directories on it. Then, if each of those 500 directories has 500 directories...there are now 500^2 directories on the stack waiting to be executed.
Click to expand...
 
You must log in or register to reply here.
Back
Top