DEV Community

loading...

The "I *dislike* recursion" notes

kauresss profile image Kauress ・1 min read

Writing these notes while I cringe and procrastinate. Yes, recursion is useful, so is my pet cat. Covers the general concept of recursion.

Definition

A recursive function, is a function that calls itself till a certain condition is met. A break criteria is necessary so that the function does not call itself infinitely.

So you can express operations in terms of itself.

A simple example is:

#include <iostream>

using namespace std;

void recurse (int count) // Each call gets its own count
{
  cout<< count <<"\n";

  recurse ( count + 1 );
}

int main()
{
  recurse ( 1 ); //First function call, so it starts at one        
}


2 parts of a recursive function

  1. Base case (the condition that stops the recursion process)
  2. Recalling condition (the condition that causes the function to call itself)

Example

The classic example is calculating the factorial of a number.

#include <iostream>
using namespace std;
//Factorial function
int f(int n){
   /* This is called the base condition, it is
    * very important to specify the base condition
    * in recursion, otherwise your program will throw
    * stack overflow error.
    */
   if (n <= 1)
        return 1;
   else
       return n*f(n-1);
}
int main(){
   int num;
   cout<<"Enter a number: ";
   cin>>num;
   cout<<"Factorial of entered number: "<<f(num);
   return 0;
}


Discussion

pic
Editor guide