# CS1101S Reflection 03C Recursive vs Iterative Processess 25675914

// Factorial function

function fact(n) {
    return (n === 1) ? 1 : n * fact(n - 1);
}

// 1: is the above recursive or iterative?
//Names: Changjun, Jotham, Weilin
//recursive function and a recursive process because there are deferred operations

// 2. How many steps does it take to compute the result of this function 
// application?
fact(5); 
//5 * fact(4)
//5 * (4 * fact(3))
//5 * (4 * (3 * fact(2)))
//5 * (4 * (3 * (2 * fact(1)))
//5 * (4 * (3 * (2 * 1)))
//5 * (4 * (3 * 2))
//5 * (4 * 6)
//5 * 24
//120
//Total: 10 steps? 2n steps for fact(n)?
//Names: Chen Lyuting,Bao bin, Ananya Shahi



// 3. How much space is required to compute the result
// of fact(5); ?
//Names: Silas, Cheng Da Lee, Joan Sim
//4
// evaluating n===1 gives false since n is 5
//5 * fact(4)
//evaluating n===1 gives false since n is 4
//5 * 4 * fact(3)
//..this continues until evaluating n===1 gives true
//5 * 4 * 3 * 2 * 1
//There are 4 steps of calculation


/// 4. Write an iterative version of fact
function fact_iter(n, counter, product){
    return counter > n ? product 
                       : fact_iter(n, counter + 1, product * counter);


function fact(n) {
    return fact_iter(n, 1, 1);
}

fact_iter(5, 1, 1);

function f(n) {
    return n === 0 ? n : f(n - 1) + f(n - 2) + f(n - 3);
}

//Names: Gregory,Guanzhou, Yi Teng

``



// 5 How many steps does it take to compute the iterative function?
// Use the substitution model!
//function factorial(n) { return iter(1, 1, n); } function iter(product, counter, n) { return counter > n ? product : iter(counter * product, counter + 1, n); }
//n because we plus 1 n times for counter>n, and at the same time Counter*product
//Therefore for 5!, we would get 10 steps
//Names: Marcus, Marcus, Wei Jie

fact(5);
fact_iter(5, 1, 1);
fact_iter(5, 2, 1);
fact_iter(5, 3, 2);
fact_iter(5, 4, 6);
fact_iter(5, 5, 24);
fact_iter(5, 6, 120);
120;




// 6. How much space is required to compute
// the result of your iterative function when
// applied to the number 5? 
// Count the number of deferred operaitons
//Quy Duc, Han Wei, alvin
// The amount of space that is required is constant, and the value is 3, given that there are 3 parameters.
// No deferred operations since it is a iterative function.


// 7. Consider the fibonacci function: is this
// function giving rise to a recursive or iterative
// process?

/*Marcus Goh, Ng Jing Xue



Recursive
There are deferred operations. eg fib(11) --> fib(10) + fib(9); need to evaluate both fib(10) and fib(9) before
we can return the result of fib(11) 

*/

fib(10)
(fib(9) + fib(8))
(fib(9) + fib(8)) + fib(8))
fib(8) + fib(7) + fib(8) + fib(8)
.
.
.
.
.
.
.
.

n stuff + n hanging stuff

function fib(n) {
    return n <= 1 
        ? n 
        : fib(n - 1) + fib(n - 2);
}

fib(11);

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + fib(3)
(((fib(2) + fib(1))) + fib(2)) + fib(3))



// 8. fib_iter: how many steps does this take?
function f(n, k, x, y) {
    return (k > n) 
        ? y
        : f(n, k + 1, y, x + y);
}
function fib_iter(n) {
    return n < 2 ? n : f(n, 2, 0, 1);
}

fib_iter(11);
//Zhang Tongjun, Tan Wen Cong
// 12 (or 24 steps if a step is defined to be less than a statement)
// one statement in fib_iter() and 11 in f(), base case when f(11, 12, 55, 89)
/* 
"fib_iter(11);"
"f(11, 2, 0, 1);"
"f(11, 3, 1, 1);"
"f(11, 4, 1, 2);"
"f(11, 5, 2, 3);"
"f(11, 6, 3, 5);"
"f(11, 7, 5, 8);"
"f(11, 8, 8, 13);"
"f(11, 9, 13, 21);"
"f(11, 10, 21, 34);"
"f(11, 11, 34, 55);"
"f(11, 12, 55, 89);"
 */


// 9. How much space is required to compute fib_iter(5)?
fib_iter(5); // Count the number of deferred operations.
//0 deferred operation. Constant space (independent of n).
//Zhizhou, Sheryl