Any computer scientists out there?

[CyberNerd]

Hi all.

I'm current struggling with a concept that I hope you could help with.

I'm learning about recursion - calling a function from within the same function. I can see that this produces cleaner code vs iteration inside a function but I'm struggling to see the advantage.

 

Presumably recursion uses more memory than iteration as it has to work backwards through values in the stack. It certainly seems more complicated (to me at least) than iteration. So what is the advantage of this method? Is it faster? If so why?

[ConradJones]

recursion is dangerous as well as you can exhaust the stack very quickly. you need to ensure that you have a conditional statement which ensures that it stops recursing when the condition is met otherwise not only will your program loop it will overflow the stack quickly.

 

consider the following searching a folder for a specific file, it uses recursion to search sub folders and iteration to search the current folder (not sure it works 100% was bored waiting for centos to install)

 

entry find_file(string folder_name, string wanted) 
{
   entry = get_first_entry(folder_name);
   while (entry != null) 
   {
       if (entry is folder)
       {
           entry2 = find_file(folder_name + "\\" + entry.name);
           if (entry2 != null)
               return entry2;
       }
       else if (entry is file)
      {
           if (entry.name == wanted)
      }
      entry = get_next_entry(folder_name, entry);
   }
   return null;
}

[Chris_Cook]

It depends on your data structure and your algorithm. The performance differences on a simple array will be minimal. Then you would want to use whatever makes the code most obvious to the reader, at least in the initial version. Once you have it working, you would use a debugger to find the slow bits and just improve them.

 

When you start using linked lists and tree structures then recursion makes more sense. There are some other mathematical functions where it is also useful such as working out the factorial of a number.

 

In a linked list, or tree, each object points to the next one or more objects. This next bit is from wikipedia:

 

struct node
{
 int data;           // some integer data
 struct node *next;  // pointer to another struct node
};

 

Because the struct node data structure is defined recursively, procedures that operate on it can be implemented naturally as recursive procedures. The list_print procedure defined below walks down the list until the list is empty (i.e., the list pointer has a value of NULL). For each node it prints the data element (an integer). In the C implementation, the list remains unchanged by the list_print procedure.

 

void list_print(struct node *list)
{
   if (list != NULL)               // base case
   {
      printf ("%d ", list->data);  // print integer data followed by a space
      list_print (list->next);     // recursive call on the next node
   }
}

 

Performing the above on a linked list with iteration would be slow, and you would probably have some similar code hidden somewhere anyway. Worst case, you might end up recursively going through the list each time you try and print an object. That would be relatively inefficient, see the next code block and imagine calling that in a 'for each' statement for each element in the list/array. Its important to understand the data structures your working on.

 

int list_index(struct node *list, int i)
{
   if (list != NULL)               // base case
   {
      if (i == 0) {
        return (list->data); 
      }
      return list_index(list->next, i - 1);     // recursive call on the next node
   }
}

int list_length(struct node *list, int i = 0)
{
   if (list != NULL)               // base case
   {
      return list_length(list->next, i + 1);     // recursive call on the next node
   } else {
      return i;
   }
}

for (int c = list_length(list, 0); 0; c ++) {
  printf("%d ", list_index(list, c));
}

Edited May 5, 2013 by Chris_Cook
fixed some errors in the code.

[CyberNerd]

Awesome answers. Thanks.

[Sam_Brown]

Try this thread...

 

http://www.edugeek.net/forums/coding/112728-any-computer-scientists-out-there.html

[jinnantonnixx]

Recursion is useful for deleting sub-objects (folders, keys, etc) within a branch.

 

In this post, I wrote a bit of code that uses recursion to delete a key branch. If the branch has sub-keys, it calls itself for each sub-key and so on.

 

http://www.edugeek.net/forums/windows-7/78733-windows-7-user-profile-failed-error-again.html#post700415

 

Sub DeleteKey (thisKey)
'delete all subkeys
objReg.EnumKey HKEY_LOCAL_MACHINE, thisKey, arrSubKeys
If IsArray (arrSubKeys) Then
	For Each strSubKey In arrSubKeys
		'recursively delete the key
		DeleteKey (thisKey & "\" & strSubKey)
	Next
End If

'delete the registry key
objReg.DeleteKey  HKEY_LOCAL_MACHINE,thisKey
End sub

[dhicks]

Presumably recursion uses more memory than iteration as it has to work backwards through values in the stack.

 

In practice, modern compilers / interpreters have facilities to improve the speed / memory footprint of recursive functions - tail recursion and so on.

 

So what is the advantage of this method? Is it faster? If so why?

 

A single function call can be assigned to a parallel process, which can then be ran on a separate core / processor / whatever, so recursive functions tend to make for more easily parellel-isble functions. Probably not noticeable at the learning stage, but good when you get to the Big Data end of things and want your processing spread over as many compute nodes as are available.

[box_l]

@ sam_brown.

 

I see what you did there..