Recursion...help,tips,suggestions

hi there I need some serious help with recursions! i have read the tutorial on this site i am reading some info out of a book and i still find it hard to understand!

if you have any tip or suggestions on how you understand recursion can you pleas post here so i can look at it.. also if you know any links of good explanations i would like to look at the also!

thanks in advance!

Here is a demonstration of recursion.

The tutorial on this site for recursion is pretty good. You'll have to be more specific about what part you don't understand.
Have you writen a non-recursive function that you would like to convert to being recursive, or do you have a particular algorithm you want to implement? It's not as easy to understand it if you aren't actually trying to program it.

well basicly.. im very confused about all of recursion.. i dont know how to write or even understand it.. i dont know how to convert a recursive function to a non-recursive function.. im just reading everything i can.. i think maybe im suffereing a little bit of over burn at the moment..

i liked the link.. had me for a second but i understand it! lol

> if you have any tip or suggestions on how you understand recursion
Consider this dumb strlen function

Code:

---

int myStrlen ( const char *s ) {
  if ( *s == '\0' ) {
    return 0; /* trivial case */
  } else {
    /* a simplification of the problem */
    return 1 + myStrlen( s + 1 );
  }
}

---

In essence, recursion just re-uses the same code to work on a simplified version of the same problem. Eventually, you get to a point which is trivial to solve and that is when the recursion stops.

Another example is walking a tree, where each sub-tree is a tree in it's own right.

however i need to figure out how to problem solve with it! anyhelp would be greatly appreciated! here is a question im working on! my coding is wrong which ill show you if you could push me in the right direction and tell me if what im doing is rightish or wrongish that would be great! this Site has helped me so much! i hope one day to become a very regular and contributing member!
okay.. here goes nothing!

Question: One way to count the number of digits in a positive number is to use a recursive function -digits-. The number is passed as an argument to the function. The function returns the value 1 is the number is less than 10, otherwise it returns 1+the number of digits in the number when divided by 10. write the recursive function in C, then write a non-recursive version of the same function.

now.. im going to show you my attempt.. its not very good.. but its the best i could do lol.. the code isnt even working.. can you please exapline to me why etc.. im not looking for an answer im just looking for explinations if that makes any sense.. lol

Code:

---

int main(){
        int digits (/*i dont know how to give digit function a number for its argument*/){
                if (digits > 9 ){
                        return 1;
                }else{
                                return 1+(digits/10);/*not sure this is even close..but this is the recursive bit.. i think*/
                }
        }

---

thanks for all the help so far! its really helped!

It would maybe be best to look at it from more of a mathematical perspective. After all, recursion is rooted in mathematics, as is most of computer science.

I am not saying you need to start cranking out math problems, but once you understand the mathematical concepts, programming them becomes much simpler. A good book on data structures and algorithms is a must.

For example, the Fibonacci sequence.

Code:

---

#include <stdio.h>
#include <stdlib.h>

/* returns the n'th fibonacci number */
int fibonacci(int n);

int main(int argc, char **argv)
{
        int num;
        if (argc == 2) {
                num = atoi(argv[1]);
                printf("fibonacci(&#37;d) = %d\n",num,fibonacci(num));
        }
        return 0;
}

int fibonacci(int n)
{
        if (n == 0) {
                return 0;
        } else if (n == 1) {
                return 1;
        } else if (n > 1) {
                return fibonacci(n - 1) + fibonacci(n - 2);
        } else {
                printf("Must be postive integer\n");
                return -1;
        }
}

---

The Fibonacci sequence is a recursively defined as F(n) = F(n-1) + F(n-2) and the bascases are 0, if n == 0, and 1 if n == 1.

The Fibonacci sequence is a very famous problem, and usually used to introduce recursion to computer science students.

A perfect example is browsing for files:

Code:

---

void some_func(char* path)
{
// Check for sub-folders; and if found then do:
some_func(new_sub_folder);
// Now do something with all those files
}

---

And so on. Each time it finds a sub-folder, it calls itself to investiate that folder. Recursion, plain and simple. I have a snippet of code, though it may be a little tough to understand.

maybe its this question thats trowing me off!

How the heck would i make recursive code outta that question?
i know how to make it non recursive.. thats easly done! but Recursive.. dose anyone have any idea how it could be done?

please explain:)

That doesn't seem like a good code to use recursion on at all.

do you mean how to convert a recursive to non-recursive function?

EDIT: Never looked at the previous code of your. And yes. The question donst say any where what need to be recursive. I thnk thats not a good example for a recursive function.

ssharish

I need to know how to make that question into a recursive function.
I also need to know.. but know how to make it a non-recursive function.

Your sample isn't recursive at all, so it's basically a non-recursive function. A recursive function is one that calls itself one or more times.
But how to make it recursive? You don't just make something recursive. Either the task you want to do requires a recursive approach or it does not. Or so it is usually.
The sample you have is just an example of a non-recursive task. I don't know how to turn it into a recursive function. And even if I did, it would just be a waste.

yea.. thats what i think.. and thats probably why its giving me headach!!! its in an old exam im studying from.. crazy! i wounder if its a mistake?

Probably. This code was not made to be recursive. I think you should ignore the make-recursive part. If you want to train recursive, you can try to find a task that requires it and write code for it (for example, a function that finds all *.exe files on drive C).
But anyway, it's up to you.

whicked.. yea i think your right! thanks Elysia im defiantly gonna get into coding something else that is more clearly adaptable to a recursive function! thanks or your help people!

If you want a recursive function to calculate the number of digits in a number:

Code:

---

int digits(unsigned int n)
{
    // First, the base case. Any number less than 10 is always
    // going to have 1 digit exactly. (Even 0 has 1 digit)
    if (n < 10)
        return 1;
    // if the number if 10 or greater then it has more digits.
    // Dividing by 10 will remove the rightmost digit which
    // we then add 1 to the result  for
    else
        return digits(n/10) + 1;
}

---

Always start with the base case and make that work. Then write the recursive case.