Tail Recursion

In my previous blog on recursion, we noted the comparison between iterative and recursive implementations. Now, if we want the memory consumption of  an iterative approach and the elegance of a recursive implementation, then I had mentioned that we would need to take a look at : Tail recursion! So, let’s start decoding this.


What is Tail Recursion ?

Tail call refers to an operation where we call a function say, g() and immediately return it’s return value as the return value of our function f(). In this case, we will not  need to preserve any of the state of the current code (state of g()) – since we are just about to throw it away and return.

Tail recursion is a form of recursion where the recursive call (call to same procedure f() itself) is the absolute last operation performed (called recursive tail call). Basically, meaning that there is nothing left to execute in the function after recursive calls – ie., the function returns the result of a recursive call.

The result of recursive call in this case can be passed directly for extra computation,  instead of waiting for it , which translates to no extra stack space. Normal recursive call, on the other hand, has a stack frame allocated, so that the compiler remembers where to get back to and to have the necessary variable values ready after recursive call is finished. This optimization is called – tail call optimization (TCO).

To write tail recursive version of the function, it means that we need to make sure recursive call is the absolute last operation in the function – there should not be any extra operations performed after the recursive call.


Let’s consider a very simple example to understand this concept.

Example

Consider a recursive function that returns the sum of ‘n’ positive numbers.

I .Recursive implementation

  • The recursive formula for sum of “n” numbers is given by: sum(n) = n+sum(n-1)
  • and sum is 1 when input is 1. (base case)

int sum(int n)

{

// Base condition for input = 1.

if(n==1) {

return 1;

}

// cases greater than 1.

else {

return n+sum(n-1); //This has extra operation of adding “n” to sum returned from recursive  function call

}

}

II. Implementing tail recursive version

  • To re-write sum function above in tail recursive form, all we have to do is :
    1. Identify the extra operation performed between return and recursive call . In this case addition of “n” to what is returned from recursive call.
    2. Modify and re-write the function to do this extra operation internally and then return, usually involves passing extra state variable called accumulation.
    3. Retain only recursive function call as the last operation in the method.

Now, let’s give tail recursive implementation a shot using the three steps outlined above.

  • In the recursive implementation above (under I),  we can see that there is an extra operation of adding output of recursive call to “n” at the end as highlighted in red.
  • For step 1 : The last line in the implementation can be split and written as :
  • y = sum(n-1);  
  • result = n+ y ;  //
  • return result ; 

For steps 2/3 : The new function version will take an extra argument which is an accumulation of current value. So, the extra operation to be performed is taken care of in the function call itself and not after return from recursive function call. Note : This style of passing control explicitly is called “Continuous Passing Style“. This makes sure that recursive call is also the last operation performed.

r2


Role of Compiler

Modern compilers support tail call elimination for tail recursive functions- an optimization called “TCO” (Tail Call optimization) as briefly mentioned above. TCO is the process by which a compiler can make a call to a function and take no additional stack space. The only case this would happens is if the last instruction executed in a function f() is a call to a function g(). Of course, in recursive case the call will be to itself f().

I have personally programmed in C and Python. GCC compiler (C compiler) offers TCO (Tail call optimizations).

Essentially, when we re-write the function in tail recursive form, the compiler optimization looks like below. It would be converted to a goto instead of recursive calls with stack allocation for it to remember the outcome of each recursive call to be used for the extra operation. This means that we  will not hit the stack over flow problem. Yay!

int tail_recursive_sum(int n, int accum=0) {
label:
    if (n == 1) return n+accum;
    accum += n--;
    goto label;
}

However, python implementation does not support TCO internally, which means it is expected that we judge the depth of recursion and re-write the iterative version, if we want to be safe with stack usage.

Generally, the need for recursive call optimization is dependent on the performance of your algorithm. If you have to implement a program that takes O(n) operations, it is not a good idea to use recursive version, while if it is O(logn) like tree implementations, we should be okay using the recursive version, we may not blow up stack.

Of course, I have shown a simple example here. There may be more complicated use cases. May be I will write about them soon in another blog. 😉

I want to keep the tidbit entries concise !


Conclusion

  • The function executes a little faster, since no stack pushes and pops are required
  • Function recursion depth is not a constraint any more, as there is no linear growth of stack usage with recursive calls.
  • We will not hit the stack overflow issue with this implementation.

So, if you are coding in C , you could implement a tail recursive way to get the benefit of compiler TCO, while for python use the iterative version! :). That’s all for today !

Check this for more details on this topic w.r.t C++ as mentioned by John in the comments below.  I will need to catch up on this as well. So, until next time,  keep decoding !

Recursive Functions

The  two pictures above form the essence of this blog. Essentially, we will look at what recursion is. It’s  a good idea to read about Functions and Stacks before going ahead.

