Recursion in Carbon

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

Advantages of Recursion

• 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.

Disadvantages of Recursion

• 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

Frequently Asked Questions

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.

• Recursion
• How to Run Carbon Code 
• Variables in Carbon

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!