If we can somehow reduce this memory usage then the code will not crash. Today’s compilers are very intelligent, if it sees that additional memory usage is not needed, it generates optimized machine code in a way that minimizes memory usage. We will use that intelligence.
In the previous code we had to save the old parameters on the stack because they will be useful on return. Can we write the code in such a way that the old parameter is no longer needed after return? This is where the tail-call idea comes in handy. If we write the code in such a way that no further work is required after the recursive function call, then n on the stack
Its values will not need to be saved.
Now instead of calculating the result every time after the recursive call ends, we calculate a partial result and send it as a parameter. At the very end we will get the result in that parameter.
This is a tail recursion, because no further work is done after the recursive function call on the last line. When this code is compiled, the compiler will see that there is no need to save old values using the stack. So this code will take as much memory as using a normal loop!
Any modern language compiler can do this optimization. If you are using C/C++ then before running the program you should check if -O2 compiler optimization is turned on or if not turn it on first, the code editor you are using will have the option to turn it on. Or you can compile directly from the terminal using the -O2 option. Search how to do it on Google. (Jazz machines usually have this optimization turned on in programming contests)
Now run fact_optimized(1000000) and see it gives nice output.
This is tail-call optimization of recursion.
The following code sums all the numbers in an array:
This code recursively sums the previous numbers and adds them to the current number. Your task will be to use tail-call recursion so that no further calculations are required after the recursive function is called.
The Fibonacci series is a series in which each number is the sum of the previous two numbers in the series. The first two numbers in the series are 0 and 1 and the first few numbers in the series are 0,1,1,2,3,5,8,13,21….
. This can be expressed with the following function:
Writing a recursive function normally would not be tail-call recursion because it would first return the value of fib(n–1) and return to fib(n–2). Your task is to write a tail-call recursion to find the nth Fibonacci.
Traveloka and I dabble in software engineering
Not an algorithm tutorial today, but a light talk about my joining Traveloka and doing my first serious software engineering.
The last year and a half was a transition period for me, before I understood contests as programming, before I worked at HackerRank, there were ten years of work with contests, and sometimes I used to dabble a little bit in Ruby on Rails. When I realized that while working at home, the roots were growing, I realized that it was time to change my job, I went to a company called Traveloka.com in Singapore.
I’m sure most of you haven’t heard the name of the company, I haven’t even heard it before the interview, I applied on Linkedin a lot! After getting the job offer, I found out that they are one of the few unicorn startups in Southeast Asia, unicorn companies are those whose valuation is above 1 billion dollars. Other unicorn tech startups in Asia include grab, go-zek, lazada, sea (shopee, garena) etc. Having seen the profile of the company, it was not difficult to decide, I joined as a back-end engineer.
Traveloka’s main office is in Indonesia, they opened a new office in Singapore because there is no better place in Asia than Singapore to attract good engineers from all over the world. I am the first Bangladeshi engineer in this company, after a few months another Bangladeshi Ahmed Fayyaz joined.
Traveloka’s core products are flights and hotels. But today’s trend is to create apps that can be used to do thousands of things. With Traveloka, you can buy movie tickets, zoo or theme park tickets, mobile top-up, rent a car, order food, pay electricity bills, I don’t even know what else you can do. But most of the products can only be used from Indonesia, launching the app from outside will show few features.
Once upon a time, Traveloka thought that many people in Indonesia did not have credit or debit cards, making it difficult for them to shop online. Then they came up with a new project called “cardless credit”. Very simple idea, the user will apply for a loan through the app, upload some useful documents, verify the documents and according to the profile, they will be given some money loan or credit.
They can spend that money to buy any product from Traveloka. Later the money can be paid in installments through bank transfer. When you hear about the loan thing, many thoughts work, usually taking a loan from the bank is very time consuming and troublesome. Traveloka has decided that the loan will be given within 1 hour of applying, most of the users will get the loan within 10-15 minutes, they will not go to any trouble like traditional banks or loan companies. Later the name of the project was changed to “PayLater”.
So it takes a lot of people to make a product like this. The product manager needs to fix the main requirements of the product, the legal team needs because there are some license issues regarding giving and receiving money, the work of the risk team is to check what kind of people are the risks of giving loans, the work of the finance team is to manage the money accounts, the work of the customer operation team is to document. Validated, marketing teams are there to run campaigns in different ways.
And of course the engineering team will be needed, otherwise who will do the real work? The project may sound small, but there are many complexities involved, especially where money is involved and a small mistake can cause a lot of damage. Having good engineers alone is not enough for the success of a software, which is why many startups don’t go far even with good ideas.
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
You must Join our Facebook Group and Subscribe YouTube Channel