In this write-up I plan to cover what recursion is , how you could write your own recursive function, things to be wary of while using recursive functions and of course a take on recursion versus iterative methods.


What is Recursion ?

Recursion refers to self-referencing. If a given problem can be solved for input “n”,  by representing the the solution for case “n” in terms of calls to the same function for cases other than “n”, it is recursive!

So in essence, recursive functions refer to functions that call themselves repeatedly until an exit condition is met. Note : If you forget an exit condition, the function will run forever eventually resulting in stack over flow !!

There are also recursive data types (structures that have an element of their own type, example linked list) that we will not be looking at today.

Writing your own recursive functions

One of the tricks to writing recursive function is to understand the pattern in the problem and creating a “recursive formula “or the “recursive action” you need to perform.

Let’s consider a really basic example. Say you need to write a function that will take an input “n” and return the (n)th odd number in the arithmetic series of odd numbers.

Now, let’s take a few input values “n” (call it the input Term) and the corresponding odd number f(n) (the Value we are looking for) in Fig (1) below under Block A. Looking at the table, we can identify a generic pattern that (n)th number is the previous value plus 2. So, we get a generic recursive formula : f(n) = f(n-1)+2 , essentially value (f(n)) for input term “n” is the previous value (i.e., f(n-1))plus 2.

We can use this recursive formula to write our recursive function for positive integer inputs, as shown in Fig(1) below under Block B.

recur.png
Fig(1). Recursion function and Recursive formula

A recursive function can be split into two blocks of execution:

  1. The Base case that is required in all recursive functions – for this defines the EXIT condition. We should know when to terminate the recursive call. There may be one or more base cases for our recursive function.
  2. Remaining part of the function shall contain recursive call to self and in some cases post processing is also required after the recursive call [example, in this case is “adding 2” operation after the recursive call]

Referring to Fig(1), for the base condition, we can take a trivial case as input. Let’s take n=1 case as the base or exit condition, the first odd number to be returned is 1.

For other cases, we can return expected value using the generic recursive formula we derived. Suppose your function is called oddNumber(n) instead of f(n), then the else part in Fig(1) Block B, shall be :

return oddNumber(n-1)+2;

This technique can be reversed to decipher what a recursive function does. If you are given a recursive method, all you have to do is look for the recursive formula in the function and start substituting valid value terms  “n” to be passed, starting with the base case values. The substitution method shall help you get an idea of what the function value represents, in the example,we can see that the values are all odd numbers and know that the function essentially returns nth odd number for given input n.

Other common examples of recursive functions-

  • Fibonacci series :

Expected value f(n)  : 1,1,2,3,5,8 and so on … 

Fibonacci value f(n) at nth position is a function of previous two values f(n-1) and f(n-2)

Recursive formula for Fibonacci is : f(n)=f(n-1)+f(n-2)

Base case here requires at least two values, so n=0 and n=1 case which return 1, shall be considered the exit condition when we write recursive function

  • GCD of two numbers : Greatest common divisor , highest common factor or the highest common divisor.

Greatest common Divisor is given by Euclid’s formula (the recursive formula to be used) : gcd(x,y) = gcd(x, x%y), recursive calls end when second term is zero ( or y is zero) , when y is zero, x is the greatest common divisor.

  • Same principle can be extended to  tree or graph traversals. Will be covering these in another blog.
  • These are the real use cases where we would prefer a recursive implementation 😉

Before we go to the next section, I have one question for you to solve.

What does the recursive method below do assuming input n is a power of 2 ? 🙂

Mail me the answer at decodergirlblog@gmail.com

// Note : Assume n is a power of 2 and log is base 2.

int func ( int n ){

if(n<=2) {

return 1;

}

else{

return func(n/2)*log(n);

}

} // end of function


Iterative or Recursive

Iterative refers to implementation using no self referential calls,implemented using loops.

From this blog entry , we know that the stack keeps growing as and when function calls are made. This holds good for recursive functions as well. A stack frame is allocated for each invocation of the recursive function. This means to say, there will be “n” stack frames allocated for an input “n”.  If we miss an exit condition or the base case,  there will be no end to the recursive calls, and because of the allocation of stack frames plus the fact that stack memory is limited resource, we will run out of stack space resulting in “stack overflow”. If you are a memory constrained system, you would be better off getting rid of recursive calls for solving trivial problems (Fibonacci, factorial etc), iterative will not allocate any extra memory, it will only update the loop variables in these cases. But, recursive functions offer cleaner, elegant solutions for problems involving “divide and conquer” technique (merge sort) and also the tree traversal problems.

