Week 7: Recursion, how we love thee.

Week 7: recursion 

Recursion is hard to completely understand mainly because when programming recursively, you need to understand exactly what your program needs to originally do then call it within itself. Also you need to ensure your program won’t run an infinite amount of times, making the depth of recursion to large, and it not working at all. 

How I have been programing before took special cases in if statements however in recursion, one way to adapt from previous knowledge is by using the idea of these ‘special cases in if statements or possibly in while loops, but making them into a base case from your initial function then calling those base cases recursively in regards to your arguments. 

This is best explained by an example: 

the Fibonacci sequence of numbers can be expressed recursively as so: 

def fib(n: num)-> int: 

if n == 1: 

return 0          (THESE ARE YOUR BASE CASES) 

if n == 2: 

return 1 

# now you have two initial numbers and for all other cases you will want to get the fib sequence for n minus your base case values for n 

return fib(n - 2) + fib(n - 1) 

looking at this code you may wonder how does this work?

fib(3) 

will process it from the return statement then call then call what the values of 

fib(3 - 2) + fib(3 - 1) 

fib(1) + fib(2) 

0 + 1 

1 will be returned 

now fib(3) == 1 

say you want to call fib(4) 

fib(4-2) + fib(4-1) 

fib(2) + fib(3)  ------> (fib 3 is then called recursively giving the second value of 1)

1 + 1 

the return int will be 2 

say you want to call fib(5) 

fib(5 - 2) + fib(5 - 1)   

fib(3) + fib(4)   ------>   (value fib(3) and fib(4) are already within your program)

1 + 2 

the return int will be 3 

and so on, recursive works well as the function is actually recursively keeping track of each value needed instead of you programing the fib sequence and giving it the value. Essentially being the best approach to program the Fibonacci sequence 

This is a simple example, however once having an idea of approaching it as: 

1. make a base case of what you want to be accomplished with your program
2. then if a special case is called you will call the function once again