What is Recursion
Recursion is a programming technique where a function calls itself in order to solve a problem.
The problem is broken down into smaller, more manageable sub-problems of the same type.
This process continues until the problem can be solved directly, which is known as the base case.
Once the base case is reached, the function stops calling itself and the results of the sub-problems are combined to produce the final solution.
Key Concepts of Recursion:
Base Case
Recursive Case
Stack Memory
Visualizing Recursion with Fibonacci Numbers
I have a function called fib(4)
. When I call it, it returns the value 3. Letβs break it down step by step.
Step 1: Draw the Recursion Tree
To understand the recursion, we can draw a recursion tree for the Fibonacci number. When the function runs, it calls the previous two values and continues this process until the base case is reached. According to the formula, we know that fib(n) = fib(n-1) + fib(n-2)
. Here is the tree:
Step 2: Reach the Base Case
Step 3: Return the Values from the Base to the Top
So far, we have a clear understanding of how the recursion tree works and how the values are returned. If we consider how a stack works, take a look at this:
It starts from the main call and follows the green line. When a call begins, it directly goes to the bottom, then the function executes from the bottom up.
code
java
public class Fibo{
public static void main(String[] args){
System.out.println(fibo(4));
}
static int fibo(int n){
if(n <= 1){
return n;
}
return fibo(n-1) + fibo(n-2);
}
}
- Python
def fibo(n):
if n <= 1:
return n
return fibo(n-1) + fibo(n-2)
if __name__ == "__main__":
print(fibo(4))
Top comments (0)