Recursion Fundamentals

A recursive function solves a problem by calling itself on a smaller subproblem. It needs a base case that stops and a progress measure that approaches that base. Recursion naturally describes hierarchical tasks, but it uses call-stack memory and can repeat work. This lesson implements factorial, naive Fibonacci and recursive summation to distinguish useful recursive structure from an inefficient recurrence.

Prerequisites: Functions; arrays; time and space analysis.

Build the idea

1. 1. State a base case and smaller task

   factorial(0)=1. For n>0, factorial(n)=n*factorial(n−1). The argument decreases by one, so a nonnegative starting n eventually reaches zero. A base case without progress is insufficient: calling factorial(n) again with the same n would never approach it. The return value of a smaller call is used only after that call finishes.

2. 2. Follow stack frames

   factorial(3) waits for factorial(2), which waits for factorial(1), then factorial(0). Returning 1 unwinds results 1,2,6. Each waiting call keeps its own n; the variable is not one shared object overwritten by every call. Depth is n+1, so time and stack are both linear, even though the code has only one visible multiplication line.

3. 3. See repeated work in Fibonacci

   F(0)=0,F(1)=1 and F(n)=F(n−1)+F(n−2). The direct function recomputes overlapping subproblems: F(5) requests F(4) and F(3), while F(4) requests F(3) again. Its call count is exponential, not O(n). Memoization or an iterative pair of values avoids repetitions; the direct version is deliberately limited to small n to make the issue visible.

4. 4. Recurse through an array

   sumFrom(a,i) returns zero at i==a.size(), otherwise a[i]+sumFrom(a,i+1). The index increases toward the end. A const vector reference avoids copying the entire array at every call. Every element is read once, but the call stack still has O(m) depth. A simple loop achieves the same sum with O(1) auxiliary space and is safer for large arrays.

5. 5. Trace and bound the example

   For n=5 and [1,2,3,4], factorial is 120, Fibonacci is 5, and recursive sum is 10. n≤20 ensures factorial fits long long, while m≤1000 keeps teaching recursion modest. These bounds do not guarantee unlimited recursion safety on every environment. For deep chains, prefer iteration or explicit stack frames rather than assuming O(n) memory automatically fits the call stack.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
long long factorial(int n){
    return n==0?1:n*factorial(n-1);
}
long long fibonacci(int n){
    if(n<=1){
        return n;
    }
    return fibonacci(n-1)+fibonacci(n-2); // Intentionally repeats work.
}
long long sumFrom(const std::vector<long long>&a,int i){
    if(i==(int)a.size()){
        return 0;
    }
    return a[i]+sumFrom(a,i+1);
}
int main(){
    int n,m;
    std::cin>>n>>m;
    std::vector<long long>a(m);
    for(long long&x:a){
        std::cin>>x;
    }
    std::cout<<factorial(n)<<' '<<fibonacci(n)<<' '<<sumFrom(a,0)<<'\n';
}

Complexity analysis

Factorial: O(n) time/O(n) stack. Naive Fibonacci: O(2ⁿ) upper-bound time (tighter Θ(φⁿ)) and O(n) maximum stack depth, not O(2ⁿ) simultaneously live stack. Array sum: O(m) time/O(m) stack. Overall O(2ⁿ+m) time and O(n+m) total storage including input; sequential call stacks peak at O(max(n,m)).

Example input and output

Read n m with 0≤n≤20, 0≤m≤1000, then m integers |value|≤10^9. Output n!, F(n), and the array sum.

Input

5 4
1 2 3 4

Output

120 5 10

Factorial multiplies 1..5, Fibonacci follows 0,1,1,2,3,5, and the four array entries sum to 10.

Practical applications

Use recursion for divide-and-conquer, trees and search decisions that mirror smaller subproblems. Use iteration for simple long sequential scans and numeric recurrences when it reduces stack use. Use memoization or DP for overlapping recursive subproblems rather than recomputing them.

Check your understanding

Why is naive recursive Fibonacci slow?

Put it into practice

Write iterative versions of factorial, Fibonacci and array sum.