Week 7 --Recursion

 Writing recursion is quite challenging for beginners like myself. For many time when I doing lab question, my code doesn't work, I don't know why; and sometimes my code works and I don't know why. I read a very interesting definition of recursion once. It states "The main point of it is that it is defined in terms of itself: "Recursion: ... for more information, see Recursion.""

First question: what kind of problem can be well solved by using recursion ? General speaking, problems are defined in term of themselves. This abstract answer tells me nothing. We need a more solid example. A good example I've find is factorial function. 5! = 5*4*3*2*1 = 5*(4*3*2*1) = 5*4! = 5*4*(3*2*1)= 5*4*3!. When n is arbitrarily large,  n! = n*(n - 1)! still holds for all n! 

Second question: how do we solve it? first, we need a base case, where it's so simple that can be solved without using recursion. Why is it so important ? Because it's a haling condition, tells the function when to stop, (stop once reaches base condition). 

for example, 

what would it return ? If n = 3, then our recursion trace would be 

3 * factorial(3-1)---> 3 * 2 * factorial(2-1)---> 3* 2 * 1 * factorial(1-1)--> 3*2*1*0*factorial(0-1)

we have meet an absurd situation. first if n is NOT restricted to natural numbers, then this would go negative infinite and never halts. but if we restricted n to natural numbers, there would be no such
factorial(0-1) exists at all !. Either case, we can't have our promising result. Therefore, the base is required !

We want to define the base so that this absurd situation would happened to us and factorial(3) gives us the reasonable answer (which is 6). 

We first, need to thinking about what happen if the input n is negative ? It should give us error. If n is give as 0 it should give us 1.

therefore, we need have
if n < 0, returns
 if  0 <=n <= 1, return 1, 

Here is how we think of defining a recursion function