Hello!

Algos

#The Noobs Guide To Solving Algorithm Problems

## To Understand Recursion Your Must First Understand Recursion

In this essay I'd like to focus more on insights and deep understanding rather than memorizing specific algorithms and tricks. 

And if there is one thing that lies at the heart of solving algorithm problems its recursion. Even problems that are solved iteratively have a recursive structure.

So let us consider our first problem . 

    Find the maximum element in an array

Now before you run off to write a for loop lets think about how to break it down recursively.

The questions you need to ask are:

####What is the smallest instance of the problem ?

The smallest instance of the problem is where the array contains a single element. This is called the base case.

#### How do we make the problem smaller ? Can we do it in terms of itself ?

We are trying to find the smallest element in the array. Say we remove the first element. Now we have a smaller sub problem which is the same as the problem we are trying to solve. 

Now how do we combine the two ? 

The maximum of the whole array is the max of the first element and the maximum of the rest of the array. So we simply call into the same function and the "recursion fairy" does the rest. 


    
    max_array(array):
	    if len(array)==1:
		    return array[0]
		return max(array[0],max_array(array[1:])) 

Notice here that we need keep track array[0] until the recursion completes. And we need to keep track of array[0] for each recursive call until we reach the end.  This kind of recursion thus needs extra space.

Such a process is called a recursive process.

## But wait why not a just a for loop ?

What if I told you that a for loop is also a kind of recursive call ?

Once you have a recursive solution one can explore how to make it iterative.

Let us try rewriting the above function in such a way that the final return statement is just a call to the same max_array function. Nothing else.

How would we do it ?

Let us think about "growing" a solution. Move from left to right and keep track of the maximum so far . 

After some thinking one might write

    max-iter(index,max_so_far,array):
	    if(index>=len(array)):
		    return max_so_far
		else:
		    max-iter(index+1,max(array[index],max_so_far,array)
	
	# To find max call it with
	max-iter(1,array[0],array)


This can then be translated to a for loop formulation as 
	
	max_val = array[0]
    for(index = 1; index < len(array); index++) {
		max_val = max(array[index],max_val)
	}

Each iteration basically calls in to the same function with an altered state. There is no need keep track of the current state. It can be discarded and we can directly jump into the recursive call with the new state. So one need not maintain a stack of the previous state.

Such a process is called an iterative process and is so common that all languages have constructs like `for` and `while` to make it easier.



## Another one

    Find the largest two elements in an array

#### What is the smallest instance of the problem ?

The smallest valid instance of the problem is an array with two elements.

The largest is the max of the two and the second largest is the min of the two.

### Can we solve it in terms of a recursive process ?

Lets try chipping off two elements and seeing if we get the same problem.

    largest_two(array):
	    
	    if(len(array)==2):
		    return(max(array[0],array[1]),min(array[0],array[1])

	(largest_rest,second_largest_rest) = largest_two(array[1:])
	
	if array[0] > largest_rest:
		return (array[0],largest_rest)
	if array[0] > second_largest_rest:
		return (largest_rest,array[0])
	else:
		return (largest_rest,second_largest_rest) 
	
		    

#### How about an iterative process? 

Starting with the smallest instance , two elements and then grow the solution one element at a time . 

    largest_two(array,index,largest_so_far,second_largests_so_far):
	    if(index>=len(array)):
		    return (largest_so_far,second_largest_so_far)
		 
		 if array[index] > largest_so_far:
			 return largest_two(array,index+1,array[index],largest_so_far)
		if array[index] > second_largest_so_far:
			return largest_two(array,index+1,largest_so_far,array[0])
		else:
			 return (array,index+1,largest_so_far,second_largest_so_far)

Now this can be easily rewritten to a for loop.