1.
Introduction
2.
What is Recursion?
3.
What is a Recursive Function?
4.
Rules of Writing Recursion
4.1.
Syntax
4.2.
Example
4.3.
Output
5.
6.
7.
7.1.
What is a base condition in recursion?
7.2.
Why recursion is slow in solving problems?
7.3.
What is the difference between recursion and iteration?
7.4.
Why recursion takes more memory?
7.5.
Why recursion is required?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Recursion in Carbon

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Have you ever thought about how we solve complex problems by breaking them into smaller blocks of code using recursion? How Recursion helps in reducing the time in writing code?

In this article, we will discuss about recursion in Carbon language. We will see Fibonacci series using recursion. We will also learn about the advantages and disadvantages of recursion while using it. Moving forward, letâ€™s first understand what exactly recursion is.

What is Recursion?

A complex problem can be solved easily when it breaks down into smaller sub-problems. Recursion allows breaking problems into smaller sub-problems, which are solved using recursive calls. In recursion, a function calls itself till the base condition is met for solving the problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

What is a Recursive Function?

A function that calls itself until the program gets the required result is called a recursive function. Letâ€™s understand the rules for writing code using recursion.

Rules of Writing Recursion

1. In recursion, a function must call itself to make recursive calls.
2. Recursion must have a base condition in order to finish the execution of a program.
3. Using recursion, the recursive calls must change their state and move toward the base condition in order to solve the problem.

Syntax

``````fn recursiveFunction()              â€”------ Recursive function
{
BaseCase;                           â€”------ Base Condition
recursiveFunction();             â€”------ Recursive call
}

fn Main() -> i32
{
recursiveFunction();                     -â€”------ Function call
}``````

Letâ€™s understand recursion with the help of an example of Fibonacci series. This series is made by adding two previous numbers. The first and the second numbers are fixed, and they are 0 and 1.

Explanation

Letâ€™s suppose we want to print the 10th number of the Fibonacci series. In this program, recursive calls will be made until the value becomes 0 or 1. If the number becomes 0 or 1, then it will be returned otherwise, recursive calls for (n-1) and (n-2) will be made.

Example

``````package sample api;

fn Fibo(n: i32) -> i32 {
if(n==0) {
return 0;
}
if(n==1) {
return 1;
}
return Fibo(n-1) + Fibo(n-2);
}
fn Main() -> i32 {
Print("The 10th term in Fibonacci series is: {0}", Fibo(10));
return 0;
}``````

Output

• Recursion reduces time in writing code as it makes recursive calls that allow using the same code.
• In recursion, we only have to make a base case and a recursive case to solve the problem, which is better than making iterations using loops.
• Recursion solves the problem in a tree-like structure, which is easily understood.

• Recursion requires a large space in memory in order to make recursive calls.
• In recursion, the execution speed reduces due to recursive calls.
• In recursion, we must take care of a valid base condition otherwise, the function will execute infinitely, and it will return nothing.
• Sometimes it is really difficult to trace recursive calls in recursion.

Must Read Recursion in Data Structure

What is a base condition in recursion?

The base condition is the stopping condition of recursive calls. Base condition is necessary for recursion as it allows the program not to execute infinitely.

Why recursion is slow in solving problems?

Recursion is slow because it takes time in storing all the recursive calls in a stack and then pop them out according to the call order.

What is the difference between recursion and iteration?

Recursion code is smaller than iterative code, but recursive calls take time to solve problems and are also not easily understood as compared to iterative code.

Why recursion takes more memory?

Recursion takes more memory because of recursive calls, with each recursive call, the function is added to the stack, and the values will stay there until all the calls are not finished.

Why recursion is required?

Recursion helps in breaking complex problems into smaller sub-problems which makes them easy to read and understand than an iterative solution.

Conclusion

In this article, we have understood recursion in the Carbon language. We have seen rules for writing recursion code while programming. We have made a code of the Fibonacci series using recursion in Carbon language. We have discussed the advantages and disadvantages of using recursion. If you want to read more about recursion and Carbon language, then you can refer to the below articles.

Also check out - Rod Cutting Problem

I hope this article helped you understand recursion in Carbon. If you want to read more articles, then you can visit our platform Coding Ninjas Studio. You can also prepare for tech interviews and tech exams through our platform. Coding Ninjas provides company-wise preparation guides which will help you in enhancing your knowledge. Our platform also provides topic-wise coding questions so you can practice those questions and get placed in good companies.

Happy Coding!

Live masterclass