[go: up one dir, main page]
Scribd
Upload
126 views3 pages

Tri Recursion Explained

This document describes a recursive function in R called `tri_recursion` that calculates the sum of the first `k` natural numbers, known as triangular numbers. It details the function's execution steps, including recursive calls and the unwinding process that produces the triangular number sequence for `k = 5`. Additionally, it presents an alternative iterative approach that computes the sum in constant time, highlighting the efficiency differences between the two methods.

Uploaded by

sairam91619
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
126 views3 pages

Tri Recursion Explained

This document describes a recursive function in R called `tri_recursion` that calculates the sum of the first `k` natural numbers, known as triangular numbers. It details the function's execution steps, including recursive calls and the unwinding process that produces the triangular number sequence for `k = 5`. Additionally, it presents an alternative iterative approach that computes the sum in constant time, highlighting the efficiency differences between the two methods.

Uploaded by

sairam91619
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Triangular Number Recursion in R

### Introduction
This document explains the recursive function `tri_recursion` in R, which calculates the sum of the first `k` natural
numbers using recursion. This sum forms a sequence known as **triangular numbers**.

### Corrected R Code


```r
tri_recursion <- function(k) {
if (k > 0) {
result <- k + tri_recursion(k - 1) # Recursive call
print(result) # Print result
return(result) # Return result
} else {
return(0) # Base case: return 0 when k is 0
}
}

# Example call
tri_recursion(5)
```

### Step-by-Step Execution

#### Step 1: Initial Call


```r
tri_recursion(5)
```
- Since `5 > 0`, the function calls itself with `k = 4` before printing or returning anything.

#### Step 2: Recursive Calls Until Base Case


Each recursive call reduces `k` by 1 until reaching `k = 0`:

| Function Call | Recursive Call |


|--------------------|------------------|
| `tri_recursion(5)` | `tri_recursion(4)` |
| `tri_recursion(4)` | `tri_recursion(3)` |
| `tri_recursion(3)` | `tri_recursion(2)` |
| `tri_recursion(2)` | `tri_recursion(1)` |
| `tri_recursion(1)` | `tri_recursion(0)` |
| `tri_recursion(0)` | Returns `0` |

#### Step 3: Unwinding and Printing Values

Once `k = 0`, the function starts returning values:

| Returning From | Computation | Printed Value | Returned Value |


|---------------|------------|---------------|---------------|
| `tri_recursion(1)` | `1 + 0` | `1` | `1` |
| `tri_recursion(2)` | `2 + 1` | `3` | `3` |
| `tri_recursion(3)` | `3 + 3` | `6` | `6` |
| `tri_recursion(4)` | `4 + 6` | `10` | `10` |
| `tri_recursion(5)` | `5 + 10` | `15` | `15` |

### Final Output


The function prints:
```r
1
3
6
10
15
```
These numbers represent the **triangular number sequence** for `k = 5`.

### Conclusion
This recursive function effectively calculates the sum of the first `k` natural numbers. The recursion follows a
**divide-and-conquer approach**, breaking down the problem into smaller subproblems and building up the result step
by step.

This method is an elegant way to compute triangular numbers but may not be optimal for large values of `k` due to
repeated function calls. Iterative approaches could be more efficient in such cases.

---
**Alternative Iterative Approach**
For efficiency, the sum of the first `k` numbers can be computed using the formula:
```r
triangular_sum <- function(k) {
return(k * (k + 1) / 2)
}

print(triangular_sum(5)) # Output: 15
```
This approach runs in constant time `O(1)`, whereas the recursive approach runs in `O(n)` time complexity.

You might also like