Firstly, if you think there's something wrong with your lungs then please see a doctor.
As for measuring heart-rate recovery, you would expect to see improvements on the timeframe of days, so from workout to workout, not within a single workout. A common method of measuring heart-rate recovery is to measure heart-rate at the end of a bout of exercise, rest for one minute, and then measure it again.
In the case of interval training, you would need to determine what constitutes a bout of exercise. If you're doing Tabata intervals, 20 seconds exertion followed by 10 seconds of rest, then you don't have a minute between rounds of exertion, so you would need to consider a bout to be the whole series of rest-exertion cycles, and measure the heart rate drop following the final round of exertion only. Whereas if you are doing longer intervals, say 5 minutes exertion and 5 minutes rest, then you could measure heart rate drop after each period of exertion.
In either case, you should be able to produce multiple measurements per workout. (Let's assume with Tabata intervals that you would do a bout of 8 rest-exertion cycles, rest for several minutes, then repeat the bout multiple additional times.) If your exercise and rest periods are long enough that each one maxes out your heart rate, and then allows it to return to normal, then the measurements should be similar, and you could just average them to get a single value for the whole workout. Or if your exercise and rest periods are shorter, such that your heart rate does not max out in the first bout, and it takes multiple bouts for the cumulative work to max out your heart rate, then you would expect the measurements to differ, and you would need to compare, e.g. the last measurement of a workout with the last measurement of the previous workout.
Finally, if the number of bouts you perform in a workout is greater than the number of measurements that you want to take, then you could just select a specific batch of them to measure, such as first, middle and last.