We would need to know the depth of recursion we are aiming for and the stack memory available and the time constraints we need to work with before we think of recursive solutions. Essentially, know the constraints you have to work with. Recursive solutions take extra space and also extra time (due to usage of system stack) for solving the problem, but offer cleaner looking and/ elegant solutions.

Now, think of this :

What if we have a way to get the space consumption as in iterative case and also have the elegance of a recursive function : this is an optimization for recursive functions – called the tail recursion !

Will be writing a tidbit about this soon. Until then, keep decoding !

Demystifying Grace Hopper Celebration

People often ask me why is there a conference only for women; isn’t the day we have no such conference – the time we have truly achieved equality? I do agree with this thought. But, to me this conference is not a celebration “for minority” but a celebration of the fact, as to how far we have come from being termed the minority.

Grace Hopper Celebration is the world’s largest conference for women in computing that has grown from a mere 500 women who came together in 1994 to 15,000 plus participants this year. This truly highlights the progress we are making on closing the gap between men and women in the field of Computing. It is needless to say how motivating and inspiring it was to learn about some wonderful women in the field and the contributions they have been making.

I had the opportunity to represent Qualcomm and be part of this amazing conference for the second time. I was introduced to this conference by fellow engineer Molly Nicholas, with whom I had collaborated on the idea of designing a hardware called Qbadge in the year 2015 – added wireless connectivity to the Hardware – (what I do best, of course ! ;)) and also some new neo-pixel patterns to light up the badge (check video below).  This was one of the few times, I had designed something on a basic breadboard and tested (pic below). It’s awesome what you explore and do when you collaborate.

Qualcomm hosted a Hackathon event that utilized the Qbadge hardware again in 2016. I was excited to be part of this event, to meet and answer the questions from the participants – young women engineers chosen from across the United States. The idea was to have a useful social interaction, make it a learning experience for the girls by exposing them to low level programming. We had them edit the programs loaded on the badges, while they solved some hackathon clues.

screenshot_2015-07-13-17-32-29-2    screenshot_20170304-125705

Pic 1 : Arduino Trinket interfaced with Bluetooth HC -05 chip

Pic 2: Internals of QBadge

Video below : Shows how the badge flashes with the programmed neopixel patterns that can be activated by a command from an Android app sent over Bluetooth connection:

One of the feedback I had from the first time at the conference in 2015 was that more men should also participate in this conference. Q showed an increased participation from the previous year , from 50 participants to 130 that included a few men as well. At the booth, Qualcomm had an invisible museum- named invisible but truly impactful Augmented Reality display. This seemed in-line with Megan Smith’s opinion she shared with a quote during her key note : “Women have always been an equal part of the past. We just haven’t been a part of history” – Gloria Steinem. This is very much the premise for Grace Hopper Conference – to recognize and highlight the contributions that women are making as well.

In my opinion, it would be a  good idea for more men to be a part of this conference to not only learn about and appreciate the contributions made by women but also to gain awareness about how they could aid with the efforts to close the gender gap, by getting involved in discussions about the problems or challenges faced by women. There were a number of men who were not only present at the conference but also made presentations such as this talk by Astro Teller, Google X.

Moving on, the technical theme for the year 2016 included Internet of Things, Artificial Intelligence, Human Computer Interaction and Data Security. While various technical talks in all the above tracks, such as self driving cars, programming humanoids, connecting millions of devices – engaged me and were giving a glimpse of tomorrow, there were also talks about solving the connectivity problem that had my attention. With the world progressing towards Drones, Smart Vehicles and Devices, Internet of Things – an all connected paradigm, it’s hard to imagine that two thirds of the world still remains unconnected – has no access to basic internet. As an Engineer at Qualcomm Research, I am excited to be part of the team that is working on connecting the unconnected.

Working on a myriad of problems and finding solutions for the questions of today and tomorrow, is what makes engineering a challenging as well as an enjoyable task. The term engineer has no gender. I believe that building a future we envision, takes each one of us and the path to that is – coming together and looking beyond the gender!

Lastly, to give you a sneak peak of how women are getting ahead on closing the gender gap in the tech industry, the winner of ABIE award for Technical Leadership,2016: Anna Patterson tried a simple way using the “show of lights” from the mobile phone to represent the show of strength. (video below)

But, it was her words : “No matter what you are going through, there is always a lesson to be learned and light at the end of the tunnel. Make sure you are looking for the light”  – that resonated  with me as I witnessed the entire hall light up around me!

More importantly, this made me realize how each one of us can make a difference to the over all picture. This post is dedicated to all the women engineers out there. Thank you to each of you for doing your bit and inspiring me each day to keep going. Together – we got this ! 


Note : This post in response to the Day-04 prompt word : “inspiration” – created by thestemsquad on Instagram in the on-going month of ‘get to know women in STEM’ initiative.