condor888

asked on

# how to understand recursion

I’ve been always having trouble to understand recursion. I know how to write some simple ones though.

Take this sum calculation Scala program for example. Please don’t answer this question based on the Scala specific implementation. I’d like to have a generic understanding on recursion.

1. It is calling sum(n-1) inside sum(n). Are they (sum(n) and sum(n-1)) using different instance of the same function?

2. How can the compiler understand this function when it is calling itself (sort of unfinished based on my view)?

3. What is the normal procedure of writing recursive functions (design recursive algorithms)?

Thank you!

Take this sum calculation Scala program for example. Please don’t answer this question based on the Scala specific implementation. I’d like to have a generic understanding on recursion.

1. It is calling sum(n-1) inside sum(n). Are they (sum(n) and sum(n-1)) using different instance of the same function?

2. How can the compiler understand this function when it is calling itself (sort of unfinished based on my view)?

3. What is the normal procedure of writing recursive functions (design recursive algorithms)?

Thank you!

SOLUTION

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

What Russ ^^^ said. The first most important thing is to know how to end it. What is the 'terminating condition'.

This is a related question, in which I posted comments and a helpful link.

ASKER

@Russ Suter, thanks for your answer, however, I didn't quite understand why you draw your illustration in a triangle shape. Could you please explain a little bit?

Also, since all recursion can be written in a iterative approach, how can I determine in which case it is viable to use recursion?

Also, since all recursion can be written in a iterative approach, how can I determine in which case it is viable to use recursion?

Look for the iterative approach. Recursion is often the easy way out but it comes at a cost of speed and memory resources.

The triangle was to illustrate how the function gets pushed onto the stack. Each column represents the next stack call. The recursive function sum(5) gets called which calls sum(4) and so on. When it reaches sum(1) then the terminating condition is met and the function is no longer called so the machine starts popping items off the stack.

These videos might be helpful.

https://www.youtube.com/watch?v=Mv9NEXX1VHc

https://www.youtube.com/watch?v=7t_pTlH9HwA

This article also does a fairly good job of explaining the basics using 3 of the most classic examples of recursion.

https://sleeplessafternoon.wordpress.com/2013/03/26/examples-of-recursion-the-good-the-bad-and-the-silly/

The triangle was to illustrate how the function gets pushed onto the stack. Each column represents the next stack call. The recursive function sum(5) gets called which calls sum(4) and so on. When it reaches sum(1) then the terminating condition is met and the function is no longer called so the machine starts popping items off the stack.

These videos might be helpful.

https://www.youtube.com/watch?v=Mv9NEXX1VHc

https://www.youtube.com/watch?v=7t_pTlH9HwA

This article also does a fairly good job of explaining the basics using 3 of the most classic examples of recursion.

https://sleeplessafternoon.wordpress.com/2013/03/26/examples-of-recursion-the-good-the-bad-and-the-silly/

Hi condor,

simple definition for recursive function for you ... here you go ...

A recursive function is a function that calls itself during its execution. This enables the function to repeat itself several times, outputting the result and the end of each iteration. Below is an example of a recursive function.

Enjoy learning ...

simple definition for recursive function for you ... here you go ...

A recursive function is a function that calls itself during its execution. This enables the function to repeat itself several times, outputting the result and the end of each iteration. Below is an example of a recursive function.

Enjoy learning ...

ASKER CERTIFIED SOLUTION

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Let me offer a non-computer-related example of recursion. English teachers often tell us not to define a word in terms of itself, but I submit that there are exceptions. Two of these exceptions are "ancestor" and "descendant." If you ask someone who his ancestors are, he is likely to say something like, "My parents, my grandparents, my great-grandparents, and so on." The "and so on" is inexact, but the only alternative is to continue listing "greats" back to the beginning of time. A more precise definition uses recursion: "My ancestors are my mother, my father, and their ancestors." Notice that there's a tree involved here, just as there is in the computer-related examples given above.

If you really want to understand the entire concept of recursion, read _Gödel, Escher, Bach: An Eternal Golden Braid_ by Douglas Hofstadter.

If you really want to understand the entire concept of recursion, read _Gödel, Escher, Bach: An Eternal Golden Braid_ by Douglas Hofstadter.

ASKER

@GuruJava, I am sorry but I didn't see your example.

ASKER

@historychef, interesting!

That's an interesting book. It's been a long time since I read it though.

SOLUTION

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.