Understanding Recursion in C++

In many ways, we can think of recursion in programming similar to recursion in mathematics or fractals in art, where a pattern repeats within itself. But in programming, recursion refers to a function that calls itself within its definition. It's a powerful tool, allowing us to write elegant solutions to problems that can be naturally split into smaller, similar subproblems.

Consider the Fibonacci sequence, a classic example of recursion. Each number in the sequence is the sum of the two preceding ones. We can express this mathematically as follows:

• fibonacci(0) = 0
• fibonacci(1) = 1
• fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) for n > 1

This translates directly into a recursive function in C++, as shown in the accompanying example code. For the base cases, fibonacci(0) and fibonacci(1), we return the input n directly. For larger numbers, we make two recursive calls to calculate the two preceding fibonacci terms, and return their sum.

This simple function doesn't just calculate Fibonacci numbers - it also demonstrates a deeper property of recursion. Each recursive call to fibonacci makes two more calls, creating a tree of calculations that grows exponentially with input size. Understanding this property is crucial to understanding recursion, and to understanding why recursion can be both powerful and tricky to use effectively.

xxxxxxxxxx

#include <iostream>

using namespace std;

​

int fibonacciRecursion(int n) {

  if(n<=1) {

    return n;

  } else {

    return(fibonacciRecursion(n-1) + fibonacciRecursion(n-2));

  }

}

​

int main() {

  int n;

  cout << "Enter the number of terms of series : ";

  cin >> n;

  cout << "\nFibonnaci Series : ";

  for(int i = 0; i < n; i++) {

    cout << " " << fibonacciRecursion(i);

  }

  return 0;

}