This course will introduce you to Ruby, as well as teach you about classes, methods, variables, data structures, loops, enumerable methods, and finishing touches.

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!

Do more with

EXPERT OFFICE^{®} is a registered trademark of EXPERTS EXCHANGE^{®}

That being said there are some applications for which recursion is ideally suited. One common example is traversing a tree.

For a recursive function to work properly it needs two main components: (1) a logical loop and (2) a terminating case. Without a terminating case or a properly constructed terminating case you can run into endless recursion (which isn't truly endless because it doesn't take long for it to eat up all available memory and crash).

To answer your questions...

1. You can call any function from within any other function. In this case sum is calling itself with a new value. In your above case if n == 1 then the recursion stops and the function starts backing out of itself.

2. The machine running the code basically pushes a new instance of the function sum() onto the stack when it needs one. Once the function is complete it pops the item off the top of the stack until it gets back to the base call. Here's a quick illustration of how a recursive function would look on a stack:

sum(1)

sum(2) sum sum

sum(3) sum sum sum sum

sum(4) sum sum sum sum sum sum

sum(5) sum sum sum sum sum sum sum sum

It's crude but the idea is that each call pushes a copy of "sum" onto the stack until the terminating condition is reached. Once that happens it starts popping those instances off the stack until it unravels completely and returns to the base call.

3. I'm not sure what you mean by "normal procedure". You do have to be VERY careful when writing a recursive function taking (at least) the following things into account:

a. Can this be done (viably) using an iterative approach rather than a recursive approach? If the answer is yes, don't use recursion.

b. Is there a guaranteed terminating condition (i.e. one in which the recursive function is guaranteed not to call itself)?

c. What are the costs of implementing your code recursively? Recursion is memory hungry (and usually slower than an iterative approach) due to the above described stack calls.

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/

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 ...

the assignments performed for sum(100) are

```
sum(100) = (100 + sum(99))
sum(99) = (99 + sum(98))
sum(98) = (98 + sum(97))
....
sum(2) = (2 + sum(1))
sum(1) = (1)
```

if you put all together into one line

```
sum(100) = (100 + (99 + (98 + (97 + (..... + (2 + 1))))).....))
```

what obviously is the adding all numbers from 100 to 1 and is equivalent to the following loop

```
sum = 0
for n = 100 to n = 1
do
sum = sum + n
end do
n = n - 1
end for
```

from the above you see that all recursive algorithms could be alternatively solved by suitable loops. however, recursion might require much less code and therefore is more elegant. you can see this from another sample already mentioned by Russ the traversing of a tree.

assume a binary tree like the following:

```
F
/ \
D G
/ \ \
B E H
/ \ /
A C I
```

if you want to traverse it in alphabetical order you would start at F node go left until A, then print A, go back to B, print B, go right to C, print C, go back to C, go back to D, print D, go right to E, print E, and so on.

obviously the way depends on whether there are left or right child nodes, and the way back to parent nodes may go over two or more steps if you return from a right leaf node. if doing the traversion with a loop you have to memorize all parent nodes for any child node in order to be able to continue the traversion after visiting a right child leaf.

by using recursion, the traversion is much simpler since each node of the tree could be seen as the root node of a sub tree. hence the traversion of the F node actually is to perform traversion of the D node going back to F, print F, and then traverse the G node.

so you have a traverse function like

```
traverse (node n)
{
if n == nil return
traverse (n.left)
print(n.data)
traverse (n.right)
}
```

which would be called intially like

```
node root = tree.root // read F
traverse(root)
```

Sara

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

2. Since "dim sum (n: Int);" has already been processed by the compiler, everything needed for "n + sum(n - 1)" is already defined. The compiler only needs to know the prototype for sum(). It doesn't need to know the instructions contained within sum(). It needs to know the instructions to compile sum(), but not just to reference sum(). A reference only needs a matching prototype.

3. "Normal" procedure? There is no "normal" procedure. There are a couple methods of defining and structuring recursive functions so that they're almost guaranteed to give expected and correct results. But after 40+ years as a programmer, I can assert that many different developers have their own methods. (Some of them seem never to figure it out.)

As others have noted, basic iteration is the foundation of recursion. Attempt to write it as a straight iterative procedure first. If it comes out cleanly, then recursion isn't called for. If you find that you need to create new instances of variables for each pass through the loop, then that's a possible indication that recursion might be useful.

And when writing iteration, you might start by attempting to write it as straight in-line code first. If you find that you're simply coding the same statements with the same variables over and over, then that's a probable indication that iteration might be useful.

But a "normal" procedure is going to be the one that works for you once you're comfortable that recursion is clear

## Premium Content

You need an Expert Office subscription to comment.Start Free Trial