Questions on recursion

Question

so I have a few questions on recursions. I am in a class and I am reviewing my notes and text and getting a little confused:

1) Am I getting this correct? Iterators and recursion seem so similar.

Recursion = a function that refers to itself and has a base case to get to the end of the problem.

Iterator: Using ++ or -- to go through all the data to get a piece of information.

2) What is recursive descent ? Is it getting closer to the base case? Then what is recursive ascent?

3) We are given this sample of recursion and it is confusing me:

Product of Positive Integer from 1 to n
Denoted by n! => n! = 1.2.3....(n-2).(n-1).n
0! = 1 , 5! = 1.2.3.4.5 = 120, 6! = 5! . 6 = 720
n! = n . ( n – 1 )!
Definition
– If n = 0 then n! = 1
– If n > 0, then n! = n. (n-1) !

Why is there an exclamation point after (n-1)? What are these dots, like n.(n-1)?

Answer 1

Recursion and iteration are not the same. You can iterate without recursion, and recursion means no iteration.

Let's leave recursive descent for now. That has to do with parsers.

The example is the mathematical operation of taking a factorial. The exclamation point means "factorial". The dot means multiplication.

Remember?

0! = 1
1! = 1
2! = 2*1
3! = 3*2*1 = 3*2!
4! = 4*3*2*1 = 4*3!

and so on.

This is a classic problem to illustrate recursion to undergrads seeing it for the first time:

function factorial_recursion(n) {
    if (n <= 1) {
        return 1;
    } else {
        return n*factorial(n-1);
    }
}

You can write the same thing without recursion by iterating:

function factorial_iter(n) {
    var value = 1;
    if (n > 1) {
        for (i = 1; i <= n; ++i) {
            value *= i;
        }
    }
    return value;
}

Answer 2

Well the dots are multiplication. It is confusing to use dots, but we know 5! = 1*2*3*4*5 so the dots must be multiplication. Also, the ! is the symbol to denote factorial. 5! = 5 * 4!

Answer 3

1. Yes, iteration and recursion are somehow similar, and it is known that any recursive solution has an equivalent iterative solution and vice versa. However, many problems are much simpler to solve in one of these approaches rather than in the other. The factorial example is easily solvable in both approaches. Whenever you see how a problem can be reduced to one or more occurrences of the same problem on smaller magnitudes, you can easily proceed with a recursive solution.

2. I suppose that recursive descent is diving into deeper levels of the recursion, while ascent is the opposite: returning from a call and getting closer to the top level call.

3. The dots stand for multiplication.